동적계획법(memoization)

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

 

처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산해 내는 분할 정복의 알고리즘과 비슷하지만

동적계획법의 각 부분 문제들은 다른 답을 구하는 이용될 수 있기 때문에 계산결과를 재활용함으로써 속도의 향상을 꾀한다.

 

부분 문제들의 답을 재활용한다는 말이 무슨 말일까?

 

피보나치 수열 문제로 예를 들어보자!

 

동적계획법을 이용한 피보나치 수열의 풀이

 

https://www.acmicpc.net/problem/2748

 

피보나치 수열은 다들 아는 것처럼 Fn = Fn-1 + Fn-2 (n>=2)의 점화식을 가지고 전개되는 수열이다.

0 1 1 2 3 5 8 13 21 34 .....

 

n번째 피보나치 수를 구하는 함수를 fibo라고 한다면, 아래와 같은 재귀함수로 구현할 수 있다.

 

#include <stdio.h>
 
long long fibo(int n)
{
    //0과 1은 예외 처리
    if (n == 0)
        return 0;
    if (n == 1)
        return 1;
    return fibo(n - 1) + fibo(n - 2);
}
 
int main()
{
    int n;
    scanf("%d", &n);
    printf("%lld", fibo(n));
}

하지만 이 코드를 제출하면 시간 초과가 뜬다! (아니 왜,,,?)

 

그건 똑같은 결과가 여러 번 사용되기 때문인데,, 간단하게 fibo(5)를 가져오면 fibo(5)를 구하기 위해 fibo(4)와 fibo(3)을 호출한다. fibo(4)는 fibo(3)과 fibo(2)를 fibo(3)은 fibo(2)와 fibo(1)을.......글로 보면 하나도 모르겠으니 아래 그림을 살펴보자

 

fibo(5) 호출 시 호출되는 함수들

fibo(2)만 살펴보아도 3번이나 호출되는 것을 알 수 있다. 그렇다면 fibo(2)를 처음 구했을 때 그 값을 기억하면 함수 속도가 더 빨라지겠지?

 

그 개념이 바로 메모이제이션(memoization)이다. 메모라이제이션(memorization)이 아니다.

 

아래와 같이 코드를 바꾸게 되면

 

#include <stdio.h>
 
// 미리 계산된 결과를 저장해 놓기 위한 배열
long long cache[91];
 
long long fibo(int n)
{
    //0과 1은 예외 처리
    if (n == 0)
        return 0;
    if (n == 1)
        return 1;
    //한 번 계산된 값이면 곧장 반환
    if (cache[n] != 0)
        return cache[n];
    // 아니라면 계산한 뒤 cache에 저장
    return cache[n] = fibo(n - 1) + fibo(n - 2);
}
 
int main()
{
    int n;
    scanf("%d", &n);
    printf("%lld", fibo(n));
}

시간 내에 풀 수 있게 된다!

 

동적계획법의 좀 더 다양한 예제는 다음에 한 번 써보겠습니다.

 

첫 포스팅은 여기까지!