동적 계획법 (이하 DP)은 큰 문제를 분할하여 부분 문제들로 만든 다음, 각 부분 문제의 답으로부터 전체 문제의 답을 이끌어내는 방식의 알고리즘입니다.
그런데 이 정의 어디에서 본 적이 있는 것 같습니다.
그렇습니다. DP도 일종의 분할 정복 알고리즘이라고 할 수 있습니다. 다만 일반적인 분할 정복 알고리즘과는 다른 점이 있습니다.
그것은 바로 DP는 부분 문제들이 독립적이지 않다는 점입니다.
다시 말하면, DP는 서로 겹치는 부분 문제가 존재할 때 쓸 수 있는 알고리즘입니다.
문제를 나눠서 푸는데 어떻게 부분 문제들이 겹칠 수 있을까요? 가장 쉬운 예를 살펴봅시다.
https://www.acmicpc.net/problem/2748
2748번: 피보나치 수 2
문제 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 n이 주어졌을 때, n번째 피보나치 수를
www.acmicpc.net
피보나치 수를 구해봅시다.
물론 우리는 \(n\)번째 피보나치 수를 \(O(n)\)에 구하는 법을 이미 알고 있습니다.
하지만, 이해를 위해 이번엔 분할해서 재귀를 이용해서 한번 풀어보도록 합시다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
#include <iostream>
#include <algorithm>
using namespace std;
long long fib(int n)
{
if (n == 0) return 0;
if (n == 1) return 1;
else return fib(n - 1) + fib(n - 2);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n; cin >> n;
cout << fib(n);
}
|
\(n\)번째 피보나치 수는 \(n-1\)번째 피보나치 수와 \(n-2\)번째 피보나치 수의 합이므로, 문제를 2개의 작은 문제로 분할해서 풀 수 있습니다. 이 코드를 제출 하면 어떻게 될까요?
그렇습니다. 이 코드는 너무 느리게 동작합니다. 실제로 이 코드를 실행시켜서 입력으로 50정도만 넣어도, 답을 내놓기까지 억겁의 시간이 걸리게 됩니다. 왜 이렇게 될까요?
\(n=4\)일 때 어떤 부분 문제들을 해결하게 되는지 살펴보도록 합시다.
\(n=0\)또는 \(n=1\)일 때 재귀를 멈추도록 했으므로, \(Fib(4)\)를 호출 하면 1번의 \(Fib(3)\), 2번의 \(Fib(2)\), 3번의 \(Fib(1)\), 2번의 \(Fib(0)\)을 계산하게 됩니다.
조금 문제가 있어 보입니다. 각 \(Fib(x)\)를 계산하는건 딱 1번이면 될텐데, 쓸데없이 같은 값을 여러번 계산하고 있습니다.
이 값들을 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
|
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
long long dp[91];
long long fib(int n)
{
if (dp[n] != -1) return dp[n];
// dp[n]이 -1이 아니라면 (이미 계산되어 있다면) 그 값을 그대로 반환한다.
// 그렇지 않다면, dp[n]을 계산해서 채워넣는다.
if (n == 0) return dp[n] = 0;
if (n == 1) return dp[n] = 1;
else return dp[n] = fib(n - 1) + fib(n - 2);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
memset(dp, -1, sizeof dp); // dp[i]를 모두 -1로 초기화한다.
int n; cin >> n;
cout << fib(n);
}
|
이렇게 하면 이번엔 여러번 계산하는 일 없이 모든 \(Fib(i)\)값을 한 번씩만 계산하게 되므로, 무난하게 정답을 받게 됩니다.
이렇듯 문제를 부분 문제들로 분할해서 푼다는 분할정복의 개념에, 한 번 구한 값은 저장해놓는 "Memoization"의 개념을 합한 것이 DP입니다.
기초적인 DP의 시간복잡도는 다음과 같습니다.
(DP테이블의 크기) \(\times\) (DP 테이블 한칸을 계산하는데 필요한 부분 문제의 수)
위의 피보나치 문제의 경우, DP테이블의 크기는 \(n+1\)이고, 한 칸을 계산하는데 최대 2개의 부분 문제를 계산해야 하므로 총 시간복잡도는 \(O(n)\)입니다.
하지만 일반적으로 피보나치 수를 계산 할 때, 굳이 이렇게 복잡한 코드를 짜지는 않습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
long long dp[91];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
dp[0] = 0, dp[1] = 1;
for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
cout << dp[n];
}
|
\(DP(n)\)보다 \(DP(n-1)\)이 먼저 계산되어야 함이 자명하기 때문에, 위의 코드도 모든 \(Fib(i)\)값을 단 한번씩만 계산해서 \(Fib(n)\)값을 구하는 DP 코드라고 볼 수 있습니다.
DP 코드를 작성할 때, 전자와 같은 방식을 탑다운(Top-Down) DP, 후자와 같은 방식을 바텀업(Bottom-Up) DP라고 합니다.
둘 중 어떤 것을 사용할지는 본인의 선택입니다.
하지만 바텀업 DP를 이용하기 위해서는 DP 테이블의 각 칸 사이의 재귀적 관계로 이루어진 그래프의 DAG에 대한 위상 정렬의 순서대로 테이블을 채워야 하기 때문에, 일반적으로 탑다운 형식의 DP를 사용하는 것이 더 마음 편하게 코드를 짤 수 있습니다.
설명은 여기까지 하고, 실제 기초적인 DP문제들을 살펴보도록 합시다.
https://www.acmicpc.net/problem/2294
2294번: 동전 2
첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.
www.acmicpc.net
\(n\)가지 종류의 동전이 있습니다. 이 동전들로 \(k\)원을 만드려고 하는데, 동전 개수를 최소로 하려고 합니다.
DP식을 다음과 같이 정의해 봅시다.
\(DP(i,j) :\) i번째 동전부터 마지막 동전까지 사용했을 때, j원을 만드는데 필요한 동전 수의 최소값
현재 상황에서는 i번째 동전을 사용해서 k원에서 까거나, 또는 i번째 동전을 사용하는 것을 그만두고 i+1번째 동전부터 사용할 수 있습니다.
그럼 다음과 같은 점화식이 유도됩니다.
\(DP(i,j) = min(DP(i, j-coin_i)+1, DP(i+1, j))\) (\(coin_i :\) i번째 동전의 가치)
함수에 이 식을 그대로 넣으면 됩니다.
DP테이블의 크기는 \(nm\)이고, 각 상태를 계산하는데 최대 2개의 부분 문제를 계산해야 하므로 시간복잡도는 \(O(nm)\)입니다.
|
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
45
46
47
|
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 987654321; // 불가능하다는 것을 표현한다.
int n, k;
int coin[101];
int dp[101][10001];
int solve(int i, int j)
{
if (i == n) // 기저 조건
{
if (j == 0)
return 0; // 동전을 다 써서 정확히 k원을 만들었다.
else
return INF; // 동전을 다 썼지만 k원을 만들지 못했다.
}
int& ret = dp[i][j];
if (ret != -1) return ret; // 이미 계산된 값이라면 바로 return 한다.
ret = INF;
if (j >= coin[i])
ret = min(ret, solve(i, j - coin[i]) + 1); // 이 동전을 한번 사용한다.
ret = min(ret, solve(i + 1, j)); // 이 동전을 쓰지 않는다.
return ret;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
memset(dp, -1, sizeof dp);
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> coin[i];
int ans = solve(0, k);
if (ans == INF) ans = -1;
cout << ans;
}
|
https://www.acmicpc.net/problem/12865
12865번: 평범한 배낭
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 입력으로 주어지는 모든 수는 정수이다.
www.acmicpc.net
\(N\)개의 물건이 있습니다.
이 물건은 각각 무게 \(W\)와 가치 \(V\)를 가지는데, 최대 \(K\)의 무게를 가지면서 가치의 합이 최대가 되도록 물건을 골라야 합니다.
'배낭 문제'로 유명한 문제입니다.
DP식을 다음과 같이 정의해 봅시다.
\(DP(i,j) :\) i번째부터 마지막 물건을 이용할 수 있고, 더 담을 수 있는 무게가 j일때 얻을 수 있는 가치의 최댓값
역시 현재 상황에서 i번째 물건을 챙기고 \(V_i\)의 가치를 얻거나, 챙기지 않을 수 있습니다.
그럼 다음과 같은 점화식이 유도됩니다.
\(DP(i,j) = max(DP(i+1, j-W_i)+V_i, DP(i+1,j))\)
시간복잡도는 \(O(NK)\)입니다.
|
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
|
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n, k;
int w[101];
int v[1001];
int dp[101][100001];
int solve(int i, int j)
{
if (i == n) return 0; // 기저 조건
int& ret = dp[i][j];
if (ret != -1) return ret; // 이미 계산된 값이라면 return 한다.
ret = 0;
if (j >= w[i])
ret = max(ret, solve(i + 1, j - w[i]) + v[i]);
// 이 물건을 챙기고 가치 v[i]를 얻는다.
ret = max(ret, solve(i + 1, j));
// 이 물건을 챙기지 않는다.
return ret;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
memset(dp, -1, sizeof dp);
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> w[i] >> v[i];
cout << solve(0, k);
}
|
https://www.acmicpc.net/problem/11053
11053번: 가장 긴 증가하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
www.acmicpc.net
길이 \(N\)의 수열 \(A\)가 주어집니다.
이 수열의 가장 긴 증가하는 부분 수열을 구해야 합니다.
역시 "Longest Increasing Subsequence", "LIS"로 유명한 문제입니다.
역시 다음과 같은 DP식을 정의해 봅시다.
\(DP(i) :\) i번째 원소부터 시작하는 가장 긴 증가하는 부분 수열의 길이
어떤 원소 \(A_i\)부터 시작하는 LIS를 만들기 위해서는, 다음 원소로 \(A_i\)보다 큰 원소를 선택해야 합니다.
이 원소를 \(A_j\)라고 합시다. \(DP(j)\)에 1을 더하면 \(DP(i)\)의 가능한 값중 하나를 계산할 수 있게 되고, 이를 가능한 모든 \(j\)에 대해 계산해서 최댓값을 취하면 됩니다.
그러므로, 다음과 같은 점화식을 유도할 수 있습니다.
\(DP(i) = max_{j>i}(DP(j)+1)\), (\(A_j > A_i\))
DP테이블의 크기는 \(N\)이고, 각 상태를 계산하는데 최대 \(N\)개의 부분 문제를 계산해야 합니다.
따라서 총 시간복잡도는 \(O(N^2)\)입니다.
|
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
|
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
int a[1001];
int dp[1001];
int solve(int i)
{
int& ret = dp[i];
if (ret != -1) return ret;
ret = 1;
for (int j = i + 1; j < n; j++)
{
if (a[i] < a[j])
ret = max(ret, solve(j) + 1);
// a[i]보다 a[j]가 크다면, DP(j)+1을 계산한 다음 DP(i)를 갱신한다.
}
return ret;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
memset(dp, -1, sizeof dp);
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
int ans = 0;
for (int i = 0; i < n; i++)
ans = max(ans, solve(i));
// a[i]로 시작하는 LIS의 길이 중 최댓값을 저장한다.
cout << ans;
}
|
DP식을 꼭 문제에서 구하려고 하는 값에 대해서 정의할 필요는 없습니다. 다음 문제를 봅시다.
https://www.acmicpc.net/problem/11659
11659번: 구간 합 구하기 4
첫째 줄에 수의 개수 N (1 ≤ N ≤ 100,000), 합을 구해야 하는 횟수 M (1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.
www.acmicpc.net
수 \(N\)개가 주어지고, \(i\)번째 수부터 \(j\)번째 수까지 합을 구해야 합니다.
합을 최대 \(M\)번 구해야 하므로, 일일히 수를 더하는 알고리즘은 \(O(NM)\)으로 시간안에 들어오지 못합니다.
지금까지 했던 대로 DP식을 한번 정의해 봅시다.
\(DP(i,j) :\) i번째 수부터 j번째 수까지의 합
그런데 뭔가 이상합니다. \(i\)와 \(j\)는 둘다 최대 \(N\)인데, \(N\times N\)크기의 DP테이블을 만들 수 있을까요?
조금 다른 방법으로 접근해야 합니다. DP식을 다음과 같이 다시 정의해 봅시다.
\(DP(i) :\) 1번째 수부터 i번째 수까지의 합
이 DP테이블을 미리 채워두고 나면, i번째 수부터 j번째 수까지의 합은 다음과 같은 식으로 쉽게 계산할 수 있습니다.
\(DP(j) - DP(i-1)\)
이렇게 첫번째 원소부터의 부분합을 전처리로 저장해 놓으면 고정된 배열에서의 구간합을 \(O(1)\)에 구할 수 있습니다.
이걸 계산하는데 \(DP(i) = DP(i-1) + A_i\) 점화식을 이용해 탑다운으로 구할 수도 있겠지만,
그냥 앞에서부터 차례대로 바텀업으로 계산하는 것이 조금 더 직관적일것 같습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n, m;
int a[100001];
int dp[100001];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) dp[i] = dp[i - 1] + a[i]; // 바텀업 DP
while (m--)
{
int i, j; cin >> i >> j;
cout << dp[j] - dp[i - 1] << '\n';
}
}
|
1부터 시작하는 인덱스를 사용하면 \(DP[i-1]\)을 예외 처리 없이 쉽게 구할 수 있습니다.
이상으로 기초적인 DP에 대한 설명을 마칩니다.
DP는 가장 흔한 문제 유형중 하나이고, 어느정도 공부하고 나면 풀 수 있는 문제가 정말 많아진다는 것을 느낄 수 있게 됩니다.
하지만 DP는 가장 마스터하기 어려운 알고리즘이기도 합니다.
입문부터 PS를 그만두는 그 순간까지 DP는 꾸준히 여러분을 괴롭힐 것입니다.
제 그룹의 문제집에서 연습 문제들을 관리하고 있습니다.
문제집의 문제들을 보고 싶으시다면, 가입 신청을 해 주세요.
https://www.acmicpc.net/group/7712
ANZ1217
무슨 내용을 넣어야 좋을까요?
www.acmicpc.net
'알고리즘 > DP' 카테고리의 다른 글
| Divide and Conquer Optimization (0) | 2021.11.08 |
|---|---|
| Convex Hull Trick (1) | 2021.11.07 |
| 기초 DP 최적화 (0) | 2021.07.13 |
| 비트마스킹 DP (0) | 2020.06.07 |
