Dynamic Programming

사용조건

1. 최적 부분 구조 (Optimal Substructure)

• 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있습니다.

2. 중복되는 부분 문제 (Overlapping Subproblem)

• 동일한 작은 문제를 반복적으로 해결해야 합니다.

예시

• 피보나치 수열

fibo(n) = fibo(n - 1) + fibo(n - 2) (a>=3,a1 = 1, a2 = 1)

시간복잡도 O(2^n)

Memoization

• 메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 하나이다.
• 한 번 계산한 결과를 메모리 공간에 메모하는 기법이다.
  • 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다.
  • 값을 기록해 놓는다는 점에서 캐싱(Cashing)이라고도 한다.
• 피보나치 수열의 경우 메모이제이션을 이용할 때 시간복잡도가 O(n)으로 줄어든다

탑다운 vs 바텀업

• 하향식, 상향식
• DP의 전형적인 형태는 바텀업 방식
• 엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 록해 놓는 넓은 개념을 의미한다.
  • 메모이제이션은 DP에 국한된 개념이 아니다.