[알고리즘] 동적 계획법(Dynamic Programming) - 기본

동적 계획법(Dynamic Programming) 짧게 줄여서 DP 라고 부르는 이 알고리즘은 분할정복(Divide and Conquer) 알고리즘과 마찬가지로 복잡한 문제를 여러 개의 부분 문제들(Sub-problem) 으로 나누어 푼 후, 그 결과를 이용하여 복잡한 문제를 푸는 알고리즘이다.

다만 분할정복 알고리즘과의 차이는 DP 에서는 각 부분 문제들간에 겹치는 부분이 존재한다는 것인데, DP 는 이러한 겹치는 부분들을 메모이제이션(Memoization) 이라는 기법을 사용하여 단 한 번만 계산하도록 함으로써 알고리즘의 작동 시간을 줄이는 게 핵심입니다.

 

 

그렇다면 메모이제이션이라는 것은 무엇인지 알아봅시다.

 

피보나치 수열을 예로 들면,

아래와 같이 Fib(0) ~ Fib(3) 은 동일한 값을 구하는 연산이 중복되어 나타나 시간의 낭비가 생기는 것을 알 수 있습니다.

 

이러한 낭비를 줄이기 위해 사용하는 방법이 메모이제이션입니다. 한 번 계산한 값은 메모리에 저장해두고 필요할 때 꺼내쓸 수 있도록 하여 연산의 중복을 줄이는 것입니다.

 

이러한 메모이제이션을 이용하여 피보나치 수열을 구현하면,

int Fibonacci(int n){
    if (n == 0) return 0;
    if (n == 1) return 1;
    
    // 이미 계산한 값을 가지고 있으면 더이상 진행하지 않고 해당 값을 리턴
    if (seq[n] != -1) return seq[n];
    
    seq[n] = Fibonacci(n-1) + Fibonacci(n-2);
    return seq[n];
}

위와 같이 구현할 수 있습니다.

벡터의 초기화는 피보나치 수열에서 계산의 결과값으로 나올 수 없는 값인 -1로 해주었습니다.

 

이처럼 메모이제이션을 사용하여 피보나치 수열을 구하는 알고리즘은 각 n 마다 하나의 값들을 구하면 되므로 O(n) 으로 일반적인 재귀형 알고리즘으로 피보나치 수열을 구현하였을 때 지수형 시간복잡도가 나오는 것과 비교하여 보면 매우 효과적이라고 볼 수 있습니다.