동적 프로그래밍(Dynamic programming)

• 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법

동적 프로그래밍의 조건

• 작은 문제가 반복이 일어나는 경우 (최적 부분 구조)
• 같은 문제는 구할 때마다 정답이 같을 때

구현순서

1. 구하고자 하는 큰 문제를 작은 문제들로 나눈다.
2. 가장 작은 부분문제를 푼 뒤 값을 저장한다. (메모이제이션)
3. 메모이제이션 된 문제들의 값을 이용해 점차 더 큰 문제들의 답을 구한다.
4. 가장 큰 문제를 풀이할때까지 반복한다.

메모이제이션(Memoization)

• 동적 프로그래밍에서는 작은 문제들이 반복되고 이 문제들의 결과값이 항상 같다. 이점을 이용해서 한번 계산한 작은 문제를 저장해놓고 다시 사용하는 것을 Memoization이라고 한다.

ex) 피보나치 수

• 피보나치 수열은 f(n) = f(n-1)+f(n-2)의 식을 갖는 수열이다.
• N이 증가함에 따라 호출되는 함수의 수가 기하급수 적으로 증가!