Dynamic Programming

1) overlapping subproblem

큰문제를 작은 문제로.

큰문제를 작은 문제로 나누는 두가지 알고리즘에는

• 동적 계획법
• 분할 정복

이 있다.
참고로 '동적'에 의미는 없다.

분할 정복과 달리 중복가능하다.

2) optimal substructure

문제의 정답을 작은 문제의 정답에서 구할 수 있다.

각 문제를 한번만 풀어야 한다.

따라서 정답을 어딘가에 메모해 둔다 : Memoization

두가지 구현

Top-Down

1. 큰 문제를 작은 문제로 나눈다.
2. 작은 문제를 푼다.
3. 작은 문제를 풀었으니, 이제 큰 문제를 푼다.

주로 재귀함수로 구현함

Bottom-Up

1. 문제를 크기가 작은 문제부터 차례대로 푼다
2. 문제의 크기를 조금씩 크게 만들며 푼다.
3. 작은 문제를 풀면서 왔기에, 큰 문제는 항상 풀 수 있다. 결국 반복하다보면 가장 큰 문제를 풀 수 있다.

주로 반복문으로 구현

예시 : #boj 1463

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

풀이

dp[n] = min(dp[n-1], dp[n-2], dp[n-3]) + 1
dp[1] = 0

sol1. Top-Down

#include <iostream>
using namespace std;
int d[1000001];
int go(int n) {
    if (n == 1) {
        return 0;
    }
    if (d[n] > 0) {
        return d[n];
    }
    
    d[n] = go(n-1) + 1;
    
    if (n%2 == 0) {
        int temp = go(n/2) + 1;
        if (d[n] > temp) {
            d[n] = temp;
        }
    }
    if (n%3 == 0) {
        int temp = go(n/3) + 1;
        if (d[n] > temp) {
            d[n] = temp;
        }
    }
    return d[n];
}
int main() {
    int n;
    cin >> n;
    cout << go(n) << '\n';
    return 0;
}

sol2. bottom-up

#include <iostream>
using namespace std;
int d[1000001];
int main() {
    int n;
    cin >> n;
    d[1] = 0;
    for (int i=2; i<=n; i++) {
        d[i] = d[i-1] + 1;
        if (i%2 == 0 && d[i] > d[i/2] + 1) {
            d[i] = d[i/2] + 1;
        }
        if (i%3 == 0 && d[i] > d[i/3] + 1) {
            d[i] = d[i/3] + 1;
        }
    }
    cout << d[n] << '\n';
    return 0;
}