[알고리즘] 동적 계획법(DP) - 코딩밥상

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

 동적 계획법이란 어떤 문제가 여러 단계의 반복되는 부분 문제로 이루어졌을 때, 각 단계에 있는 부분 문제의 답을 기반으로 전체 문제의 답을 구하는 방법을 말합니다.

 앞서 배운 분할 정복은 문제를 위에서부터 아래로 쪼개지만(Top-Down), 동적 계획법은 제일 작은 부분 문제부터 상위에 있는 문제로 풀어 올라갑니다(Bottom-Up). 또한 분할 정복 기법으로 쪼갠 각 부분 문제는 완전히 독립적인 문제로 다룰 수 있지만, 동적 계획법에서 각 단계에 있는 부분 문제들은 그 이전 단계에 있는 문제들의 답에 의존합니다.

 

 무엇보다 동적 계획법은 분할 정복과 달리 한 번 푼 적 있는 부분 문제의 답을 다시 푸는 일이 없도록 테이블 등에 저장합니다.

저장하는 부분이 없으면 부분 문제들의 답을 수없이 반복해서 다시 구하는 일이 생길 수도 있기 때문입니다.

 

동적 계획법으로 설계된 알고리즘의 동작 방식은 다음 세 단계로 정리됩니다.

1. 문제를 부분 문제로 나눈다
2. 가장 작은 부분 문제부터 해를 구한 뒤 테이블에 저장한다
3. 테이블에 저장된 부분 문제의 해를 이용하여 점차적으로 상위 부분 문제의 최적해를 구한다

 

 동적 계획법으로 풀 수 있는 문제는 한정되어있는데, 바로 그 문제가 '최적 부분 구조(Optimal Substruct)'를 갖추어야 합니다.

최적 부분 구조란 전체 문제의 최적해가 부분 문제의 최적해로부터 만들어지는 구조를 말합니다.

예를들어 5개의 작은 문제로 쪼갤 수 있는 어떤 문제가 있고 쪼개진 문제의 해 5개를 모두 얻어야 이 문제의 해를 구할 수 있다면 이 문제는 최적 부분 구조를 갖추었다고 할 수 있습니다. 좀 더 직관적으로는 '점화식'을 세울 수 있는 문제이면 됩니다.

 

더욱 자세한 예시로 앞서 분할 정복으로도 해결해보았던 피보나치에 대해 적용해 보겠습니다.

 

동적 계획법 기반 피보나치 수열

 피보나치 수는 선행되는 피보나치 수를 구해야 다음 피보나치 수를 구할 수 있기때문에 최적 부분 구조를 갖추었다고 할 수 있습니다.

long Fibonacci(int n){
    if(n==0) return 0;
    
    if(n==1 || n==2) return 1;
    
    return Fibonacci(n-1) + Fibonacci(n-2);
}

 다음과 같이 피보나치를 가장 쉽게 구현하는 방법은 Fibonacci(n-1) + Fibonacci(n-2) 처럼 함수를 재귀 호출 해서 구현하는 방법입니다.

하지만 이 방법은 O(2^n)으로 성능면에서는 형편 없습니다. 그 이유도 이미 알고 있습니다. 부분 피보나치 수를 얻기 위한 중복 계산이 수없이 이루어지기 때문입니다.

 

이를 동적 계획법으로 생각하면, Fibonacci(n)함수는 Fibonacci(n-1) 과 Fibonacci(n-2)의 합입니다. Fibonacci(n-1)은 Fibonacci(n-2) 와 Fibonacci(n-3)의 합이고요. 즉 부분 집합으로 나뉜다는 것을 알 수 있습니다.

각 결과값들을 테이블에 저장해 놓는 것입니다. 각각의 결과값들을 테이블에 저장해 나아가면 구하고자 하는 n번째 요소의 Fibonacci(n)의 결과 값에 도달 할 수 있게 됩니다.

이를 성능면에서 살펴보면, 어떠한 중복 계산 없이 기존 테이블 값에 의존해 한 번의 연산으로 다음 값을 얻을 수 있기 때문에 O(n)입니다.

long Fibonacci(int n){
    long result;
    long* FibonacciTable;
    
    if(n==0 || n==1) return n;
    
    FibonacciTable = (long*)malloc(sizeof(long) * (n+1));
    
    FibonacciTable[0] = 0;
    FibonacciTable[1] = 1;
    
    for(int i=2; i<=n; i++){
        FibonacciTable[i] = FibonacciTable[i-1] + FibonacciTable[i-2];
    }
    
    result = FibonacciTable[n];
    
    free(FibonacciTable);
    
    return result;
}