동적계획법(Dynamic Programming)
동적계획법
개요
문제를 부분 문제로 나눈 후, 해당 부분 문제의 최적해를 결합하여 문제의 최적해를 구할 수 있을 때 중복되는 부분 문제의 답을 저장해 두었다가 재활용하는 알고리즘 설계 방식
조건
총 두 조건이 만족한다면 동적계획법을 활용할 수 있다.
중복되는 부분 문제(Overlapping Subproblems): 부분 문제들의 최적해가 두 번 이상 중복으로 활용되는 경우에만 활용이 가능하다. 그렇지 않을 경우 부분 문제를 여러번 계산할 필요가 없으므로 동적계획법을 활용할 필요가 없다.
최적 부분 구조(Optimal Substructure): 문제의 최적해를 찾고자 할 때 부분 문제들에 대한 최적해를 찾고, 이를 결합하여 문제의 최적해가 나와야 활용이 가능하다. 만약 부분 문제를 활용하여도 문제의 최적해를 구하지 못한다면 동적계획법으로는 제대로 된 값을 구하는 것이 불가능할 것이다.
구현 방식
사용되는 기법 및 테크닉
메모이제이션(Memoization) 기법: 함수의 결괏값을 저장해 두었다가 재활용하는 최적화 기법이다. 해당 기법을 사용하기 위해서는 참조적 투명성(referential transparency)이 적용되어야 한다.
참조적 투명성이란 함수의 반환 값이 입력 값만으로 결정되는 것을 뜻한다. 이는 다시말해 입력이 고정되어 있다면 출력도 고정되어 있어야 함을 뜻한다.
표(Tabulation) 기법: 문제를 쪼개어 작은 부분 문제로 나눈 후 작은 문제의 해부터 큰 문제의 해 순으로 테이블에 저장하는 방식으로 문제를 해결하는 기법이다.
슬라이딩 윈도우(Sliding Window) 테크닉: 쉽게 말해 일정 크기로 고정된 배열을 밀어주면서 사용하지 않는 공간을 줄여주는, 공간복잡도를 줄이는 방식의 테크닉 DP에서는 보통 표(Tabulation) 기법에서 공간을 효율적으로 활용하기 위해 사용한다.
Top-Down
구하고자 하는 문제를 호출 후 이를 풀이하기 위한 작은 문제를 재귀적으로 호출하여 최종적인 최적해를 찾는 구현 방식 메모이제이션(Memoization) 기법을 사용하고, 재귀 호출(Recursive Call)을 활용하여 구현한다.
풀이하는 대략적인 플로우는 다음과 같다.
- 부분 문제를 설계하며 최적해를 반환하는 완전 탐색(bruteforce) 알고리즘 설계
- 최적 부분 구조가 설립할 경우 함수에 최대한 부분 문제의 최적해만을 활용하는 부분 문제로 변환
- 적절한 변환을 통하여 메모이제이션
Bottom-Up
가장 작은 문제부터 해결하며 최종적인 문제의 최적해를 찾는 구현 방식 표(Tabulation) 기법을 사용하고, 반복자(Iterater)를 활용하여 구현한다.
해당 풀이 방식은 슬라이딩 윈도우 기법으로 메모리 사용량을 줄일 수 있다.
비교
| Top-Down | Bottom-Up | |
|---|---|---|
| 접근 방식 | 큰 문제 - > 작은 문제 | 작은 문제 -> 큰 문제 |
| 기법 | 메모이제이션(Memoization) | 표(Tabulation) |
| 구현 | 재귀 호출(Recursive Call) | 반복(Iteration) |
| 장점 | 직관적 | 메모리 사용량 및 성능이 비교적 우월 |
| 단점 | 스택 오버플로우가 날 가능성이 존재 | 최적해를 구할 때 사용되지 않는 부분 문제까지 계산 |
웰노운 테크닉들
행렬 거듭제곱을 이용한 DP (exponentiation_by_squaring)
분할정복을 활용하여 행렬의 거듭제곱을 $O(n^3log{m})$의 시간복잡도로 풀이할 수 있다는 것을 선형 점화식 DP에 활용하는 테크닉이다.
분량이 너무 길어지므로 이 글 참조 (추후 정리 예정)
비트마스킹을 활용한 DP (bit_dp)
보통은 재활용 할 값의 매개변수 또는 해가 bool형 배열일 때 사용한다.
비트마스킹에 관한 글은 추후 추가 예정
트리DP (tree_dp)
추후 추가 예정
웰노운 문제들
배낭문제(knapsack problem)
정확히는 0-1 Knapsack Problem으로 문제는 다음과 같다.
” $N$의 무게를 버틸 수 있는 가방이 있고, $M$개의 물건이 각각 $W_i$의 무게와, $P_i$의 값어치를 가질 때 가방에 들어갈 수 있는 물건들의 값어치의 합의 최댓값은?”
여기서 부분 문제를 “ $i$번 물건까지 고려했을 때 $j$의 무게가 더 들어가는 가방에 들어갈 수 있는 값어치의 합의 최댓값” 으로 정의한다면 $j$가 $W_i$보다 크거나 같다면 물건이 들어 갈 수 있다는 뜻이고, 적다면 물건이 더 들어갈 수 없다는 뜻이므로 점화식은 다음과 같다.
\[DP[i][j] = \begin{cases} max(DP[i - 1][j - W_i], DP[i - 1][j]) & W_i \le j \\ DP[i - 1][j] & W_i > j \end{cases}\]기타
마르코프 연쇄 모델
현실 세계의 현상들을 모델링 하기 위하여 사용되는 모델이다. 성질은 아래와 같다.
- 유한개의 상태가 존재.
- 매 시간마다 상태가 변경됨.
- 현재 상태 a에서 다른 상태 b로 옮겨갈 확률은 a에 좌우. 이때 a 이전의 상태나 시간은 영향을 주지 않음.