0x10. 다이나믹 프로그래밍(DP) - 메모이제이션과 점화식

0x10 다이나믹 프로그래밍

0x00 알고리즘 설명

다이나믹 프로그래밍 ( Dynamic Programming, DP ) : 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘

DP를 푸는 과정

테이블 정의하기
점화식 찾기
초기값 정하기

0x01 연습문제

BOJ 1463번 : 1로 만들기

테이블 정의하기 D[i] = i를 1로 만들기 위해 필요한 연산 사용 횟수의 최솟값
점화식 찾기 D[k] = ? 3으로 나누어지면 3으로 나누거나 ( D[k] = D[k/3] +1 ) 2로 나누어지면 2으로 나누거나 ( D[k] = D[k/2] +1 ) 1을 빼거나 ( D[k] = D[k-1] + 1 ), 이들 중에서 최솟값
초기값 정의하기 D[1] = 0

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

int D[1000002];
int n;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    D[1] = 0; // 초기값 설정
    for(int i=2; i<=n; i++) {
        D[i]= D[i-1] + 1;
        if(i%2= 0) D[i]= min(D[i], D[i/2]+1);
        if(i%3= 0) D[i]= min(D[i], D[i/3]+1);
    }
    cout << D[n];
}

BOJ 9095번 : 1, 2, 3 더하기

테이블 정의하기 D[i] = i를 1, 2, 3의 합으로 나타내는 방법의 수
점화식 찾기 D[4] = ? 1+1+1+1, 3+1, 2+1+1, 1+2+1 ( 3을 1, 2, 3의 합으로 나타내는 방법 ) + 1, D[3] 1+1+2, 2+2 ( 2를 1, 2, 3의 합으로 나타내는 방법 ) + 2, D[2] 1+3 ( 1을 1, 2, 3의 합으로 나타내는 방법 ) + 3, D[1] D[4] = D[1] + D[2] + D[3] D[k] = D[k-1] + D[k-2] + D[k-3]
초기값 정의하기 D[1] = 1, D[2] = 2, D[3] = 4 D[k] = D[k-1] + D[k-2] + D[k-3]이니 초기값이 최소 3개는 주어져야 한다.

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

int D[15];
int t, n;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> t;
    D[1] = 1, D[2] = 2, D[3] = 4; // 초기값 설정
    for(int i=4; i<12; i++)
        D[i]= D[i-1] + D[i-2] + D[i-3];

    while(t--) {
        cin >> n;
        cout << D[n] << "\n";
    }
}

BOJ 2579번 : 계단 오르기

테이블 정의하기 D[i][j] = 현재까지 j개의 계단을 연속해서 밟고 i번째 계단까지 올라섰을 때 점수 합의 최댓값, 단 i번째 계단은 반드시 밟아야 함
점화식 찾기 D[k][1] = max(D[k-2][1], D[k-2][2]) + S[k] D[k][2] = D[k-1][1] + S[k] (연속으로 3개의 계단을 밟을 수는 없다는 제한이 있기 때문) 마지막에 max(D[N][1], D[N][2]) 출력
초기값 정하기 D[1][1] = S[1], D[1][2] = 0, D[2][1] = S[2], D[2][2] = S[1] + S[2]

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

int D[302][3];
int S[302];
int n;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i=1; i<=n; i++) cin >> S[i];

    D[1][1] = S[1], D[1][2] = 0,
    D[2][1] = S[2], D[2][2] = S[1] + S[2]; // 초기값 설정
    for(int i=3; i<=n; i++) {
        D[i][1]= max(D[i-2][1], D[i-2][2]) + S[i];
        D[i][2]= D[i-1][1] + S[i];
    }

    cout << max(D[n][1], D[n][2]) << "\n";
}

1차원 배열로 해결

테이블 정의하기 D[i] = i번째 계단까지 올라섰을 때 밟지 않을 계단의 합의 최솟값, 단 i번째 계단은 반드시 밟지 않을 계단으로 선택해야 함
점화식 찾기 D[k] = S[k] + min(D[k-2], D[k-3])
초기값 정하기 D[1] = S[1], D[2] = S[2], D[3] = S[3] 모든 점수의 합에서 min(D[N-1], D[N-2])를 빼면 답

BOJ 1149번 : RGB거리

테이블 정의하기 D[i][0] = i번째 집까지 칠할 때 비용의 최솟값, 단 i번째 집은 빨강 D[i][1] = i번째 집까지 칠할 때 비용의 최솟값, 단 i번째 집은 초록 D[i][2] = i번째 집까지 칠할 때 비용의 최솟값, 단 i번째 집은 파랑
점화식 D[k][0] = min(D[k-1][1], D[k-1][2]) + R[k] D[k][1] = min(D[k-1][0], D[k-1][2]) + G[k] D[k][2] = min(D[k-1][0], D[k-1][1]) + B[k]
초기값 정하기 D[1][0] = R[1] D[1][1] = G[1] D[1][2] = B[1]

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

