동적 계획법(Dynamic Programming)

Dynamic Programming

---

동적 계획법(Dynamic Programming), 줄여서 DP는 특정 범위까지의 값을 구하기 위해 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계기법이다.

구현

---

동적 계획법의 접근 방식은 기본적으로 분할 정복 알고리즘과 비슷하다. 분할정복과 차이가 생기는 부분은 원래의 문제를 부분 문제로 나누는 방식에 있다. 동적 계획법의 경우 주어진 문제를 나눌 때 부분 문제를 최대한 많이 이용하도록 나눈 다음, 주어진 부분 문제의 정답을 한번만 계산하고 저장해둔 뒤 다시한 번 이 부분 문제를 이용할 때에는 저장해둔 정답을 바로 산출하여 이용함으로써 속도를 향상시킨다.

대표적인 예시

---

동적 계획법의 핵심이 되는 메모이제이션 코드이다. 

1. 재귀함수 형태의 피보나치 수열

int fibonnaci(int n){
    if(n <= 1){
        return n;
    }
    else{
        return fibonnaci(n - 1) + fobonacci(n - 2);
    }
}

아래의 그림과 같이 위 함수를 사용하면 중복 계산되는 부분이 생기고 실행시간이 길어지게된다.

2. 메모이제이션을 이용한 피보나치 수열

 
int fibo_memo(int n){
    int memo[10] = { 0 };
    if(n <= 1){
        return n;
    }
    else if(memo[n] != 0){
        return memo[n];
    }
    else{
        return fibo_memo(n - 1) + fibo_memo(n - 2);
    }
}

메모에 이전에 우선적으로 계산해 저장해 뒀던 값이 저장되어있다면 같은 계산을 반복하지 않고 그값을 사용하게 된다. 그래서 실행시간이 단축된다.

연습문제

---

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

Top-Down 방식

#include <stdio.h>
 
int N, i, answer;
int memo[11] = { 0 };
 
int fibo_memo(int n) {
    if (n <= 0) return 0;
    else if (n == 1) return 1;
    else if (n == 2) return 2;
    else if (n == 3) return 4;
    else {
        if (memo[n] != 0)
            return memo[n];
        else {
            memo[n] = fibo_memo(n - 1) + fibo_memo(n - 2) + fibo_memo(n - 3);
            return memo[n];
        }
    }
}
int main() {
    int T;
    
scanf("%d", &T);
    for (int i = 1; i <= T; i++) {
        
        scanf("%d", &N);
        answer = fibo_memo(N);
 
        printf("%d\n", answer);
 
    
    }
    return 0;
}

Down-Top 방식

#include <stdio.h>
 
int dp[1000001];
 
int min(int a, int b) {
    return a > b ? b : a;
}
 
int main() {
    int N;
    scanf("%d", &N);
    
    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);
        }
    }
    printf("%d", dp[N]);
    return 0;
}