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

'코딩 테스트를 위한 자료 구조와 알고리즘 with C++' 를 참고하여 작성하였습니다.

1. 동적 계획법 ; dynamic programming

1.1 개념

분할 정복 패러다임 개념을 확장한 것으로, 큰 문제를 작은 문제로 나누어 푸는 문제를 일컫는 말이다. 언뜻 문제를 보면 비슷하다 생각될 수 있지만, 분할 정복과 구분되는 동적 계획법만의 특성은 다음과 같다.

 

1. 중복되는 부분 문제(overlapping subproblem)

2. 최적 부분 구조(optimal substructure)

 

다음과 같은 속성을 만족해야 동적 계획법을 통해 문제를 해결할 수 있다. 전체 문제가 독립적인 부분 문제로 나뉘는 분할 정복 문제와 달리 동적 계획법에서는 중복되는 부분 문제가 반복적으로 등장한다. 또한 최적 부분 구조를 가져 부분 문제의 최적의 답을 이용하여 전체 문제에 대한 최적의 답을 표현할 수 있다.

---

가장 간단한 예시를 들어보자. 재귀 함수를 배울 때 가장 먼저 배우는 피보나치 수열을 떠올릴 수 있다.

{ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... } 와 같은 순서를 가지는 수열을 피보나치 수열이라고 한다. 여기서 우리 모두가 알고 있는 규칙을 찾아보면 다음과 같다.

 

F(0) = 0

F(1) = 1

..

F(n) = F(n - 1) + F(n - 2)

 

F(n)은 이전 원소 두 개(F(n-1), F(n-2))에 의해 결정되고, F(n) = F(n - 1) + F(n - 2) 와 같이 표현되는 수식은 이 수열의 재귀 관계(recurrence relation) 가 된다. 

F(5)를 구하는 구조를 그림으로 표현하면 다음과 같다.

피보나치 수열에서 F(5) 계산하기

위의 재귀 트리에서 F(4) = F(3) + F(2)이고, F(3) = F(2) + F(1) 이기 때문에 F(2)는 F(4)와 F(3)을 구하는 과정에서 여러 번 등장한다. 이를 통해 중복되는 부분 문제를 확인할 수 있다.

또한 F(2)는 F(4)를 구하는 과정에서도, F(3)을 구하는 과정에서도 사용이 된다. F(4)를 구하기 위해 이전에 구해두었을 F(2)를 다시 사용할 수 있으므로 최적 부분 구조를 만족한다.

 

1.2 접근방법

접근 방법은 크게 캐시(cache)에 기록하는 하향식 접근방법(top-down approach)과 표를 만들어 저장하는 상향식 접근방법(bottom-up approach)으로 나눌 수 있다.

 

1.2.1 메모이제이션 ; 하향식 접근 방법

메모를 한다는 뜻의 메모이제이션(memoization)은 각 단계마다 부분 문제의 해답을 찾으면 배열 구조의 캐시에 저장한다. 캐시에 값이 저장되어 있는지 여부를 확인하여 저장되어 있다면 저장된 값을 반환한다. 쉽게 생각하면 재귀 함수를 통해 위에서부터 계산해 나가는 방식이 이에 해당한다. 

 

1.2.2 타뷸레이션 ; 상향식 접근 방법

테이블에 정리한다는 의미의 타뷸레이션(tabulation)은 모든 부분 문제에 대한 해답을 표에 저장한 후 재사용하는 방식이다. 반복문을 통해 부분 문제에 대한 해답을 저장해나가는 방식으로 메모리 사용이 효율적이고, 가능한 모든 상태를 기록하기 때문에 임의의 여러 상태를 참조하는 문제를 쉽게 해결할 수 있다.

---

타뷸레이션을 더 많이 사용하긴 하지만, 메모이제이션으로 해결할 수 있는 대부분의 문제는 타뷸레이션으로 해결할 수 있고, 그 반대 역시 가능하다. 피보나치 수열을 예를 들어보자.

우리가 일반적으로 알고 있는 재귀를 이용한 피보나치 수열 함수는 다음과 같다.

int Fibonacci(int n) {
    if(n < 2) return n;
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

위의 함수를 넣어 코드를 실행한다면, n에 조금만 큰 수가 들어가도 답이 나오는 데 굉장히 오래걸리는 것을 알 수 있다. 이는 위 함수의 시간복잡도가 O(2^n)이기 때문이다. 따라서 앞서 설명한 두 접근 방법을 이용하여 풀어보도록 한다.

 

#1. 메모이제이션

#define MAX 101

vector<int> memo(MAX, -1);

int DP(int num) {
    if(num < 2) return num;		// 기저상태 설정
    if(memo[num] > 0) return memo[num];
    
    int result = DP(n - 1) + DP(n - 2);
    memo[num] = result;
    return result;
}

 

#2. 타뷸레이션

int DP(int num) {
    vector<int> table(num + 1, 0);
    table[1] = 1;		// 기저상태 설정
    
    for(int i = 2; i <= num; i++) {
        table[i] = table[i - 1] + table[i - 2];
    }
    
    return table[num];
}