다이나믹 프로그래밍(Dynamic Programming)

다이나믹 프로그래밍 정의

  • 다이나믹 프로그래밍은 "큰 문제를 작은문제로 나눠서 생각한다" 라는 아이디어에서 고안된 방법이다. 분할 정복 문제와의 차이점은 중복의 여부이다. 다이나믹 프로그래밍은 중복이 나온 경우 효율적으로 처리하고, 분할 정복은 중복이 등장하지 않는다.

  • 두 가지 속성을 만족해야 다이나믹 프로그래밍으로 문제를 풀 수 있다.

    • Overlapping Subproblem : 겹치는 부분 존재
    • Optimal Substructure : 최적부분 구조(더 작은 부분으로부터 큰 값을 구할 수 있다.)
  • 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 문제에는 "피보나치 수"가 있다.

    • F0 = 0, F1 = 1, Fn = F(n-1) + F(n-2) (n>=2)
    • Fn이라는 큰 문제는, F(n-1) + F(n-2) 작은문제들의 합으로 구할 수 있다. (Overlapping Subproblem)
  • 서울에서 부산을 가는 가장 빠른 길이 대전과 대구를 순서대로 거쳐야 한다면 대전에서 부산을 가는 가장 빠른 길은 대구를 거쳐야 한다. (Optimal Substructure)

  • Optimal Substructure의 조건을 만족하면, 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다.

  • Top - Down (재귀)

    • 문제를 풀어야 한다. (fibonacci(n))
    • 문제를 작은 문제로 나눈다. (fibonacci(n-1) 과 fibonacci(n-2))
    • 작은 문제를 푼다. (fibonacci(n-1) 과 fibonacci(n-2) 를 호출해서 문제를 푼다.)
    • 작은 문제를 풀었으니, 이제 문제를 푼다 (fibonacci(n-1) fibonacci(n-2)의 값을 더해 문제를 푼다.
  • Bottom - Up (반복)

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

※ 피보나치 수

image.png

다이나믹 프로그래밍 문제 풀이 전략

  • 문제에서 구하려고 하는 답을 문장으로 나타낸다.
  • 예 ) 피보나치 수를 구하는 문제
  • N번째 피보나치 수
  • 이제 그 문장에 나와 있는 변수의 개수만큼 메모하는 배열을 만든다.
  • Top-Down의 경우에는 재귀 호출의 인자의 개수
  • 문제를 작은 문제로 나누고 ,수식을 이용해서 문제를 표현해야 한다.
int fibonacci(int n) {

 if (n <= 1) {
     return n;
 }
 else {
     return fibonacci(n-1) + fibonacci(n-2); 
 }
}

문제

image.png

image.png

풀이

  • DP로 해결할 수 있는 문제이다. DP[9]의 연산 + 1과 DP[5] +1 을하면 된다.
  • 따라서 점화식은 아래와 같다. i값을 1빼거나, 3나누거나, 2 나누거나 한 경우중 가장 작은 값을 선택하면 된다.
  • 2로만 나눠지는경우, 3으로만 나눠지는 경우, 2와 3 모두 나눠지는 경우에 따라 점화식이 변하게 된다.

점화식 : N을 1로 만드는 최소 연산 횟수

dp[i] = 1 + min(dp[i-1],dp[i/2],dp[i/3])

예를들어, 입력에 10이 들어 왔다면, 10이 1이 될 수 있는 경우는 아래와 같다.

10 -> 9 -> 3 -> 1 (3번 연산)
10 -> 5 -> 4 -> 2 -> 1 ( 4번연산)

코드

[Bottom - up 방식]

#include<stdio.h>
#define MAX 1000001
#include<algorithm>
using namespace std;
int dp[MAX] = {0,0,1,1};
int main() {

    int n;
    for(int i = 4; i < MAX; i++) {
        if(i % 2 == 0 && i % 3 != 0) {
            dp[i] = 1 + min(dp[i-1],dp[i/2]);    
        }
        else if(i% 2 != 0 && i % 3 == 0) {
            dp[i] = 1 + min(dp[i-1],dp[i/3]);
        }
        else if(i%2 == 0 && i % 3 == 0) {
            dp[i] = 1 + min(dp[i-1] , min(dp[i/2],dp[i/3]) );
        }
        else {
            dp[i] = 1 + dp[i-1];
        }

    }    
    scanf("%d",&n);
    printf("%d\n",dp[n]);

    return 0;
}

[Top-Down방식]

#include<stdio.h>
int d[100001];
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;
    scanf("%d",&n);
    printf("%d",go(n));
    return 0;
}