Dynamic Programming
프로그래밍을 통한 문제 해결은 결국 탐색 공간에서 원하는 해를 찾아내는 과정이다. 알고리즘의 측면에서 우리는 어떻게 하면 적은 연산을 통해 해를 도출할 수 있을지 고민하는 것이 중요하다. 동적 계획법 또한 해를 탐색하는 전략의 일종으로 해를 구하는 과정에서 불필요한 연산을 최소화하기 위해 고안된 기법이다. 동적 계획법은 문제를 여러 개의 부분 문제로 나누어 각 부분 문제에 대한 결과를 구한 다음, 그 결과들을 이용해 해결하고자 하는 원래의 문제를 푸는 최적화 기법의 일종이다. 즉, 큰 문제를 여러 부분 문제로 나눈 후, 부분 문제들의 답을 각각 구하고 그 결과값을 바탕으로 큰 문제의 결과값을 구하는 방법이다. 이렇게 말하면 쉽게 와닿지 않을 뿐더러 기법에 대한 정의가 굉장히 포괄적이다. 이는 곧 해당 알고리즘의 솔루션이 정형화되어 있지 않다는 것을 의미하며 기법적인 측면이 강하다는 것을 나타낸다. DP의 가장 대표적인 예시로 피보나치 수열이 존재한다.
피보나치 수열의 점화식은 다음과 같이 나타난다. 이는 n번째 항의 값이 이전 번째 항과 그 전 번째 항의 합으로 나타내어짐을 알 수 있다.
$F_{1}=0, F_{2}=1$
$F_{N} = F_{N-1} + F_{N-2}$
이 수열의 항들을 나열해보면 $0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55....$로 나타내어진다. 이 수열의 N번째 항을 구하는 코드를 재귀적으로 구현해보면 다음과 같다.
|
1
2
3
4
5
6
|
int f(int n)
{
if(n==0) return 0;
if(n==1) return 1;
return f(n-1)+f(n-2);
}
|
cs |
반복문을 통한 단순 탐색의 측면에서 생각해보았을 때, 우리는 $N$번째 항을 구하기 위해 1번째 항부터 차례대로 구하는 과정을 통해 해를 구할 수 있으므로 연산 횟수가 최소 $N$번이 될 수 있다는 것을 생각할 수 있다. 하지만 아래와 같이 함수 호출이 불필요하게 많이 발생함을 알 수 있으므로 이를 개선해야 한다. 이러한 불필요성을 개선하는 아이디어가 동적 계획법이다.
위 재귀 함수 기반의 탐색은 하나의 함수에서 2개의 재귀 함수가 발생하므로 전체 함수 호출 횟수는 $N$에 대해 지수적으로 증가할 것이다. 위 과정에서 불필요한 과정이 존재하는데, 이는 중복된 연산이다. 만약 우리가 3번째 피보나치 수를 구했다면 이 값을 다시 계산할 필요가 없다. 하지만 위 알고리즘은 $f(3)$을 한 번만 호출하지 않고 계속해서 호출하여 불필요한 계산량을 늘리고 있다. 따라서 $f(3)$의 값을 저장하여 다시 계산하는 것을 막아야 한다. 아래를 통해 해당 기법을 설명한다.
$F_{4}$ 를 구하려면 $F_{3}$ 값과 $F_{2}$ 값이 필요하다.
$F_{3}$ 값을 구하려면 $F_{2}$ 값과 $F_{1}$ 값이 필요하다.
$F_{1}$ 값은 1이고 $F_{2}$ 값은 $F_{0} + F_{1} = 1$이다.
$F_{4} = F_{3} + F_{2}$인데 우리는 $F_{3}$를 구하는 과정(탐색 공간 트리에서의 왼쪽 노드)에서 이미 $F_{2}$를 구했으므로 굳이 $F_{2}$를(탐색 공간 트리에서 오른쪽 노드) 다시 계산할 필요가 없다. 즉, 이미 계산한 항의 결과들(원 문제에서 분할되어 만들어진 소문제들)에 대해서는 다시 계산할 필요가 없으므로, 이미 계산한 값을 배열에 기록해 두어 중복 계산을 하지 않도록 해야한다. 이 기법을 동적 계획법의 핵심이 되는 메모이제이션(Memoization)이라고 한다.
즉, Dynamic Programming을 피보나치 예시에 맞추어 설명하면, 구하고자 했던 해($f(n)$)를 구하기 위해 문제를 여러 부분 문제로 나누어($f(n-1), f(n-2), ...$), 그들의 해를 계산한 후, 이를 바탕으로 해를 구하는 방법이다. 이 때 Partial Problem의 해를 중복해서 계산하는 것을 막기 위해 Memoization을 적용하여 불필요한 계산을 하지 않게 된 것이다.
추후에 다룰 문제 해결 기법 중 하나인 Divide and Conquer(분할 정복) 또한 문제를 여러 Partial Problems로 분할하는 방식을 취한다. 추후 서술할 두 방식의 가장 큰 차이점 중 하나는, Divide and Conquer 기법에서 발생하는 분할된 부분 문제들은 공통된 범위를 가지고 있지 않다. ( 피보나치 문제에서 $f(4)$를 구하기 위해 분할한 두 부분 문제인 $f(3)$, $f(2)$는 $f(2)$라는 공통된 부분 문제를 포함하고 있었다. ) 따라서 DnC 기법은 메모이제이션을 적용하지 않고 문제를 분할하게 되고( 일반적으로 구간을 Left/Right로 분할하여 탐색한다. ) Dynamic Programming은 Memoization 기반의 분할 탐색 방식을 취한다.
아래 코드는 Memoization을 구현한 코드로, 시간복잡도가 $O(N)$이다.
|
1
2
3
4
5
6
7
8
9
10
|
int memo[101];
int f(int n)
{
if(n==0) return 0;
if(n==1) return 1;
//이미 계산한 값이 저장되어 있으면 그 값을 리턴한다.(다시 계산할 필요X)
if(memo[n]!=0) return memo[n];
return memo[n]=f(n-1)+f(n-2);
}
|
cs |
또한 이것을 재귀함수가 아닌 반복문으로 구현할 수도 있다.
|
1
2
3
4
5
6
|
fibo[0]=0;
fibo[1]=1;
for(int i=2; i<=N; i++){
fibo[i]=fibo[i-1]+fibo[i-2];
}
|
cs |
이 두 코드는 모두 시간복잡도가 $O(N)$으로 초기의 Bruteforce 기법보다 훨씬 빠른 속도로 동작하게 된다. 동적계획법의 기본적인 원리는 Memoization에 기반한 분할 기법이지만, 구현 방식은 크게 2가지로 나뉜다. ( 실제로 동작하는 과정은 일치한다. ) 이들은 탐색 방법에 따라 구분되는데, 원 문제를 해결하기 위해 원 문제를 Partial Problems로 분할하며 탐색을 진행하는지, 혹은 Partial Problems를 먼저 계산해나가면서 마지막에 원 문제의 해를 구하는지의 차이이다. 조금 더 간단히 설명하면, 재귀호출를 이용하여 큰 문제에서 작은 문제로 나누는 방법을 탑다운(Top-Down)이라고 부르고, 반복문을 사용하여 가장 작은 문제(Initial Values)에서 점점 큰 문제로 탐색해 나가는 방법을 바텀업(Bottom-Up)이라고 부른다. 위 코드에서 첫 번째 방식이 Top-Down, 두 번째가 Bottom-Up이다. 탑다운은 점화식과 코드를 직관적으로 이해하기 쉽고, 바텀업은 탑다운보다 시간, 메모리를 절약할 수 있다. ( 재귀 깊이에 대해 걱정하지 않아도 된다. )
일반적으로 점화식 설계를 연습하다보면, Top-Down 방식이 더 익숙할 것이지만, Bottom-Up 기반의 최적화 기법이 여럿 존재하니 두 방식의 구현 모두 연습하는 것이 중요하다.
동적 계획법 문제를 해결하는 과정에서 가장 중요한 요소 중 하나가 바로 점화식 설계이다. 점화식을 알고 있다면 Fibonacci 문제에서 구현했던 것처럼 점화식 + Memoization으로 간단하게 구현할 수 있기 때문에 문제에서 점화식을 유도해내는 과정이 필수적이다.
1. 점화식 항의 의미를 정의하기 ( ex. $a_{n}$ : n개의 타일을 채우는 경우의 수 )
2. 점화식 유도하기 ( ex. $a_{n} = a_{n-1} + 2a_{n-2}$ )
3. 초항 구하기 ( ex. $a_{1} = 1, a_{2} = 2$ )
4. Top-Down or Bottom-Up으로 구현하기
Problems
길이가 $N$인 수열을 만들어야하는데 선택할 수 있는 것은 '1' 또는 '00'이다.
$F_{n}$을 길이가 $N$인 수열을 만들 수 있는 가짓수라고 정의한다면
'1'을 선택했을 때는 $F_{N-1}$의 값이 필요하고('1'을 선택하면 남은 수열의 길이는 n-1이기 때문)
'00'을 선택했을 때는 $F_{N-2}$의 값이 필요하다('00'을 선택하면 남은 수열의 길이는 n-2이기 때문)
$F_{1}=1$
$F_{2}=2$
$F_{N} = F_{N-1} + F_{N-2}$
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
#include <iostream>
using namespace std;
long long memo[1000001];
int main()
{
int n;
scanf("%d", &n);
memo[1]=1; memo[2]=2;
for(int i=3; i<=n; i++){
memo[i]=(memo[i-1]+memo[i-2])%15746;
}
printf("%lld\n", memo[n]);
return 0;
}
|
cs |
i번째 집의 색은 i-1번째 집의 색과 달라야 한다.
빨간색을 0, 초록색을 1, 파란색을 2라고 한다면 $dp[i][j]$를 i번째 집의 색을 j라고 정했을 때의 비용의 최솟값이라고 할 수 있다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#include <iostream>
using namespace std;
int n;
int a[1001], b[1001], c[1001];
int dp[1001][3];
int main()
{
scanf("%d", &n);
for(int i=1; i<=n; i++){
scanf("%d %d %d", &a[i], &b[i], &c[i]);
}
dp[1][0]=a[1]; dp[1][1]=b[1]; dp[1][2]=c[1];
for(int i=2; i<=n; i++){
dp[i][0]=min(dp[i-1][1], dp[i-1][2])+a[i];
dp[i][1]=min(dp[i-1][0], dp[i-1][2])+b[i];
dp[i][2]=min(dp[i-1][0], dp[i-1][1])+c[i];
}
printf("%d\n", min(dp[n][0], min(dp[n][1], dp[n][2])));
return 0;
}
|
cs |
예를 들어 dp[i][0]은 i-1번째 집에서 색을 0으로 정하지 않았어야 하므로 dp[i-1][1]과 dp[i-1[2]의 최솟값에 a[i]를 더한 값으로 생각할 수 있다.
아래 코드는 탑다운 방식으로 짠 코드다.
|
1
2
3
4
5
6
7
8
9
10
11
12
|
const int inf = 1e9;
int dp(int n, int color)
{
if(n==0) return 0;
if(memo[n][color]!=-1) return memo[n][color];
memo[n][color] = inf;
if(color!=0) memo[n][color]=min(memo[n][color], dp(n-1, 0)+a[n]);
if(color!=1) memo[n][color]=min(memo[n][color], dp(n-1, 1)+b[n]);
if(color!=2) memo[n][color]=min(memo[n][color], dp(n-1, 2)+c[n]);
return memo[n][color];
}
|
cs |
유명한 dp 문제로, 점화식을 구성할 때의 디테일한 부분에 집중해야 한다.
$dp[i]$: [1, i]의 원소들로 구성된, 마지막 원소가 $a_{i}$인 lis의 길이 (마지막 원소에 대한 조건이 왜 있는지 고민해보는 것을 추천한다.)
$dp[i] = dp[j] + 1$ (단, $j < i 이고 a_{j} < a_{i}$이다.)
1. Top-Down
|
1
2
3
4
5
6
7
8
9
10
11
|
int dp(int x)
{
if(memo[x]!=-1) return memo[x];
memo[x]=0;
for(int i=x+1; i<=n; i++){
if(arr[x]<arr[i]){
memo[x]=max(memo[x], dp(i)+1);
}
}
return memo[x];
}
|
cs |
2. Bottem-Up
|
1
2
3
4
5
6
7
8
9
10
|
for(int i=1; i<=n; i++){
dp[i]=1;
// 최소 길이는 i를 원소로 하는 1이다.
for(int j=1; j<i; j++){
if(arr[i]>arr[j]){
dp[i]=max(dp[j]+1, dp[i]);
}
}
ans=max(ans, dp[i]);
}
|
cs |
4) BOJ 9251 LCS: https://david0506.tistory.com/38
'Algorithm' 카테고리의 다른 글
| [ Graph ] 깊이 우선 탐색 (DFS, Depth-First-Search) (1) | 2021.02.11 |
|---|---|
| 그래프란? (0) | 2021.02.11 |
| [ Sort ] 다양한 정렬 방법 (0) | 2021.02.11 |
| [ Search ] 백트래킹 (BackTracking) (0) | 2021.02.11 |
| [ Search ] 이분탐색(Binary Search), Parametric Search (0) | 2021.02.11 |