동적 계획법(Dynamic Programming)

동적 계획법(Dynamic Programming), 줄여서 DP는 메모리 공간을 약간 더 사용하여 연산 속도를
타 알고리즘과 비교해 비약적으로 상승시킬 수 있는 프로그래밍 기법으로 크게 탑다운(Top-down) 방식과
바텀업(Bottom-up) 방식으로 나눌 수 있다. 추가로 DP를 위해 자주 사용되는 메모이제이션 기법에 대하여 알아보도록 하겠다.

1. 피보나치 수열

다이나믹 프로그래밍을 이용하여 문제를 해결할 때 확연하게 성능적 향샹을 보이는 대표적 예시로,
피보나치 수열이 있다. 피보나치 수열은 이전 두항의 합을 현재의 항으로 설정하는 특징의 수열이다.

이러한 피보나치 수열은 아래와 같은 점화식으로 나타낼 수 있다.

a_n+2 = f(a_n+1, a_n) = a_n+1 + a_n

피보나치 수열은 1항과 2항이 모두 1이기에 각 원소가
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... 인 수열이 된다.

이러한 수학적 점화식은 재귀 함수를 이용하여 표현할 수 있는데 다음 코드는 C++언어로 표현한 피보나치 수열이다.

void fibo(int x){
    if (x == 1 || x==2){
        return 1;
    }

    return fibo(x-1) + fibo(x-2);
}

재귀함수를 이용하여 표현한 피보나치 수열은 그냥 보기엔 이상이 없어 보이지만
x값이 커질 수록 심각한 문제가 발생할 수 있다. 이는 x값이 커지면 코드의 수행 시간이 기하급수적으로 늘어나기 때문인데
해당 fibo함수의 시간 복잡도를 빅오 표기법으로 나타내면 O(2^N)이 되고 이는 지수 시간이 소요된다는 것을 알 수 있다.

fibo함수를 f라 하고 x의 값을 6이라 할 때, 함수 f의 호출과정은 아래와 같다.

그래프를 보면 동일 함수가 반복적으로 호출되는 것을 확인할 수 있는데, 이는 한 번 계산한 함수를 중복적으로
계속 호출할 때 마다 계산하게 된다. 그래프에서 f(3) 함수는 3번 호출되었다. 즉 x의 값이 커질 수록 반복 호출이 더 많이 일어나게 된다.

이렇게 매번 계산을 반복하여 재귀함수로 문제를 해결하면, 계산량이 너무 늘어나 시간적으로 오랜 시간이 걸린다.
이를 다이나믹 프로그래밍으로 해결하면 훨씬 효율적으로 문제를 해결할 수 있다.

다만, 다이나믹 프로그래밍을 할 때는 몇 가지 주의해야 할 점이 있다.

2. 메모이제이션

이제 피보나치 수열을 메모이제이션 기법을 활용한 다이나믹 프로그래밍으로 해결하여 보겠다.
메모이제이션 기법은, 다이나믹 프로그래밍 구현 방법 중 하나로
한 번 구한 결과를 메모리 공간에 저장해두고 다시 호출할 때 저장된 결과를 가져오는 방식이다.

long long fibo(int x, vector<long long>& v){
    if (x <= 1) return 1;
    if (v[x] != 0) return v[x];
    v[x] = fibo(x-1, v) + fibo(x-2, v);
    return v[x];
}

int main(){
    vector<long long> v(100);
    int n = 92;
    for (int i = 0; i < n; i++){
        cout << fibo(i, v) << " ";
    }
}

위 코드에서 vector v에 0으로 초기화한 100개의 공간을 미리 만드는데, 이 벡터가 바로 메모이제이션 용도의 벡터이다.

fibo함수에 값을 넘겨줄 때, 원하고자 하는 수열의 항 n값과 벡터 v를 넘겨준다.

이때 벡터는 재귀호출 시 같은 벡터를 가리킬 수 있게 참조로 인자를 넘겨준다.

이후 n값을 받아와 fibo함수를 재귀 호출하며 수열을 계산한다.

