동적 계획법(Dynamic Programming)

동적 계획법이 뭐에요

동적 계획법을 한 마디로 정의내리기는 힘들지만 핵심은 큰 문제를 해결하기 위해 더 작은 문제를 해결한다는 것입니다.

실제로 PS를 할 때 가장 많이 보이는 문제 유형이기도 하고, solved.ac 기준 3번째로 많은 태그입니다.

예시로 설명해요

피보나치 수열로 예를 들어보겠습니다.

 

$$F_n =  \begin{cases} 0  & \text{if }n = 0 \\ 1   & \text{if }n = 1 \\ F_{n-1} + F_{n-2}   & \text{if }n > 1 \end{cases}$$

피보나치 수열의 점화식은 이렇습니다.

$F_n$이라는 큰 문제를 해결하기 위해 $F_{n-1}$과 $F_{n-2}$ 같은 작은 문제의 결과를 이용합니다.

간단하게 재귀 함수로 코드를 짜면

int fibonacci(int n) {
    if(n==0) return 0;
    if(n==1) return 1;
    return fibonacci(n-1)+fibonacci(n-2);
}

이렇게 됩니다.

그러나 n=30 정도만 돼도 답을 빠르게 구하지 못합니다.

그 이유는 같은 항의 피보나치 함수를 너무 많이 호출하기 때문입니다.

그래서 보통 메모이제이션(memoization) 기법을 사용합니다.

int dp[100];
int fibonacci(int n) {
    if(n==0) return 0;
    if(n==1) return 1;
    if(dp[n]!=0) return dp[n];
    return dp[n]=fibonacci(n-1)+fibonacci(n-2);
}

메모이제이션이란 간단하게 말해서 값을 배열로 저장해두는 것입니다. 그러면 같은 항이 또 호출되면 기록된 값을 리턴하게 되어 $O(N)$에 계산할 수 있게 됩니다. 이 방식을 Topdown 방식이라고 합니다. 큰 문제부터 접근을 하는 거에요.

 

재귀 호출을 사용하지 않고 그냥 반복문으로 짤 수도 있습니다.

int f[100];
f[0]=0, f[1]=1;
for(int i=2; i<=N; i++) f[i]=f[i-1]+f[i-2];

이 방식은 Bottomup 방식이라고 합니다. 작은 문제를 먼저 접근합니다.

Topdown vs Bottomup

Topdown 방식의 장점은 생각하기 쉽다는 것입니다. 큰 문제의 답을 작은 문제로부터 가져오니 매우 직관적입니다. 또한 이 방식으로만 풀리는 문제들도 있습니다. 그러나 단점은 시간, 메모리 관점에서 비효율적입니다. 재귀 함수의 스택 메모리와 호출 시간을 무시할 수 없습니다. 또한 나중에 나올 DP Optimization을 적용하지 못합니다.

Bottomup 방식의 장점은 시간, 메모리 관점에서 매우 효율적입니다.

따라서 보통은 Bottomup 방식이 더 낫다고 볼 수 있습니다.

DP 문제 풀기

DP 문제를 풀 때는 DP 식을 어떻게 정의할 것인가와 점화식을 어떻게 구하고 답을 어떻게 구할 것인가가 가장 중요한 부분입니다. 가끔씩 Simple DP로 풀리지만, DP 식 정의가 굉장히 어려운 문제들도 있습니다.

예시 1

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

풀이

n을 1로 만들기 위한 연산의 최소 횟수를 $A_n$이라고 하면, $A_n$은 $A_{n/3}+1$ (3 | n인 경우 ) $A_{n/2}+1$ (2 | n 인 경우) $ A_{n-1}+1$ 중 최솟값이 됩니다. 물론 $A_1=0$입니다.

소스코드

#include <bits/stdc++.h>
using namespace std;

const int INF=987654321;
int n;
vector<int> dp;

int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    dp.resize(n+1,INF); dp[1]=0;
    for(int i=2;i<=n;i++) {
        dp[i]=dp[i-1]+1;
        if(i%3==0) dp[i]=min(dp[i],dp[i/3]+1);
        if(i%2==0) dp[i]=min(dp[i],dp[i/2]+1);
    }
    cout<<dp[n];
    return 0;
}

예시 2

https://www.acmicpc.net/problem/10870

10870번: 피보나치 수 5

풀이

위에서 설명한 것 처럼 피보나치 수를 구하면 됩니다.

소스코드

#include <bits/stdc++.h>
using namespace std;

int n,dp[30]={0,1};

int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    for(int i=2;i<=n;i++) dp[i]=dp[i-1]+dp[i-2];
    cout<<dp[n];
    return 0;
}

예시 2

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

풀이

n을 1, 2, 3들의 합으로 표현하는 방법의 수를 $dp_n$이라고 하면 $dp_1=1, dp_2=2, dp_3=4, dp_n=dp_{n-1}+dp_{n-2}+dp_{n-3}$이 됩니다.

소스코드

#include <bits/stdc++.h>
using namespace std;

int t,n,dp[20]={1};

int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(0);
    for(int i=1;i<=10;i++) {
        dp[i]=dp[i-1];
        if(i>=2) dp[i]+=dp[i-2];
        if(i>=3) dp[i]+=dp[i-3];
    }
    cin>>t;
    while(t--) {
        cin>>n;
        cout<<dp[n]<<"\n";
    }
    return 0;
}

