2025년 4월 20일
동적 계획법 (Dynamic Programming)
1. 동적 계획법 (Dynamic Programming)의 개념 및 특징
| 개념 | 복잡한 문제 해결 위해 하위 문제로 나누어 점화식을 도출하고 초기 해와 점진적 해를 계산하는 상향식 문제해결 접근 전략 | |
|---|---|---|
| 특징 | 상향식 문제 해결 (Bottom-Up Approach) | – 문제를 하위 문제로 분할하고 하위 문제 해결 후 결과 재사용 |
| 최적성의 원리 적용 | – 주어진 문제 최적해가 분할된 부분 문제에 대한 최적해로 구성 | |
| 점화/재귀 관계식 적용 | – 하위 문제들이 서로 독립적이지 않고 점화/재귀 관계식 도출 | |
- 반복 요소 존재, 하위 문제가 기하급수적으로 증가하는 경우 효과적 최적해 도출 기법으로 활용
- 예를 들어, 피보나치 수열은 F[n] = F[n-1] + F[n-2] + … 점화식을 통해 동적 계획법을 활용하여 문제해결
2. 동적 계획법의 전제 조건/동작 원리 및 프로세스
(1) 동적 계획법의 전제 조건/동작 원리
| 전제 조건 | – 최적성 원리 만족 시 점화/재귀 관계식 도출 가능하여 동적 계획법 적용 가능 – 점화 재귀 관계식 도출 : an+1 = f(an) [함수 f(an): 수열 {an}의 점화식점화식, an/an+1: 인접 항] | |
|---|---|---|
| 동작 원리 | 최적의 하부 구조 (Optimal substructure) | – Problem의 최적해 안에 sub-problem에 대한 최적해가 존재 – 최적 해 비용 = 각 product A1 … Ak와 Ak+1 … An의 계산 비용 + 두 product의 곱셈 비용 |
| 하위 문제 중복 (Overlapping Sub-problem) | – 문제를 하위 문제로 분할 시 중복되는 계산 문제 존재 – 동일한 하위 문제 반복 수행 시 최적화 문제는 Overlapping Sub-problem을 가진다고 표현 | |
(2) 동적 계획법의 프로세스
 |
- 동적 계획법은 분할정복 기법과 같이 부분 문제의 해를 결합해 문제를 해결하는 방식이지만, 해를 저장 후 재사용하는 방식 등 차이점 존재
3. 동적 계획법의 사례 및 유사 문제해결 전략 비교
(1) 동적 계획법의 사례 (피보나치 수열 사례)
| 피보나치 수열 구현 코드 | int fib(int n) { f[1] = f[2] = 1; for (int i=3; i<=n; i++) f[i] = f[i-1] + f[i-2]; return f[n]; } |
|---|---|
| 피보나치 수열 구현 방식 |  |
(2) 동적 계획법과 유사 문제해결 전략 비교
| 비교 항목 | 분할과 정복 (Devide & Conquer) | 동적 계획법 (Dynamic Programming) | 탐욕법 (Greedy Method) |
|---|---|---|---|
| 문제 해결 접근 방식 | – 최소 문제로 분할하여 원래의 문제 해를 구하는 방식 | – 하위 문제의 해 저장 후 큰 문제의 해를 점진적으로 구하는 방식 | – 현재 단계에서 국부적 최적 해를 선택하여 전체 해를 구하는 방식 |
| 주요 특징 | – 하향식 접근 – 분할 → 정복 → 결합 | – 상향식 접근 – 메모이제이션 | – 국부적 최적 해 선택 – 근사치 추정 |
| 주요 알고리즘 | – 이진 탐색 알고리즘 – 병합 정렬 알고리즘 | – 플로이드-워셜 알고리즘 – 피보나치 수열 | – 최소 신장 트리 – 동전 거스름돈 문제 |
- 동적 계획법을 이용한 문제해결 접근 시 점화식의 복잡도에 따라 계산 성능이 좌우되므로 점화식은 최대한 단순화 필요
[참고]
- 로버트 세지윅 외, 길벗, 알고리즘, 2018
- 권오흠, 국립부경대학교, 알고리즘
About The Author