main함수에서 for문을 사용해 벡터를 순회하면 피보나치 수열을 얻을 수 있다.

단, long long값이 나타낼 수 있는 정수의 크기가 제한되기에
n = 92까지의 피보나치 수열을 계산할 수 있고, 더 큰 n값은 별도의 데이터 처리가 필요하다.

앞서 예로 들었던 f(6)의 경우를, 메모이제이션 기법을 활용한 다이나믹 프로그래밍 방식 피보나치 수열의 그래프로 보면

실질적 실행 함수의 수는 15 -> 4로 확연하게 줄어듦을 알 수 있다.
그럼에도 정확히 4개의 함수만 호출하는 것은 아니기에, n값이 클 때 오버헤드가 발생할 수 있다.

이러한 오버헤드를 줄이기 위해선, 재귀함수 대신 반복문을 사용하는 것이 좋다.
(일반적으로, 다이나믹 프로그래밍은 반복문을 이용한 것이 재귀함수를 이용한 것보다 더 성능이 좋다)

다이나믹 프로그래밍을 적용한 피보나치 수열 알고리즘의 시간 복잡도는 O(N)이다.

그 이유는 f(1)을 구한 값이 f(2)를 구하는데 사용되고, f(2)의 값이 f(3)을 구하는 것에 사용되기에
한 번 구한 결과는 다시 구해지지 않기 때문이다. 실제로 호출되는 함수에 대해서 확인하기 위해
아래와 같은 코드를 실행하여 보겠다.

long long fibo(int x, vector<long long>& v){
    cout << "f(" << x << ")" << " ";
    if (x == 1 || x == 2) return 1;
    if (v[x] != 0) return v[x];
    v[x] = fibo(x-1, v) + fibo(x-2, v);
    return v[x];
}

int main(){
    vector<long long int> v(200);
    int n = 6;
    fibo(n, v);
    cout << endl;
}

output

f(6) f(5) f(4) f(3) f(2) f(1) f(2) f(3) f(4) 

3. 탑다운, 바텀업

output에서 보이는 것처럼, 재귀 함수를 이용하여 다이나믹 프로그래밍을 작성하는 방법을
큰 문제를 해결하기 위해 작은 함수를 호출한다하여 탑다운(Top-down) 방식이라 한다.

반대로 단순히 반복문을 이용하여 다이나믹 프로그래밍으로 문제를 해결하는 방식을
작은 문제부터 답을 도출한다하여 바텀업(Bottom-up) 방식이라고 말한다.

바텀업 방식의 반복문 활용 다이나믹 프로그래밍을 이용한 피보나치 수열의 코드는 아래와 같다.

int main(){
    vector<long long> v(100);
    v[0] = 1;
    v[1] = 1;
    int n = 6;
    for (int i = 2; i < n; i++){
        v[i] = v[i-1] + v[i-2];
    }

    for (long long i : v){
        if(i != 0) cout << i << " ";
        }
    cout << endl;
}

output

1 1 2 3 5 8

4. DP 테이블

탑다운 방식은 하향식이라고도 하며, 바텀업 방식은 상향식이라고도 한다.
다이나믹 프로그래밍의 전형적 형태는 바텀업 방식으로, 바텀업 방식에서 사용되는 결과 저장용 배열을 DP 테이블이라 부르며,
메모이제이션 기법은 탑 다운 방식에 국한되어 사용하는 표현이다.

• DP 테이블 - 바텀업
• 메모이제이션 - 탑다운

( 엄밀하게는 메모이제이션은 이전 계산 결과를 일시적으로 기록하는 넓은 개념이기에 다이나믹 프로그래밍과는 별도의 개념이다. )

다이나믹 프로그래밍은 조금의 메모리 공간을 추가로 사용하여, 시간 복잡도를 확연히 줄일 수 있는 프로그래밍 기법이다.
탑다운 방식보단 바텀업 방식이 권장되며( 시스템 상 재귀함수 스택 크기가 한정적일 수 있기 때문 )
최단 경로 알고리즘이나 플로이드 워셜 알고리즘 등 다양한 문제 해결 방식에 도움을 준다.