동적 계획법(Dynamic Programming)의 원리와 설계 - soo:bak
작성일 :
동적 계획법이란?
동적 계획법(Dynamic Programming, DP) 은 큰 문제를 작은 부분 문제로 나누어 해결하고,
그 결과를 저장하여 중복 계산을 방지하는 알고리즘 설계 기법입니다.
피보나치 수열 F(n) = F(n-1) + F(n-2)를 단순 재귀로 계산하면,
F(50)을 구하는 데만 수십억 번의 함수 호출이 필요하여 실행 시간이 매우 오래 걸립니다.
그러나 동적 계획법을 사용하면 단 50번의 계산으로 같은 결과를 얻을 수 있습니다.
동적 계획법은 중복되는 계산을 한 번만 수행하고 그 결과를 재사용함으로써,
지수 시간 복잡도의 문제를 다항 시간으로 해결합니다.
동적 계획법이 적용 가능한 문제는 다음 두 가지 특징을 가집니다:
1. 최적 부분 구조 (Optimal Substructure)
큰 문제의 최적 해가 작은 부분 문제의 최적 해로 구성됩니다.
2. 중복 부분 문제 (Overlapping Subproblems)
동일한 부분 문제가 여러 번 반복적으로 계산됩니다.
이 두 조건을 만족하는 문제에 동적 계획법을 적용하면,
불필요한 재계산을 피하고 효율적으로 최적해를 구할 수 있습니다.
왜 중복 계산이 문제인가?
피보나치 수열 F(5)를 단순 재귀로 계산하면 다음과 같은 호출 트리가 생성됩니다:
1
2
3
4
5
6
7
8
9
F(5)
├── F(4)
│ ├── F(3)
│ │ ├── F(2)
│ │ └── F(1)
│ └── F(2)
└── F(3)
├── F(2)
└── F(1)
위 트리를 보면 F(3)이 2번, F(2)가 3번 계산됩니다.
단 5번째 값을 구하는데도 같은 계산이 반복되는 것입니다.
n이 커질수록 이러한 중복 계산은 기하급수적으로 증가합니다.
F(50)을 계산하려면 수십억 번의 함수 호출이 필요하고,
F(100)은 현실적으로 계산이 불가능합니다.
동적 계획법은 한 번 계산한 결과를 저장하여 같은 문제를 다시 만났을 때 저장된 값을 즉시 반환함으로써,
이러한 중복 계산을 제거합니다.
최적 부분 구조와 중복 부분 문제
동적 계획법이 적용 가능한 문제는 두 가지 특징을 가집니다.
1. 최적 부분 구조
큰 문제의 최적 해가 작은 부분 문제의 최적 해로 구성되는 성질입니다.
예를 들어, 출발지 A에서 목적지 C까지의 최단 경로를 구한다고 가정해봅시다.
만약 최단 경로가 A → B → C라면,
A에서 B까지의 경로 역시 A에서 B로 가는 최단 경로여야 합니다.
만약 A에서 B로 가는 더 짧은 경로가 존재한다면,
그 경로를 사용하여 A → C의 경로를 더 짧게 만들 수 있기 때문입니다.
이처럼 전체 문제의 최적 해가 부분 문제의 최적 해를 포함하는 구조를 최적 부분 구조라고 합니다.
2. 중복 부분 문제
동일한 부분 문제가 여러 번 반복적으로 계산되는 성질입니다.
피보나치 수열에서 F(n)을 계산할 때 F(n-1)과 F(n-2)를 구해야 하고,
F(n-1)을 계산할 때 다시 F(n-2)와 F(n-3)을 구해야 하는데,
이 과정에서 F(n-2)가 중복 계산됩니다.
단순 재귀는 이러한 중복을 매번 처음부터 다시 계산하지만,
동적 계획법은 한 번 계산한 값을 저장하여 재사용합니다.
동적 계획법의 구현 방식
동적 계획법을 구현하는 방법에는 크게 두 가지가 있습니다:
Top-down (하향식, 메모이제이션)과 Bottom-up (상향식, 타뷸레이션)입니다.
1. Top-down 방식 (메모이제이션)
Top-down 방식은 재귀 호출을 사용하되, 계산 결과를 저장하여 중복 계산을 방지하는 방식입니다.
큰 문제부터 시작하여 필요한 부분 문제를 재귀적으로 호출하며,
한 번 계산한 결과는 메모리에 저장(메모이제이션)하여 같은 문제를 다시 만나면 저장된 값을 반환합니다.
피보나치 수열 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
vector<int> dp(100, -1); // -1로 초기화 (아직 계산되지 않음을 의미)
int fib(int n) {
// 기저 조건
if (n <= 1) return n;
// 이미 계산된 값이 있으면 반환 (메모이제이션)
if (dp[n] != -1) return dp[n];
// 계산 후 저장
return dp[n] = fib(n - 1) + fib(n - 2);
}
int main() {
int n;
cin >> n;
cout << fib(n) << "\n";
return 0;
}
Top-down 방식의 특징
장점:
- 재귀적 구조로 직관적이고 이해하기 쉬움
- 필요한 부분 문제만 계산 (불필요한 계산 생략)
- 점화식을 그대로 코드로 옮기기 쉬움
단점:
- 재귀 호출로 인한 함수 호출 오버헤드 존재
- 재귀 깊이가 깊으면 스택 오버플로우 위험
- 일반적으로 Bottom-up보다 약간 느림
2. Bottom-up 방식 (타뷸레이션)
Bottom-up 방식은 작은 부분 문제부터 순서대로 계산하여 큰 문제를 해결하는 방식입니다.
가장 작은 문제부터 시작하여 반복문을 통해 순차적으로 계산하며,
각 단계의 결과를 테이블(배열)에 저장합니다.
피보나치 수열 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
// dp 테이블 초기화
vector<int> dp(n + 1);
// 기저 조건 설정
dp[0] = 0;
dp[1] = 1;
// 작은 문제부터 순서대로 계산
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
// 최종 답 출력
cout << dp[n] << "\n";
return 0;
}
Bottom-up 방식의 특징
장점:
- 반복문 사용으로 함수 호출 오버헤드 없음
- 일반적으로 Top-down보다 빠름
- 스택 오버플로우 위험 없음
- 공간 최적화가 용이함
단점:
- 필요하지 않은 부분 문제도 모두 계산할 수 있음
- 계산 순서를 명확히 파악해야 함
- 점화식이 복잡한 경우 구현이 어려울 수 있음
Top-down vs Bottom-up 비교
| 구분 | Top-down (메모이제이션) | Bottom-up (타뷸레이션) |
|---|---|---|
| 구현 방식 | 재귀 + 메모이제이션 | 반복문 + 테이블 |
| 계산 방향 | 큰 문제 → 작은 문제 | 작은 문제 → 큰 문제 |
| 직관성 | 높음 (점화식과 유사) | 중간 |
| 속도 | 상대적으로 느림 | 상대적으로 빠름 |
| 공간 최적화 | 어려움 | 용이함 |
| 부분 문제 계산 | 필요한 것만 | 모두 계산 |
동적 계획법 설계 과정
동적 계획법 문제를 해결하기 위해서는 체계적인 접근이 필요합니다.
다음 단계를 따라 문제를 분석하고 해결할 수 있습니다.
1. 최적 부분 구조 확인
문제가 부분 문제의 최적 해로부터 구성되는지 확인합니다.
전체 문제의 해가 부분 문제의 해를 결합하여 구할 수 있는지 판단해야 합니다.
만약 최적 부분 구조가 없다면, 동적 계획법을 적용할 수 없습니다.
예를 들어, “A에서 C로 가는 최단 경로”는 “A에서 B로 가는 최단 경로”와 “B에서 C로 가는 최단 경로”로 나눌 수 있습니다.
2. 점화식 유도
부분 문제 간의 관계를 수식으로 표현합니다.
\(dp[i]\)가 무엇을 의미하는지 명확히 정의하고,
이를 \(dp[i-1]\), \(dp[i-2]\) 등 이전 값들로 표현하는 식을 찾습니다.
3. 기저 조건 설정
가장 작은 부분 문제의 해를 정의합니다.
재귀가 멈추는 조건이자, 모든 계산의 시작점이 되는 값입니다.
4. 계산 순서 결정
부분 문제를 어떤 순서로 계산할지 결정합니다.
Bottom-up 방식의 경우, \(dp[i]\)를 계산할 때 필요한 값들이 모두 계산되어 있어야 합니다.
5. 구현
Top-down 또는 Bottom-up 방식으로 구현합니다.
동적 계획법의 활용
동적 계획법은 다양한 최적화 문제에 적용됩니다.
대표적인 활용 사례를 구체적인 구현과 함께 살펴보겠습니다.
1. 정수 삼각형 문제
정수 삼각형은 삼각형의 맨 위에서 시작하여 아래로 내려가며 경로 상의 숫자 합이 최대가 되도록 하는 문제입니다.
각 단계에서 대각선 방향으로 인접한 두 숫자 중 하나를 선택할 수 있습니다.
관련 문제:
문제 분석
삼각형의 \(i\)번째 줄, \(j\)번째 위치에 도달하는 최대 합은,
이전 줄의 인접한 위치들 중 더 큰 값을 선택하고 현재 위치의 값을 더한 것입니다.
점화식:
\[dp[i][j] = \max(dp[i-1][j-1], dp[i-1][j]) + \text{triangle}[i][j]\]여기서 \(dp[i][j]\)는 \((i, j)\) 위치까지의 최대 합을 의미합니다.
기저 조건: \(dp[0][0] = \text{triangle}[0][0]\)
구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
// 삼각형 입력 및 DP 테이블 초기화
vector<vector<int>> tri(n);
vector<vector<int>> dp(n);
for (int i = 0; i < n; i++) {
tri[i].resize(i + 1);
dp[i].resize(i + 1);
for (int j = 0; j <= i; j++) {
cin >> tri[i][j];
}
}
// 기저 조건: 맨 위 값
dp[0][0] = tri[0][0];
// Bottom-up으로 각 위치까지의 최대 합 계산
for (int i = 1; i < n; i++) {
for (int j = 0; j <= i; j++) {
if (j == 0) {
// 맨 왼쪽: 위에서만 올 수 있음
dp[i][j] = dp[i-1][j] + tri[i][j];
} else if (j == i) {
// 맨 오른쪽: 왼쪽 대각선에서만 올 수 있음
dp[i][j] = dp[i-1][j-1] + tri[i][j];
} else {
// 중간: 두 대각선 중 큰 값 선택
dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + tri[i][j];
}
}
}
// 마지막 줄에서 최댓값 찾기
int maxSum = *max_element(dp[n-1].begin(), dp[n-1].end());
cout << maxSum << "\n";
return 0;
}
시간 복잡도: \(O(n^2)\) (\(n\)은 삼각형의 높이)
공간 복잡도: \(O(n^2)\)
2. 최장 증가 부분 수열 (LIS, Longest Increasing Subsequence)
주어진 수열에서 오름차순으로 증가하는 부분 수열 중 가장 긴 것의 길이를 찾는 문제입니다.
예를 들어, 수열 [10, 20, 10, 30, 20, 50]에서 LIS는 [10, 20, 30, 50]이며 길이는 4입니다.
문제 분석
각 원소를 끝으로 하는 증가 부분 수열의 최대 길이를 저장합니다.
\(dp[i]\)는 \(arr[i]\)로 끝나는 LIS의 길이를 의미하며,
\(i\)보다 앞에 있으면서 값이 작은 모든 \(j\)에 대해 \(dp[j] + 1\) 중 최댓값을 선택합니다.
점화식:
\[dp[i] = \max(dp[j] + 1) \quad \text{for all } j < i \text{ where } arr[j] < arr[i]\]기저 조건: \(dp[i] = 1 \quad \text{(각 원소 자체가 길이 1인 증가 수열)}\)
구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> arr(n);
vector<int> dp(n, 1); // 기저 조건: 각 원소는 최소 길이 1
// 수열 입력
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
// 각 위치에서 끝나는 LIS 길이 계산
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
// arr[j]가 arr[i]보다 작으면 arr[i]를 뒤에 추가 가능
if (arr[j] < arr[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
// 전체 수열에서 LIS의 최대 길이 찾기
int lis = *max_element(dp.begin(), dp.end());
cout << lis << "\n";
return 0;
}
시간 복잡도: \(O(n^2)\)
공간 복잡도: \(O(n)\)
참고: 이진 탐색을 사용하면 \(O(n \log n)\)으로 최적화할 수 있습니다.
3. 배낭 문제 (0/1 Knapsack Problem)
무게 제한이 있는 배낭에 물건을 담아 최대 가치를 얻는 문제입니다.
각 물건은 담거나 담지 않거나 둘 중 하나를 선택해야 하며 (0/1),
물건을 쪼개서 담을 수는 없습니다.
문제 분석
\(i\)번째 물건까지 고려했을 때, 무게 \(w\)까지 담을 수 있는 최대 가치를 구합니다.
각 물건에 대해 담는 경우와 담지 않는 경우 중 더 큰 가치를 선택합니다.
점화식:
\[dp[i][w] = \max(dp[i-1][w], \quad dp[i-1][w-\text{weight}[i]] + \text{value}[i])\]- \(dp[i-1][w]\): \(i\)번째 물건을 담지 않는 경우
- \(dp[i-1][w-\text{weight}[i]] + \text{value}[i]\): \(i\)번째 물건을 담는 경우
기저 조건: \(dp[0][w] = 0 \quad \text{(물건이 0개일 때)}\)
\[dp[i][0] = 0 \quad \text{(배낭 용량이 0일 때)}\]구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, maxWeight;
cin >> n >> maxWeight;
vector<int> weight(n + 1);
vector<int> value(n + 1);
// DP 테이블 초기화 (기저 조건: 0으로 초기화)
vector<vector<int>> dp(n + 1, vector<int>(maxWeight + 1, 0));
// 물건 정보 입력
for (int i = 1; i <= n; i++) {
cin >> weight[i] >> value[i];
}
// DP 테이블 채우기
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= maxWeight; w++) {
if (weight[i] <= w) {
// i번째 물건을 담을 수 있는 경우
// 담는 것과 담지 않는 것 중 최댓값 선택
dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i]);
} else {
// i번째 물건을 담을 수 없는 경우 (무게 초과)
dp[i][w] = dp[i-1][w];
}
}
}
// 최종 답: n개 물건, maxWeight 용량일 때의 최대 가치
cout << dp[n][maxWeight] << "\n";
return 0;
}
시간 복잡도: \(O(n \times W)\) (\(n\)은 물건 개수, \(W\)는 배낭 용량)
공간 복잡도: \(O(n \times W)\)
공간 최적화: 1차원 배열만 사용하여 \(O(W)\)로 줄일 수 있습니다.
동적 계획법의 효율성
동적 계획법을 적용하면 지수 시간 복잡도의 문제를 다항 시간으로 해결할 수 있습니다.
시간 복잡도 비교
| 문제 | 단순 재귀 | 동적 계획법 | 개선 효과 |
|---|---|---|---|
| 피보나치 수열 | \(O(2^n)\) | \(O(n)\) | 지수 → 선형 |
| 정수 삼각형 | \(O(2^n)\) | \(O(n^2)\) | 지수 → 이차 |
| LIS | \(O(2^n)\) | \(O(n^2)\) | 지수 → 이차 |
| 배낭 문제 | \(O(2^n)\) | \(O(n \times W)\) | 지수 → 의사다항 |
단순 재귀로는 \(n = 40\)만 되어도 수십억 번의 연산이 필요하지만,
동적 계획법을 사용하면 수천 번의 연산으로 해결할 수 있습니다.
공간 최적화 기법
동적 계획법에서 시간 복잡도 못지않게 공간 복잡도도 중요합니다.
메모리 제한이 있는 경우 공간을 최적화하는 기법을 사용할 수 있습니다.
1. 필요한 값만 유지하기
이전 단계의 결과만 필요한 경우, 전체 테이블 대신 최근 몇 개의 값만 저장할 수 있습니다.
피보나치 수열 공간 최적화
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 prev2 = 0, prev1 = 1;
int current;
for (int i = 2; i <= n; i++) {
current = prev1 + prev2;
// 값을 앞으로 이동
prev2 = prev1;
prev1 = current;
}
return current;
}
공간 복잡도: \(O(n)\) → \(O(1)\)
2. 배낭 문제 1차원 최적화
배낭 문제에서 2차원 배열 대신 1차원 배열만 사용할 수 있습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int main() {
int n, maxWeight;
cin >> n >> maxWeight;
vector<int> weight(n + 1);
vector<int> value(n + 1);
vector<int> dp(maxWeight + 1, 0); // 1차원 배열
for (int i = 1; i <= n; i++) {
cin >> weight[i] >> value[i];
}
// 뒤에서부터 계산하여 이전 값 보존
for (int i = 1; i <= n; i++) {
for (int w = maxWeight; w >= weight[i]; w--) {
dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
}
}
cout << dp[maxWeight] << "\n";
return 0;
}
공간 복잡도: \(O(n \times W)\) → \(O(W)\)
공간 최적화 시 주의사항
공간 최적화를 적용하면 메모리는 절약되지만, 다음과 같은 제약이 생길 수 있습니다:
- 경로 복원이 어려움: 최적 해의 값만 구할 수 있고, 어떤 선택을 했는지 역추적이 어렵습니다.
- 특정 패턴에만 적용 가능: 모든 동적 계획법 문제에 적용할 수 있는 것은 아닙니다.
마무리
동적 계획법은 큰 문제를 작은 부분 문제로 나누어 해결하고,
그 결과를 저장하여 중복 계산을 방지하는 알고리즘 설계 기법입니다.
최적 부분 구조와 중복 부분 문제라는 두 가지 조건을 만족하는 문제에 적용할 수 있으며,
지수 시간 복잡도의 문제를 다항 시간으로 해결할 수 있습니다.
구현 방식은 Top-down (메모이제이션)과 Bottom-up (타뷸레이션) 두 가지가 있으며,
피보나치 수열, 정수 삼각형, 최장 증가 부분 수열, 배낭 문제 등 다양한 최적화 문제에 활용됩니다.
참고 : 피보나치 수열 (Fibonacci Sequence) - soo:bak
참고 : 조합(Combination)의 원리와 구현 - soo:bak
관련문제