동적 프로그래밍 (Dynamic Programming)

동적 프로그래밍은 재귀적으로 구현한 알고리즘에서 중복 호출이 일어나 심각한 비효율이 발생할 때 이를 해결하는 방법이다 예를들어 피보나치 수를 아래와 같이 정의할 때 f(n) = f(n-1) + f(n-2) f(1) = f(2) = 1 * n은 자연수 n번째 피보나치 수 f(n)(n>2)은 피보나치 수 f(n-1)와 피보나치 수 f(n-2) 를 포함한다. 이와같이 큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있을 때 최적 부분 구조(Optimal Substructure)를 가졌다고 하고, 아래와 같은 재귀호출로 자연스럽게 구현할 수 있다. def fibo(n) if n==1 or n==2: return 1 else: return fibo(n-1) + fibo(n-2) 중복호출로 인한 비효율이 있는..