[Algorithm] 동적 계획법(Dynamic Programming)이란?

🚦 이번 포스팅에서는 〰️

▶️ 동적 계획법(Dynamic Programming)이란?
▶️ 동적 계획법(Dynamic Programming) 문제 풀어보기

 

📌 동적 계획법(Dynamic Programming)이란?

---

: 하나의 문제는 단 한번만 풀도록 매번 저장하는 알고리즘

• 동일한 문제를 요구하는 경우 기존에 이미 저장해 두었던 것을 가져온다.
• 불필요한 반복 계산을 줄이고 효율적으로 최적해를 찾는다.
• 계산한 값들은 하나의 보관용 테이블(배열)에 순서대로 저장한다.
• 분할 정복법과 같이 여러개의 하위 문제들로 나누어 먼저 처리해야 할 때 사용한다.
• 대표적인 문제 : 피보나치 수열
• DP 구현의 두가지 방법
  1. 재귀 함수 이용 (Top - Down) : 큰 문제를 쪼개나간다.
     
     • 재귀 함수를 이용한 피보나치 수열 구현
     • int fibonacci(int x)
       {
       if (x<=1) {
            arr[x] = x;
               return arr[x];
           }
           if(arr[x]!=0) return arr[x];
           arr[x] = fibo(x-1) + fibo(x-2);
           return arr[x];
       }
  2. 반복문 이용 (Bottom - Up) : 작은 문제부터 올라간다.
     • 반복문을 이용한 피보나치 수열 구현
     • arr[0] = 0;
       arr[1] = 1;
       
       for(int i=2; i<=N; i++)
       {
       arr[i] = arr[i-1] + arr[i-2];
       }
       cout << arr[N] << endl;

 

---

 

 

 

〰️ 동적 계획법 vs 분할 정복법

: 우선 분할 정복법이란 큰 문제를 여러개의 작은 문제로 나누어 푸는 것을 말한다.

• 분할 정복법은 큰 문제를 여전히 다뤄질 수 있는 작은 문제로 분해해 가는 과정이 필요할 때 이용한다.
• 동적 계획법은 작은 문제들의 중첩의 과정에서 큰 문제를 해결할 때 이용한다.
• 동적 계획법이 분할 정복법보다 더 빠르다.

 

 

https://www.interviewbit.com/blog/difference-between-divide-and-conquer-and-dynamic-programming/

Divide&Conquer

 

 

 

 

---

 

 

〰️ 동적 계획법을 사용하려면

1. 큰 문제를 작은 문제로 나눌 수 있어야 한다.
   • 큰 문제들은 작은 문제들로 이루어진다.
   • ex) 피보나치 수열
   • 단, 큰 문제와 작은 문제의 관계에서 사이클이 발생해선 안된다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
   • 즉, 점화식을 세울 수 있어야 한다.
   • 작은 문제에서 구해 저장한 값을 큰 문제를 구하는 과정에서 쓸 수 있어야 한다.

 

📌 동적 계획법(Dynamic Programming) 문제 풀어보기

---

백준 21317 징검다리 건너기

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 999999;
/*
three jumps
plus 1 (no skip)
plus 2 (1 skip)
plus 3 (2 skips) -> just one time & k energy
*/


int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n,k; cin >> n;
    pair<int, int> energy[21];
    for(int i=1; i<n; i++) {
        int x,y; cin >> x >> y;
        energy[i] = make_pair(x,y);
    }
    cin >> k;

        /*
    dp[i][0]은 매우 큰 점프를 쓰지 않고 온 경우이다.
    이 경우는 두가지 경로로 i번째까지 올 수 있는데
    1. i-1번째에서 작은 점프 + i-1번째까지의 값
    2. i-2번째에서 큰 점프 + i-2번째까지의 값
    두가지 경우 중에서 최소값을 저장한다.


    dp[i][1]은 매우 큰 점프를 i번째에 쓰고 온 경우이다.
    이 경우 또한 두가지 경로로 i번째까지 올 수 있는데
    1. 매우 큰 점프를 써서(k) i번째에 도달한 경우
    2. i번째에 도달하기까진 다른 점프를 써서 오고, 그 전에 매우 큰 점프를 사용한 경우
    두가지 경우 중에서 최소값을 저장한다.

    이 중 2번째는 또 다시 경우의 수가 두가지로 나눠지는데,
    이는 dp[i][0]을 구하는 방법과 같은 경우의 수이다.
    1. i-1번째에서 작은 점프 + i-1번째까지의 값
    2. i-2번째에서 큰 점프 + i-2번째까지의 값
    다른 점은 그 전에 매우 큰 점프를 사용한 경우이므로 dp[?][1]의 값을 참조한다.
    */

    int dp[21][2];
    for (int i = 0; i <= n; i++) {
        dp[i][0] = MAX;
        dp[i][1] = MAX;
    }

    dp[1][0] = 0;
    dp[2][0] = energy[1].first;
    dp[3][0] = min(energy[1].first + energy[2].first, energy[1].second);
    
    // 큰 점프를 쓸 수 있는 4번째 부터 n까지 반복문을 시작한다.
    for(int i=4; i<=n; i++) {
        dp[i][0] = min(energy[i-1].first + dp[i-1][0],
                       energy[i-2].second + dp[i-2][0]);
        //cout << "dp[" << i-3 << "][0]" << dp[i-3][0] << endl;
        dp[i][1] = min(k + dp[i-3][0],
                       min(energy[i-1].first + dp[i-1][1],
                           energy[i-2].second + dp[i-2][1]));
    }

    cout << min(dp[n][0], dp[n][1]);


    return 0;
}

 

 

 

 

 

[Reference]

https://ansohxxn.github.io/algorithm/dp/

https://www.interviewbit.com/blog/difference-between-divide-and-conquer-and-dynamic-programming/