최근 수정 시각: 2021-08-08 15:22:21
_
1. 소개
동적 계획법(Dynamic Programming, DP)은 서로 비슷한 형태의, 작은 부분 문제 여러 개를 해결하여 전체 문제를 해결하는 알고리즘이다.
예를 들어 피보나치 수열을 만드는 재귀적 수식 \(F_i = F_{i-1} + F_{i-2}\)에서 \(F_{30}\)을 구하기 위해 \(F_{3}\)부터 \(F_{30}\)까지 부분 문제들을 \(F_i = F_{i-1} + F_{i-2}\)로 풀어 나가 \(F_{30}\)를 구하는 방식을 동적 계획법이라고 할 수 있다. 이 문제를 해결하기 위해 피보나치 수를 위에서부터 아래로 재귀함수를 사용하여 구하면 같은 \(F_i\)를 여러번 계산하여 시간복잡도가 많이 커질텐데, 동적 계획법을 사용하면 이를 빠르게 처리할 수 있다.
동적 계획법에서는 비슷한 형태의 부분 문제로 전체 문제를 나누는데, 이와 비슷하게 전체 문제를 부분 문제로 나누고 그 부분 문제들을 계속 나눠 전체 문제를 해결하는 방식을 Divide & Conquer라고 한다.
2. 종류
2.1. Top-Down
피보나치 수를 예로 들면, 피보나치 수를 구하는 과정에서 int F(int x){ return F(x-1) + F(x-2); }와 비슷한 코드를 사용할 때 단점은 같은 수를 구하기 위해 여러번 재귀 과정을 거치기 때문에 시간이 오래 걸린다는 점이다. 이미 계산한 부분문제를 다시 묻는 경우 저장한 값을 사용하여 계산 과정을 반복하지 않으면 이 문제를 해결할 수 있는데, 이를 메모이제이션(Memoization)이라고 한다.
2.2. Bottom-Up
피보나치 수를 구할 때 \(F_3\)부터 \(F_n\)까지 올라가면서 부분 문제를 해결하면 앞에서 처리했던 부분 문제들을 사용하면서 새로운 부분 문제들을 쉽게 해결할 수 있다. Top-Down 방식을 사용한 직관적인 방법을 잘 바꿔 Bottom-Up 방식으로 구현하면 더 간단해지는 경우가 많다.
3. 예시
3.1. LCS
LCS 참고
3.2. Dijkstra Algorithm
3.3. 0-1 Knapsack Problem
배낭 문제(Knapsack Problem)은 두 가지 종류가 있는데, Greedy Algorithm으로 해결할 수 있는 분할 가능 배낭문제(Fractional Knapsack Problem)와 달리 0-1 배낭 문제(0-1 Knapsack Problem)는 동적 계획법을 사용해서 해결해야 한다.
0-1 Knapsack Problem은 각 물건들마다 무게 \(w_i\)와 가치 \(v_i\)가 주어져 있고 가방에 담을 수 있는 최대 무게 \(S\)가 주어졌을 때, 최대 무게를 넘지 않게 가방에 물건들을 담았을 때 얻을 수 있는 가치의 합의 최댓값을 구하는 문제다.
이 문제를 동적 계획법으로 풀기 위해 점화식을 세워보면 \(i\)번 물건까지 고려했을 때 총 무게가 \(j\)인 경우 가치 합의 최댓값을 \(DP(i, j)\)라 하면 \(DP(i, j) = \max(DP(i-1, j), DP(i-1, j-w_i) + v_i)\)로 표현할 수 있다. 이때 전체 문제를 해결하기 위해서는 \(N \times S\)개의 부분 문제를 해결하면 되기 때문에 \(O(NS)\) 시간복잡도로 문제를 해결할 수 있다.
최근 수정 시각: 2021-08-08 15:22:21