예시 3

https://www.acmicpc.net/problem/11051

11051번: 이항 계수 2

풀이

\({N \choose K} = {{N-1} \choose K} + {{N-1} \choose {K-1}}\)입니다. 

소스코드

#include <bits/stdc++.h>
using namespace std;

const int Mod=10007;
int n,k,dp[1010][1010];

int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>k;
    for(int i=0;i<=n;i++) {
        dp[i][0]=1;
        for(int j=1;j<=i;j++) {
            dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%Mod;
        }
    }
    cout<<dp[n][k];
    return 0;
}

예시 4

https://www.acmicpc.net/problem/11057

11057번: 오르막 수

풀이

$dp_{i, j}$=i번째 자리가 j인 오르막 수의 개수라고 정의하면, \(dp_{i, j} = \sum_{k=0}^{j} {dp_{i-1, k}}\)가 됩니다.

소스코드

#include <bits/stdc++.h>
using namespace std;

const int Mod=10007;
int n,dp[1010][15],ans;

int main(void) {
	ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    for(int i=0;i<=9;i++) dp[1][i]=1;
    for(int i=2;i<=n;i++) {
        for(int j=0;j<=9;j++) {
            for(int k=0;k<=j;k++) dp[i][j]+=dp[i-1][k];
            dp[i][j]%=Mod;
        }
    }
    for(int i=0;i<=9;i++) {
        ans+=dp[n][i];
        ans%=Mod;
    }
    cout<<ans;
    return 0;
}

예시 5.

https://www.acmicpc.net/problem/11055

11055번: 가장 큰 증가 부분 수열

풀이

LIS(Longest Increasing Subsquence)라고 부르는 문제입니다.

$dp_i$=LIS의 마지막 원소가 $A_i$일 때 LIS의 길이라고 정의하면,

\(dp_i= \max_{0 \le j < i, A_j < A-i} {dp_j}\)가 됩니다.

소스코드

#include <bits/stdc++.h>
using namespace std;

int n,a[1010],dp[1010],ans;

int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) {
        for(int j=0;j<=n;j++) {
            if(a[j]<a[i]) dp[i]=max(dp[i],dp[j]+a[i]);
        }
        ans=max(ans,dp[i]);
    }
    cout<<ans;
    return 0;
}

예시 6

https://www.acmicpc.net/problem/11054

11054번: 가장 긴 바이토닉 부분 수열

풀이

앞에서부터 구한 LIS의 길이를 $dp1_i$로 정의하고 뒤에서부터 구한 LIS의 길이를 $dp2_i$로 정의합니다.

그러면 답은 \(\max_{i=1}^{n} {dp1_i+dp2_i}\)가 됩니다.

소스코드

#include <bits/stdc++.h>
using namespace std;

int n,a[1010],dp1[1010],dp2[1010],ans;

int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) {
        for(int j=0;j<i;j++) if(a[j]<a[i]) dp1[i]=max(dp1[i],dp1[j]+1);
    }
    for(int i=n;i>=1;i--) {
        for(int j=n+1;j>i;j--) if(a[j]<a[i]) dp2[i]=max(dp2[i],dp2[j]+1);
    }
    for(int i=1;i<=n;i++) ans=max(ans,dp1[i]+dp2[i]-1);
    cout<<ans;
    return 0;
}

예시 7.

https://www.acmicpc.net/problem/5557

5557번: 1학년

풀이

$dp_{i, j}$를 $i$번째까지 고려했고, 현재까지의 결과가 $j$인 경우의 수로 정의하면 점화식을 구할 수 있습니다.

(답이 int 범위를 초과할 수 있는 것에 주의해야 합니다.)

소스코드

#include <bits/stdc++.h>
using namespace std;
using ll=long long;

int N, A[110];
ll ans, DP[110][25];
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N;
    for(int i=1; i<=N; i++) cin>>A[i];
    DP[1][A[1]]=1;
    for(int i=2; i<N; i++) {
        for(int j=0; j<=20; j++) {
            if(j-A[i]>=0) DP[i][j]+=DP[i-1][j-A[i]];
            if(j+A[i]<=20) DP[i][j]+=DP[i-1][j+A[i]];
        }
    }
    cout<<DP[N-1][A[N]];
    return 0;
}

예시 8

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

풀이

0-1 Knapsack Problem으로 알려진 문제입니다.

$dp_{i, j}$를 "i번째 물건까지 고려했고, 지금까지 j의 무게를 사용했을 때 얻을 수 있는 최대 무게"라고 정의하면, $dp_{i, j}$를 구할 때는 i번째 물건을 사용할 때와 사용하지 않을 때(0-1)를 고려해주면 됩니다.

점화식은 \(dp_{i, j}=max(dp_{i-1, j}, dp_{i, j-W_i}+V_i)\)가 됩니다.

소스코드

#include <bits/stdc++.h>
using namespace std;

int n,k,w[110],v[110],dp[100010];

int main(void) {
	ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>w[i]>>v[i];
    for(int i=1;i<=n;i++) {
        for(int j=k;j>=w[i];j--) {
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        }
    }
    printf("%d",dp[k]);
    return 0;
}