티스토리 뷰

Table of Contents


개요

DP 기본 예제 – 피보나치 수열

DP 구현하기

DP 문제 - 1

DP로 문제에 접근하기

DP 문제 - 2

유명한 DP 응용

주의할 점

DP 문제 - 3




1. 개요


 동적 계획법, 영어로 Dynamic programming 다이나믹 프로그래밍, 줄여서 DP.


 문제를 여러 개의 하위 문제들로 나누어 먼저 처리한 후, 그 하위 문제들의 답을 이용해 원래 문제를 처리하는 방법을 뜻합니다. 하위 문제를 처리하는 과정에서 같은 문제를 여러 번 처리하게 되는데, 한 번 수행한 문제들의 답을 저장해 놓으면 그 다음부터는 답을 바로 알아낼 수 있어 속도를 비약적으로 빨라지게 할 수 있습니다.




2. DP 기본 예제 – 피보나치 수열


 피보나치 수열을 DP로 구하는 과정을 통해서 DP에 대해 알아보도록 하겠습니다. 피보나치 수열은 아래의 조건을 만족하는 수열입니다.


{\displaystyle F_{n}:={\begin{cases}0&{\mbox{if }}n=0;\\1&{\mbox{if }}n=1;\\F_{n-1}+F_{n-2}&{\mbox{if }}n>1.\\\end{cases}}}



 이제 '음이 아닌 정수 n이 주어졌을 때 F[n]을 구하라.'는 문제를 DP로 해결해 보겠습니다. 개요에 나오듯이, DP란 '문제'를 여러 개의 '하위 문제'들로 나누어 먼저 처리한 후에 원래 문제의 답을 찾는 방법입니다. 지금 '문제'는 'F[n]'이라고 할 수 있습니다. 그리고 문제를 풀기 위한 '하위 문제'는 자연스럽게 F[n-1]와 F[n-2]가 됩니다.


 다시 말하면 F[n] = F[n-1] + F[n-2] 라는 점화식이 성립하므로 '문제' F[n] 을 구하기 위해 '하위 문제' F[n-1], F[n-2] 의 답을 먼저 구한 후, 이 두 개를 더해 F[n] 을 구하는 전략을 생각해 볼 수 있습니다.


 이를 재귀함수로 구현하면 아래의 코드 1-1과 같이 됩니다.


