다이나믹 프로그래밍

 

 

다이나믹 프로그래밍은 한마디로 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘이다

큰 문제를 작은 문제로 나눠서 계산하는데, 작은 문제의 결과를 메모리에 저장하여 다시 계산하지 않도록 한다

 

다이나믹 프로그래밍은 문제가 다음의 조건을 만족할 때 사용할 수 있다고 함

1) 최적 부분 구조 : 큰 문제를 작은 문제로 나누고, 작은 문제의 답을 모아서 큰 문제를 해결

2) 중복 부분 문제 : 동일한 작은 문제를 반복적으로 해결해야할 때

 

가장 대표적인 예시로는 피보나치 수열이 있다

 

 

int fibo(int num){
  if(n <= 1) return n;
  else return fino(n - 1) + fibo(n - 2);
}

 

위는 재귀함수를 통해 구현한 피보나치 수열 코드다

f(5)는 f(4)+f(3), f(4)는 f(3)+f(2), f(3)은 f(2)+f(1)

겹치는 호출을 하는 비효율적인 코드임을 알 수 있다

 

 

int dp[100] = { 0, };
 
int fibo(int n){
    //종료조건
    if (n <= 2)
        return 1;
    
    //이미 저장된 값 존재
    if (dp[n] != 0)
        return dp[n];
    
    //저장된 값 X
    dp[n] = fibo[n - 1] + fibo[n - 2];
    return dp[n];
}

위는 피보나치를 DP로 구현한 코드이다

결과값을 dp[n]에 저장하여 이미 계산된 값은 다시 계산하지 않아도 된다

 

이렇게 한 번 구한 결과를 메모리 공간에 저장하여

같은 식을 다시 호출했을 때 저장해둔 결과를 그대로 가져오는 기법을 메모이제이션이라고 한다

 

함수가 종료될 때까지 실제로 호출된 함수는 아래와 같다

 

 

훨씬 빠를 것 같다

 

 

위와 같이 재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법을,

큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운(Top-Down) 방식이라고 한다

반대로 바텀업(Bottom-Up) 방식은 반복문을 이용하여 소스코드를 작성하는 경우

작은 문제부터 차근차근 답을 도출하는 것을 말한다

 

 

int dp[100] = {0, };
 
dp[1] = 1;
dp[2] = 1;
n = 5;
 
for (int i = 3; i <= n; i++){
    dp[i] = dp[i - 1] + dp[i - 2];
}

 

바텀업 방식으로 피보나치를 구현한 코드다

결과 저장용으로 사용되는 리스트 dp는 DP 테이블 이라고 부른다 함

 

탑다운 방식보다는 바텀업 방식을 많이 사용한다고 한다

아니 그러는 편이 좋다고 한다~~

 

---

추가로 백준에서 풀 수 있는 DP 문제!

예전에 풀었던건데 글을 안썼네..

 

 

N은 100,000 보다 작거나 같다고 한다

수의 범위는 큰데 시간 제한이 있는 문제다

세상이 이렇다.. 할 일은 많은데 시간은 없다

 

N=10 일 때

10 > 5 > 4 > 2 > 1

10 > 9 > 3 > 1

두 가지 경우를 찾을 수 있다

수가 커졌을 때 이렇게 모든 경우를 찾으려면 답도 없다

이딴식으로는 제공된 시간 0.15초 안에 답을 출력해줄 수 없다

 

DP스럽게 풀어 보자

N = 2, 3일 때 답은 1이다

8일 때는? 8 > 4 > 2 > 1의 과정을 통해 답은 3이 된다

 

이 때 2의 답은 1이라고 DP 테이블에 저장해뒀다면 계산이 좀 더 빨랐을 것이다

4일 때 답이 2인 것도 저장해뒀다면 매우 빨랐을 것이다

 

이렇게 1부터 N까지 차례대로 dp테이블에 값을 저장해두고

마지막에 dp[n]을 출력하면 계산이 뒤집어지게 빠르다

 

자세한건 코드를 보면 이해가 빠르다

 

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int dp[1000001] = {};
 
 
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int n;
    cin >> n;
 
    dp[0] = dp[1] = 0;
 
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + 1;
 
        if (i % 2 == 0) dp[i] = min(dp[i], dp[i / 2] + 1);
        if (i % 3 == 0) dp[i] = min(dp[i], dp[i / 3] + 1);
    }
 
    cout << dp[n] << '\n';
}