Dynamic Programming1 [Python] 다이나믹 프로그래밍 (DP) 다이나믹 프로그래밍이란? 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 의미한다. 문제를 여러 개의 하위 문제로 나누어 푼 다음, 그 결과들을 결합하여 답을 구한다. 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는, 메모리 공간을 조금 더 사용함으로 연산 속도를 늘릴 수 있는 알고리즘 설계 기법이다. 예시 이렇게 글로만 보면 확 와닿지 않는다. 그럼 예시를 한 번 보도록 하자. 다이나믹 프로그래밍(이하 DP)으로 해결할 수 있는 대표적인 문제 예시로 피보나치 수열이 있다. n번째 피보나치 수는 n-1번째 수 더하기 n-2번째 수이다. 이걸 정리하면 f(n) = f(n-1) + f(n-2)이다. def fibo(n): if n == 0: retu.. 2022. 1. 15. 이전 1 다음