동적 계획법(Dynamic Programming) 알고리즘

 동적 계획법 이름의 유래

수학, 컴퓨터 공학, 경제학에서 사용되는 문제풀이 방법.

리처드 벨만이 처음 이 단어를 사용했으며,

그의 자서전 '태풍의 눈'에서 다음과 같이 설명했다.

어떤 문제가 다단계로 이루어져 있으며,  // sub-structure

시간에 대해 가변적이고,  // time-varying

동적이다.  // dynamic

시간에 대해 가변적이라는 특성은, 

특히 경제학에서 주로 다뤄지는 것 같다.

 동적 계획법이란?

하나의 복잡한 문제를, 

동일한 구조의 간단한 문제들의 합으로 푸는 방법.

하나의 문제를, 그것과 동일한 형태의 작은 문제들로 나눈 뒤.

작은 문제들을 풀어내어 최종적인 문제에 접근하는 것이 그 목적이다.

또한 어떤 문제를 푸는 도중에, 작은 문제들의 결과값이 필요하다면,

작은 문제를 푸는 과정으로 진입하는데,

그 문제를 풀기위한 모든 작은 문제를 풀어야 하므로,

전역 탐색과 매우 유사하다.

 기저 (base case)

어떤 문제를 작은 문제들로 풀어낸다는 것은,

그 문제들의 레벨이 낮추어진다는 것을 의미한다.

다만,  레벨의 하한을 정하지 않는다면 어떻게 될까?

레벨이 정의되지 않은 영역으로 빠지게 될 것 이다.

레벨의 하한을 정하는 것을, 기저라고 하며,

문제가 정의되는 최소한의 케이스이라는 개념을 가지고 있다.

 메모이제이션 (memoization)

문제를 푸는 도중에,  여러개의 작은 문제들이 도출되는데.

이 문제들이 겹쳐지면 중복계산이 발생한다.

따라서, 한번 푼 문제는 중복하여 풀지 않도록 캐싱하는 작업을 추가한다.

이것을 메모이제이션이라고 하며, 잠시 결과값을 메모해둔다는 의미를 가지고 있다.

따라서 동적 계획법은, 겹쳐지는 작은 문제들이 

기하급수적으로 증가하는 문제에 대해 매우 효과적이다.

#include <bits/stdc++.h>
using namespace std;
using int64 = int64_t;

int64 cache[40];
int64 fibo(int x){
    //! 기저사항 (base condition)
    if(x == 0) return 0;
    if(x == 1) return 1;


    //! 이전에 풀었던 값이 있는가? (memoization)
    if(cache[x] != 0) return cache[x];


    //! 처음 푸는 문제.
    cache[x] = fibo(x-1) + fibo(x-2);
    return cache[x];
}

즉, 동적 계획법의 설계 방법은 다음과 같다.

1. 주어진 문제를 완전 탐색으로 푼다.
2. 중복된 부분 문제를 한 번만 계산하도록 메모이제이션을 적용한다.

 관점의 차이

동적 계획법으로 문제를 풀 때, 2가지의 관점이 존재한다.

• 큰 문제에서 시작해서 아래로 푼다.  (Top-down)
• 작은 문제에서 시작해서 위로 푼다.  (Bottom-up)

탑 다운 (Top-down)

• 큰 문제를 풀 때, 작은 문제를 계산하는 과정으로 빠진다.
• 재귀 형태로 풀린다.
• 중복계산 방지를 위한 메모이제이션이 필요하다.
• 부분 문제간 의존관계를 신경 쓸 필요가 없다.
• 슬라이딩 윈도 기법을 쓸 수 없다.
• 오버 플로우에 유의해야 한다.

#include <bits/stdc++.h>
using namespace std;
using int64 = int64_t;

int64 cache[40];
int64 fibo(int x){
    //! 기저사항 (base condition)
    if(x == 0) return 0;
    if(x == 1) return 1;


    //! 이전에 풀었던 값이 있는가? (memoization)
    if(cache[x] != 0) return cache[x];


    //! 처음 푸는 문제다.
    cache[x] = fibo(x-1) + fibo(x-2);
    return cache[x];
}

바텀 업 (Bottom-up)

• 아래 단계부터 풀어서, 목표 단계까지 접근한다.
• 반복문 형태로 풀린다.
• 점화식이 사용된다.
• 슬라이딩 윈도 기법을 쓸 수 있다.
• 부분 문제간 의존관계를 신경써야 한다.

#include <bits/stdc++.h>
using namespace std;
using int64 = int64_t;

int64 fibo[40];

int main() {
    int target = 21;

    fibo[0] = 0;
    fibo[1] = 1;
    
    for(auto i=2; i<=target; i++){
        // 점화식 f(n) = f(n-1) + f(n-2)
        fibo[i] = fibo[i-1] + fibo[i-2];
    }
    cout << fibo[target];
}

 경로 추적

일반적인 동적 계획법은 문제의 "답"을 계산하는 것 뿐이지,

어떻게 그 답에 도달했나 하는 "경로"는 고려하지 않는다.

답의 경로를 구하기 위해서는,

아래와 같은 과정을 거쳐야 한다.

1. 먼저, 답을 알아낸 뒤.

2. 메모이제이션된 기록을 바탕으로 경로를 계산한다.

 동적 계획법의 시간 복잡도 계산

동적 계획법에서의 시간 복잡도는 다음과 같이 정의된다.

O( 접근된 상태의 개수 * 각 상태마다 걸리는 시간 )

Q1 :

피보나치의 경우에는 다음과 같다.

• 접근된 상태의 개수 :  n

• 각 상태마다 소요시간 :  1

• 최종 시간 복잡도 :  O(n)

Q2 :

짝수인 경우 : /2

홀수인 경우 : -1

1 까지 몇 번의 단계를 거치는가?

e.g)  15 ->  7 -> 3 -> 1

• 접근된 상태의 개수 :  2*log n

• 각 상태마다 소요시간 :  1

• 최종 시간 복잡도 :  O(log n)