다이나믹 프로그래밍 (DP) 정리

다이나믹 프로그래밍이란?

복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법이다.

 

1. Top-down 하향식 (메모이제이션, memoization)

• 재귀 함수로 구현한다.
• 큰 문제를 작은 문제로 나누어 먼저 해결한다는 방향이다.
• 이미 계산한 값은 캐시(dict, 배열) 에 저장해두고, 다시 호출되면 캐시에서 바로 꺼낸다.

 

2. Bottom-up 상향식 (타뷸레이션, tabulation)

• 반복문으로 구현
• 가장 작은 부분 문제부터 차례로 테이블을 채워나간다.
• 재귀 호출이 없다. 

 

 

 

DP 가 필요한 경우 

1. 최적 부분 구조 :
   • 부분 문제의 최적해로 전체 최적해 구성
   • ex) 최단 경로 문제 A → C 가 A → B + B → C 로 이루어짐
2. 중복 부분 문제 :
   • 같은 문제가 반복적으로 등장
   • ex) fib(5) 를 구하려고 fib(3) 을 여러 경로에서 반복 호출

 

* 최적 부분 구조만 있으면 → 분할 정복

 

 

 

DP 의 프레임워크

1. 상태 정의 (부분 문제 정의)
   • dp[i] 가 무엇을 의미하는지 정의
2. 점화식 세우기
   • dp[i] 이전 상태들로 어떻게 표현하는지
3. 기저 조건 설정 
   • 초기값을 설정
4. 계산 순서 결정
   • bottom-up 상향식 vs top-down 하향식
5. 구현

 

 

 

시간/공간 복잡도 

(상태의 개수) X (상태 전이에 걸리는 시간)