int D[1002][3];
int R[1002], G[1002], B[1002];
int n;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i=1; i<=n; i++) cin >> R[i] >> G[i] >> B[i];
    if(n == 1) {
        cout << min(min(R[1], G[1]), B[1]);
        return 0;
    }

    D[1][0]= R[1], D[1][1]= G[1], D[1][2]= B[1]; // 초기값 설정
    for(int k=2; k<=n; k++) {
        D[k][0]= min(D[k-1][1], D[k-1][2]) + R[k];
        D[k][1]= min(D[k-1][0], D[k-1][2]) + G[k];
        D[k][2]= min(D[k-1][0], D[k-1][1]) + B[k];
    }

    cout << min(min(D[n][0], D[n][1]), D[n][2]) << "\n";
    // cout << *min_element(D[n], D[n]+3);
}

BOJ 11726번 : 2 X n 타일링

테이블 정의하기 D[i] = 2 X i 크기의 직사각형을 채우는 방법의 수
점화식 찾기

왼쪽 위칸을 2x1 타일로 덮으면 D[n-1]가지가 있고, 1x2 타일로 덮으면 D[n-2]가지

초기값 정하기 D[1] = 1 D[2] = 2

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

int D[10002];
int n;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    D[1] = 1;
    D[2] = 2;

    for(int i=3; i<=n; i++) D[i]= (D[i-1]+D[i-2])%10007;
    cout << D[n] << "\n";
}

BOJ 11659번 : 구간 합 구하기 4

Prefix Sum ( 구간 합 )

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

int D[100002];
int A[100002];
int n, m;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for(int i=1; i<=n; i++) {
        cin >> A[i];
        D[i] = D[i-1] + A[i];
    }

    while(m--) {
        int i, j;
        cin >> i >> j;
        cout << D[j]-D[i-1] << "\n";
    }
}

0x02 경로 추적

BOJ 12852 : 1로 만들기 2

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

int d[1000002];
int pre[1000002];
int n;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    d[1] = 0;
    for(int i=2; i<=n; i++) {
        d[i]= d[i-1]  + 1;
        pre[i]= i-1;
        if(i%2= 0 && d[i] > d[i/2]+1) {
            d[i] = d[i/2] + 1;
            pre[i] = i/2;
        }
        if(i%3 == 0 && d[i] > d[i/3]+1) {
            d[i] = d[i/3] + 1;
            pre[i] = i/3;
        }
    }
    cout << d[n] << "\n";

    int cur= n;
    while(1) {
        cout << cur << " ";
        if(cur= 1) break;
        cur= pre[cur];
    }
}

단순히 DP에서 값만 출력하는 것이 아니라 값을 얻은 경로가 필요한 상황이라면 값이 어디서부터 온 것인가를 따로 저장한 후 나중에 경로를 복원하면 된다.

문제 풀이

Note_ 1932번 정수 삼각형 : j와 j+1을 비교해서 큰값을 담으려고 해서 경우의 수가 커졌는데 다른 시각으로 보면 간단해졌다.

d[1][1] = a[1][1];
for(int i = 2; i <= n; i++)
    for(int j = 1; j <= i; j++)
        d[i][j] = max(d[i-1][j-1], d[i-1][j]) + a[i][j];

cout << *max_element(d[n] + 1, d[n] + n + 1);

1912번 연속합 : 더한것과 안더한것 중 최대를 선택

for(int i = 1; i <= n; ++i){
    cin >> a[i];
    d[i] = a[i];
}

for(int i = 1; i <= n; ++i)
    d[i] = max(d[i], d[i-1] + a[i]);

cout << *max_element(d + 1, d + n + 1);

9461번 파도반 수열 : 문제 해결은 했으나 기억해두면 좋을 수학식

d[i] = d[i - 2] + d[i - 3];

14501번 퇴사 : 정답에 거의 근접했지만 n에서 1로 내림차순을 생각해내지 못했다.

int d[20]; // i번째 일에 상담을 시작했을 때 얻을 수 있는 최대 수익

for(int i=n; i>0; i--) {
    // i번째 일에 상담을 할 수 있을 경우
    if(i + t[i]-1 <= n) {
       // i번째 일에 상담을 했을 때와 상담을 하지 않았을 때 얻을 수 있는 수익 중 최대 수익을 취함
        d[i] = max(d[i + t[i]] + p[i], d[i + 1]);
    }
    else d[i] = d[i + 1];
}

10844번 쉬운 계단 수 : 도저히 정답이 생각이 안났던 문제. DP 문제 대부분이 정답을 보는 순간 허무해지는 느낌이 있다.

ll d[102][10]; // d[i][j]는 길이가 i이고, 끝자리가 j인 계단수의 개수
for(int i=1; i<=9; i++) d[1][i] = 1; // 초기값
for(int i=2; i<=n; i++)
    for(int j=0; j<=9; j++) {
        if(j != 0) d[i][j] += d[i-1][j-1];
        if(j != 9) d[i][j] += d[i-1][j+1];
    }

리뷰

다이나믹 프로그래밍도 생소한 개념이였지만 테이블을 정의하고 점화식을 떠올리는 연습만 한다면 코드는 정말 간단한 것 같다.

하지만 테이블 정의와 점화식 떠올리는 것이 생각보다 너무 어려웠다.

연습문제를 천천히 풀어보고 다음으로 넘어가려고 한다.

다음은 0X11 그리디로 돌아오겠다.

출처: 바킹독님의 실전알고리즘 강의