[알고리즘] 4. 동적 계획법(Dynamic Programming)

"이미 알고있는 답은 또 구하지 않는다"

 

사실 전혀 다이나믹하지 않고, 프로그래밍이라고 하기에도 애매하다. 벨만이라는 수학자가 펀딩을 잘 받기 위해서, 눈에 띄는 이름을 지은 것이다.  이광근 교수님의 저서 "컴퓨터과학이 여는 세계"에서는 '기억하며 풀기'라는 이름이 쓰였다.

 

하나의 큰 문제를 작은 문제로 나누어서, 그 결과를 얻고, 큰 문제의 답을 구하는 방식이다. "분할 정복법"과도 유사하다.

 

다이나믹 프로그래밍에는 두 가지 방법이 있다:

종류	메모이제이션	타뷸레이션
과정	하향식(Top down)	상향식(Bottom up)
구현	재귀 함수	반복문
장점	직관적이다	시간을 더 아낄 수도 있다
단점	재귀함수의 호출이 잦아 느려질 수 있다.	DP테이블을 잘 채워야 한다.
기타	Lazy - Evaluation	Eager - Evaluation

 

메모이제이션

구한 답을 캐시에 저장하고, 다음에 같은 경우가 생겼을 때, 다시 꺼내서 쓰는 방법이다.

사용된 부분만 캐시에 저장되어서 필요한 부분만 구하는 방법이다.

 

 

타뷸레이션

부분 문제들의 모든 답을 다 구하는 방법이다.

필요하지 않은 부분들도 모두 구한다.

 

예시 - 피보나치 수열을 다이나믹 프로그래밍으로 속도 빠르게 하기

#include <iostream>

long long cache[1000];
long long output;
long long times;

long long fibo_with_dp(long long num)
{
    times++;
    if (num == 1 || num == 2)
    {
        return 1;
    }
    if (cache[num] != -1)
    {
        return cache[num];
    }
    output = fibo_with_dp(num - 1) + fibo_with_dp(num - 2);
    cache[num] = output;
    return output;
}
long long fibo(long long num)
{
    times++;
    if (num == 1 || num == 2)
    {
        return 1;
    }
    return fibo(num - 1) + fibo(num - 2);
}

int main()
{
    // main 함수에서 cache 배열 초기화
    std::memset(cache, -1, sizeof(cache));
    times = 0;
    std::cout << fibo(50) << std::endl;
    std::cout << "재귀 횟수: " << times << std::endl;
    times = 0;
    std::cout << fibo_with_dp(50) << std::endl;
    std::cout << "재귀 횟수: " << times << std::endl;
    return 0;
}

 

12586269025
재귀 횟수: 25172538049
12586269025
재귀 횟수: 97

메모이제이션 방법을 사용한 피보나치 수열의 구현이다. 순수하게 재귀 함수만을 사용하는 방법은, int범위를 한참 넘어서는 재귀 호출을 보여준다. 반면, 한번 구한 답을 또 구하지 않고, 캐시에 메모이제이션 했다가 다시 찾는 fibo_with_dp()함수는 단 97번의 재귀만 사용하였다.