1
2
3
4
5
// code by RiKang, weeklyps.com
int fibonacci(int n){
    if(n<=1return n;
    return fibonacci(n-1+ fibonacci(n-2);
}
cs


위 함수를 이용하여 F[4]를 구하면 아래와 같이 함수들이 호출됩니다.



 그런데 이 호출 과정을 보면, 같은 값을 return 함에도 함수가 호출될 때마다 새롭게 값을 구하는 함수( * f(2)) 가 있다는 걸 알 수 있습니다.이는 시간복잡도 측면에서 굉장한 낭비가 됩니다.


 다행히 개선 방법은 간단합니다. 함수가 처음으로 호출되었을 때 return 했던 값을 따로 저장해 놓으면, 재 호출 되었을 시 새로 계산하지 않고 저장해 놓은 값을 바로 return 할 수 있습니다.


 이러한 방법을 ‘메모이제이션’ 이라고 합니다.


1
2
3
4
5
6
7
// code by RiKang, weeklyps.com
int dp[15]
int fibonacci(int n){
    if(n<=1return n;
    if(dp[n]!=0return dp[n];
    return dp[n] = fibonacci(n-1+ fibonacci(n-2);
}
cs


 이 코드로 다시 F[4]를 구하면 아래와 같이 함수가 호출됩니다.



코드 1-1 과 달리 처음 fibonacci(2) 수행 시 결과값을 저장했기 때문에 다음에는 f(2)를 구하기 위해 f(0), f(1) 을 호출할 필요가 없어집니다. 그냥 dp[2]를 리턴하면 끝이기 때문입니다. F[4]는 숫자가 작아 큰 차이가 나진 않지만 n이 커질수록 코드 1-1.과 코드 1-2의 수행 시간 차이는 기하급수적으로 늘어나게 됩니다.




3. DP 구현하기


 DP를 구현하는 방식에는 크게 2가지 방식, 반복적 동적 계획법과 재귀적 동적 계획법이 있습니다. 반복적 동적 계획법은 재귀 호출이 아닌 반복문을 통해 구현하고,  재귀적 동적 계획법은 재귀 호출과 메모이제이션을 통해 구현합니다.


1
2
3
4
5
6
7
8
9
// code by RiKang, weeklyps.com
int dp[55]
 
int fibonacci(int n){
    dp[0= 0, dp[1= 1;
    for(int i=2; i<=n; i++)
        dp[i] = dp[i-1+ dp[i-2];
    return dp[n];
}
cs


반복적 동적 계획법을 이용한 피보나치 수열


1
2
3
4
5
6
7
8
// code by RiKang, weeklyps.com
int dp[55]
 
int fibonacci(int n){
    if(n<=1return n;
    if(dp[n]!=0return dp[n];
    return dp[n] = fibonacci(n-1+ fibonacci(n-2);
}
cs


재귀적 동적 계획법을 이용한 피보나치 수열


 이 두 가지 방법은 서로 장단점을 가지고 있는데, DP에 대한 감각과 이해도의 향상을 위해서 두 가지 방법 모두 사용해 보시는 걸 추천합니다. 그리고 어떤 방법을 선택 하는 지에 따라 메모리를 절약할 수 있거나, 구현 난이도가 내려가는 등의 이득을 볼 수 있으니 어려운 문제의 경우엔 구현하기 전에 어떤 방식으로 코딩할 것인지 생각해 보는 것이 좋습니다.




4. DP 문제 - 1


(0) [BOJ 9461] 파도반 수열



(1) [BOJ 1003] 피보나치 함수



(2) [BOJ 1149] RGB거리





5. DP로 문제에 접근하기


 DP로 주어진 문제를 해결하고자 할 때 필요한 것은 아래의 3가지 정도가 있습니다.


(1) DP 문제를 정의하는 것

(2) 문제의 해결에 필요한 하위 문제들을 찾는 것

(3) 하위 문제들의 답으로 문제의 답을 구하는 방법


 다음 예제를 통해 DP 문제를 단계적으로 해결해 보겠습니다. 꼭 문제를 먼저 읽으시길 바랍니다.


예제 ) 삼각 그래프


1) DP 문제를 정의하는 것


 가장 아래쪽 ‘정점’ 으로 가는 ‘최소 비용’ 을 구해야 하므로 자연스럽게 다음과 같이 문제를 정의할 수 있습니다.

 DP( i, j ) = i 행의 j 번째 ‘정점’ 까지 가는데 필요한 ‘최소 비용’.


2) 문제의 해결에 필요한 하위 문제들을 찾는 것


 ( i , j )로  갈 수 있는 정점은 ( i-1 , j-1 ), ( i-1 , j ), ( i-1 , j+1 ), ( i , j-1 ) 뿐입니다. ( * ( i, j ) = i 행의 j 번째 정점 )

 그리고 다른 정점에서는 ( i , j ) 로 직행하는 것이 불가능 하므로 다음과 같이 하위 문제들을 특정할 수 있습니다.

 DP( i, j ) 하위 문제 = DP( i-1 , j-1 ), DP( i-1 , j ), DP( i-1 , j+1 ), DP( i , j-1 )


3) 하위 문제들의 답으로 문제의 답을 구하는 방법


 마지막으로 DP( i, j ) 와 하위 문제들 사이의 관계를 알아내야 합니다. 이를 위해  DP( i-1 , j-1 )의 정의와 덧셈 연산의 특성을 고려해 보면 다음과 같은 사실을 알 수 있습니다.


 ( i , j ) 직전에 ( i-1 , j-1 ) 을 거친 경우 중 최소 비용 = DP( i-1 , j-1 ) + A[i][j] ( * A[i][j] = ij번째 정점의 비용 )


 그리고 ( i , j ) 에 도달하기 위해선 ( i-1 , j-1 ), ( i-1 , j ), ( i-1 , j+1 ), ( i , j-1 ) 중 하나를 무조건 거쳐야 하므로다음과 같은 식이 성립합니다.


 DP( i, j ) = ( i , j ) 직전에 ( i-1 , j-1 ) or ( i-1 , j ) or ( i-1 , j+1 ) or ( i , j-1 )  을 거친 경우 중 최소 비용

                  = MIN( DP( i-1 , j-1 )+A[i][j], DP( i-1 , j )+A[i][j], DP( i-1 , j+1 )+A[i][j]DP( i , j-1 )+A[i][j] )

                  = MIN( DP( i-1 , j-1 ), DP( i-1 , j ), DP( i-1 , j+1 ), DP( i , j-1 ) ) + A[i][j]


 이제 이를 구현한 후 정답 = DP( n, 2)이 됨은 자명합니다.


( * 이 경우에서는 아니었지만, 만일 (3)까지 진행해 본 결과 (1)에서 정의한 문제의 답을 구할 수 없거나 너무 큰 시간복잡도를 줄일 수 없다면, (1)과 (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
// code by RiKang, weeklyps.com
#include <stdio.h>
#include <algorithm>
 
using namespace std;
 
const int N = 100000, INF = 2140000000;
int n;
int a[N+5][4];
int dp[N+5][4];
 
int get_dp(int i, int j){
    if(i==1 && j==2return dp[i][2= a[i][2];
    if(i==1 && j==3return dp[i][3= a[i][2]+a[i][3];
    if(i<=1 || j<1 || j>3return INF;
    if(dp[i][j]!=INF) return dp[i][j];
    return dp[i][j] = min({get_dp(i-1,j-1),get_dp(i-1,j),get_dp(i-1,j+1),get_dp(i,j-1)}) + a[i][j];
}
 
int main(){
    for(int i=1true; i++){
        scanf("%d",&n);
        if(n==0break;
        for(int j=1; j<=n; j++)
            for(int k=1; k<=3; k++){
                dp[j][k] = INF;
                scanf("%d",&a[j][k]);
            }
        printf("%d. %d\n",i,get_dp(n,2));
    }
    return 0;
}
cs




6.  DP 문제 - 2


(0) [BOJ 2579] 계단 오르기 

풀이 링크


(1) [BOJ 5060] 무글 맵스 

풀이 링크




7. 유명한 DP 응용



(0) 0/1 냅색



(1) LIS




8. 주의할 점


1) 문제들을 정점으로, 상위 문제 -> 하위 문제를 간선으로 그래프를 그렸을 때, 사이클이 없는 방향성 그래프 ( 즉, DAG( Directed Acyclic Graph )) 가 되도록 정의해야 합니다.


 만일 (1)의 조건에 어긋나는 상황, 아래 그림과 같은 상황이 나온다면 무한 루프에 빠지는 등 DP로 해결이 힘들어지게 됩니다.


DP(1)을 구하는데 DP(2)가 필요하고 DP(2)구하는데 DP(3)가 필요하고

DP(3)구하는데 DP(1)이 필요한 무한 루프의 상황


 위의 특징으로 인해 만일 문제의 입력이 사이클이 존재하는 그래프로 주어진다면 DP의 가능성이 낮아지게 됩니다. (DP에 맞도록 그래프를 변형하여 응용하는 등의 경우도 있어 가능성이 없진 않습니다.)

 반대로 만일 입력이 DAG의 형식으로 주어진다면 DP의 가능성을 의심해 보아야 하며, 그중에서도 특히 tree 에 DP를 적용하는 문제들은 대회에서 꽤 높은 빈도로 출제되고 있습니다.


 예시)

 DP 문제 - 3 (0) - (https://www.acmicpc.net/problem/2533)

 DP 문제 - 3 (1) - (http://codeforces.com/contest/235/problem/B)


2) DP 문제의 갯수, 저장할 정보의 양, 상위 문제와 하위 문제 사이의 관계의 갯수, 상위 문제와 하위 문제의 관계식 등은 서로 상호작용을 합니다.


 위의 요소들은 프로그램의 최종 시간 복잡도에 결정적인 영향을 끼치는 것들입니다. 그렇기 때문에, 생각해낸 솔루션의 시간 복잡도가 높을 경우 이 요소들을 줄여보는 시도를 하게 됩니다. 물론 다른 요소들은 가만히 둔 채 시간 복잡도가 개선된다면 좋겠지만, 그렇게 되지 않아서 막히는 경우도 많습니다. 이럴 경우엔, 이들의 관계에 좀 더 주의하며 솔루션 개선을 노리는 게 도움이 될 수 있습니다. 예를 들면 저장할 정보를 추가하거나 수정했더니 필요한 하위 문제의 갯수가 1/N 로 줄이는 방법이 나타나는 경우 등입니다.


 예시)

 DP 문제 - 3 (3) - (http://www.acmicpc.net/problem/8902)




9. DP 문제 - 3


(0) [BOJ 2533] 사회망 서비스 

풀이 링크


(1) [CF 146 B] Let's play osu! 

풀이 링크


(2) [CF 265 C] Subtitutes in Number


(3) [BOJ 8902] 색상의 길이 


(4) [BOJ 9338] Chemicals monitoring 


※ 본문의 코드들은 C++ 14 환경으로 작성되었습니다.