Dynamic Programming (동적계획법)

1. 동적계획법

   : 큰 문제를 여러 개의 작은 부분으로 분할하여 해결하는 기법.

 

 

2. DP vs. Divide & Conquer

	Dynamic Programming	Divide & Conquer
공통점	큰 문제를 여러 개의 작은 문제로 나눠서 해결한다.
차이점	작은 문제에서 중복 O	작은 문제에서 중복 X

 

 

3. DP의 조건

 1) 작은(부분) 문제들이 중복된다.

      -> 부분 문제 한 번만 계산한 후 그 해를 테이블에 저장.

      -> 그 부분 문제가 중복될 때마다 테이블에서 미리 저장해둔 해를 반환.

 

 2) 최적 부분 구조를 가진다.

      -> 작은 문제의 해로부터 큰 문제의 해를 구할 수 있음.

 

 

4. How To Solve DP

Top-Down / 재귀함수를 사용하는 방식 (Memoization) -> 시간복잡도 문제 발생 가능.

                 이전에 계산했던 값을 메모리에 저장해두었다가 나중에 재사용.

Bottom-Up / 재귀를 피하기 위한 방법.

                  간단한 하위 문제를 해결하면서 상위 문제로 나아가는 방식.

 

Memoization과 Bottom-Up 모두 동적계획법의 핵심 기술.

 

 

DP 해결 방식

1. base case 구하기.
2. base case를 이용하여 점화식 구하기.
3. 최적해를 구하기 위한 코드 구현 (보통 Bottom-Up 방식)
4. 시간복잡도 계산