Dynamic Programming (DP)
Divde & Conquer 과 같이 문제를 작은 부분문제들로 쪼개는 과정을 거친다.
하지만 DP는 memoization을 사용한다는 차이점이 있다.
여기서 memoization이란 한 번 계산한 값을 저장해 두었다 재활용하는 기법을 의미한다.
종합하자면, Divide & Conquer은 부분 문제들이 서로 겹치지 않을 때 사용하기 좋다.
만약 동일한 부분 문제들이 계산 과정에서 여러 번 등장한다면, 중복 계산을 피하는 DP를 사용하는 것이 좋다.
이항 계수 (binomial coefficient) 계산을 예로 들어보자.
$$ \binom{4}{2} = \binom{3}{1} + \binom{3}{2} = (\binom{2}{0} + \binom{2}{1}) + (\binom{2}{1} + \binom{2}{2}) $$
계산이 중복되는 모습을 확인할 수 있다.
# Without memoization
int binom(int n, int k) {
if (k == 0 || n == k) {
return 1;
}
return binom(n - 1, k - 1) + binom(n - 1, k);
}
# With memoization
vector<vector<int> > dp(100, vector<int>(100, -1);
int binom(int n, int k) {
if (dp[n][k] != -1) {
return dp[n][k];
}
if (k == 0 || n == k) {
return dp[n][k] = 1;
}
return dp[n][k] = (binom(n - 1, k - 1) + binom(n - 1, k));
}
가능하지 않은 값으로 초기화해준 cache를 만들어 주고 사용을 할 때 초기화 해준 값이 변경되어있다면 바로 가져와서 쓰고 그대로라면 계산해서 넣어준다.
메모리를 희생하고 시간을 버는거지만, 공정한 trade off라기엔 효용이 너무 좋아진다.
대표격인 문제로는
'Problem Solving > 알고리즘' 카테고리의 다른 글
0 - 1 BFS (0) | 2022.03.22 |
---|---|
Prefix function, Knuth-Morris-Pratt algorithm (0) | 2022.01.17 |
Following materials (0) | 2022.01.17 |
분할 정복 (0) | 2022.01.07 |
무식하게 풀기 (0) | 2022.01.06 |
댓글