Dynamic Programming (동적 계획법)
Dynamic Programming?
DP(Dynamic Programming, 동적 계획법)는 복잡한 문제를 여러 개의 작은 하위 문제(Subproblem)로 나누어 해결한 뒤, 그 결과를 재사용하여 전체 문제를 효율적으로 해결하는 알고리즘입니다.
대표적인 예로 피보나치 수열을 생각해 보겠습니다.
1
2
3
4
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
위 코드는 매우 직관적이지만 비효율적입니다. 그 이유는 fib(6)을 계산할 때 fib(4)는 여러 번 호출되고, fib(3)은 그보다 더 많이 호출됩니다. 동일한 값을 계속 계산하고 있기 때문입니다.
이러한 방식의 시간 복잡도는 O(2ⁿ) 수준으로 입력이 조금만 커져도 실행 시간이 급격히 증가하게 됩니다.
DP는 이 문제를 해결하기 위해 이미 계산한 결과를 저장합니다. 예를 들어 fib(4)를 한 번 계산했다면 그 값을 배열이나 Map에 저장해 두고, 다음에 fib(4)가 필요할 때는 저장된 값을 바로 사용합니다.
1
2
3
4
5
int fib2(int n) {
if (DP[n] != -1) return DP[n];
DP[n] = fib2(n - 1) + fib2(n - 2);
return DP[n];
}
이렇게 하면 동일한 상태(n)를 여러 번 계산할 필요가 없습니다. 결과적으로 각 상태는 한 번만 계산되므로 시간 복잡도는 O(N)으로 줄일 수 있습니다.
| n | 3 | … | 18 | … | 25 |
|---|---|---|---|---|---|
| fib(1) 호출 횟수 | 2 | … | 2584 | … | 75025 |
| fib2(1) 호출 횟수 | 2 | … | 2 | … | 2 |
위 표는 각 함수가 fib(1)을 몇 번 호출하는지를 나타냅니다. DP가 중복 계산을 제거하여 호출 횟수를 크게 줄이는 것을 확인할 수 있습니다.
따라서 DP의 핵심은 중복 계산을 제거하는 것입니다. 따라서 문제를 분석할 때 “같은 상태가 반복해서 등장하는가?”를 먼저 확인해 보는 것이 DP를 떠올리는 좋은 출발점이 됩니다.
DP 핵심 조건
DP를 적용하려면 아래 두 조건을 모두 만족해야 합니다.
Overlapping Subproblems (중복되는 부분 문제)
중복되는 부분 문제란, 문제를 분할하는 과정에서 동일한 상태를 여러 번 계산하는 경우를 의미합니다.
예를 들어 (0, 0)에서 (2, 2)까지 오른쪽 또는 아래쪽으로만 이동한다고 가정해 보겠습니다.
1
2
3
4
5
6
7
(0,0)
├─ (0,1)
│ ├─ (1,1)
│ └─ ...
└─ (1,0)
├─ (1,1)
└─ ...
위 그림에서 (1, 1)에 도달하는 경우가 여러 경로에서 반복됩니다. 이 처럼 동일한 상태를 여러 번 계산하는 성질을 중복되는 부분 문제 라고 합니다.
Optimal Substructure (최적 부분 구조)
최적 부분 구조란, 전체 문제의 최적해가 하위 문제들의 최적해를 이용해 구성할 수 있는 성질을 의미합니다.
예를들어 a -> d으로 가는 최단 경로가 a -> b -> c -> d라고 가정해 보겠습니다. 그렇다면 a -> c으로 가는 최단 경로도 a -> b -> c여야 합니다.
즉, a -> c으로 가는 최단 경로를 알게 된다면 a -> d으로 가는 최단 경로를 쉽게 계산할 수 있습니다.
이처럼 부분 문제의 최적해를 이용하여 전체 문제의 최적해를 구성할 수 있는 성질을 최적 부분 구조 라고 합니다.
구현 방법
DP는 크게 두 가지 방식으로 구현할 수 있습니다.
Top-Down (Memoization)
Top-Down 방식은 큰 문제 부터 시작하여 필요한 하위 문제를 재귀적으로 해결해 나가는 방법입니다. 이미 계산된 결과는 메모리에 저장해 두고 동일한 상태가 다시 등장하면 저장된 값을 재사용합니다.
피보나치 수열을 예를 들면 다음과 같습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int[] dp = new int[100];
int fib(int n) {
if (n <= 1) {
return n;
}
// 중복 계산 방지, 값 재활용
if (dp[n] != 0) {
return dp[n];
}
// 작은 문제로 분할하여 처리
return dp[n] = fib(n - 1) + fib(n - 2);
}
fib(5)를 호출하면 필요한 하위 문제인 fib(4), fib(3) 등을 재귀적으로 계산합니다. 이후 동일한 상태가 다시 등장하면 저장된 값을 사용하므로 중복 계산을 방지할 수 있습니다.
Bottom-Up (Tabulation)
Bottom-Up 방식은 가장 작은 문제부터 차례대로 해결하면서 큰 문제의 답을 만들어 가는 방법입니다. 재귀 호출을 사용하지 않고 반복문을 통해 DP 테이블을 채워 나갑니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int fib(int n) {
if (n <= 1) {
return n;
}
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
dp[0], dp[1]부터 시작하여 순서대로 값을 계산하므로, dp[i]를 계산할 때 필요한 dp[i - 1]과 dp[i - 2]는 이미 계산되어 있습니다.