1. 동적 계획법 (Dynamic Programming, 다이내믹 프로그래밍) 전략
ㅇ 중첩된 부 문제들을 갖는 복잡한 문제를 해결하는 최적화 기법
- 주로, 아래에서 위로 해결하면서, 전체 문제를 해결하는, 상향식 접근 방식을 취함
※ 동적 계획 용어 고안 : 1953년 리처드 벨먼 (Richard Ernest Bellman, 1920~1984)
- 미국의 응용수학자
※ 분할 정복, 동적 계획 방법 간의 비교
- 분할 정복 : 분할된 부 문제들이 서로 독립적임
- 동적 계획 : 분할된 부 문제들이 서로 의존적임
2. 동적 계획법의 적용 대상
ㅇ 주어진 문제가,
- 최적 부분 구조 (Optimal Substructure)를 갖고,
- 부 문제들이 중첩되는 (Overlapping Subproblem) 정도가 높을 때, 유용함
ㅇ 최적성의 원리
- 주어진 문제에 대한 최적해가 소문제에 대한 최적해들로 구성된다는 원리
ㅇ 例)
- 피보나치 수열
- 최소값/최대값을 구하는 최적화 문제
- 최단경로 알고리즘 (플로이드 알고리즘, 벨만 포드 알고리즘)
. 어떤 최단 경로 내 각각의 부분 경로들도 최단 경로이어야 됨
3. 동적 계획법의 풀이 방식 개요
ㅇ 간단한 하위 문제부터 해결하면서,
ㅇ 하위 문제의 해를 테이블에 저장해 놓고,
ㅇ 이를 이용하여, 좀더 복잡한 상위 문제를 해결하여 나아감
4. 동적 계획법의 풀이 방식 요점
ㅇ 재귀 관계식을 세워, 입력 사례를 더 작은 입력 사례로 분할 함
- 단, 통상적인 재귀 접근과는 달리, 상향식 임
. 즉, 하위 문제를 풀고, 이들 해들을 결합시키면서, 전체 해를 구함
ㅇ 주로, 크기별로 모든 문제들을 미리 풀어놓고, 이를 찾아 재사용하게 됨
- 즉, 각 부 문제의 해답을 1회 만 풀어 저장하고,
- 나중에 동일한 부 문제의 해답이 요구될 때, 이렇게 저장된 해답을 찾아서 해결함
5. 동적 계획법의 주요 특징
ㅇ 분할된 부 문제들이 서로 독립일 필요는 없음
ㅇ 특히, 주어진 문제가 재사용 가능한 여러 중복된 부 문제들로 중첩되면, 적합함
6. 동적 계획법의 풀이 구현 방식 종류
ㅇ Memoization (메모이제이션) (하향식 접근 풀이)
ㅇ Tabulation (상향식 접근 풀이)