동적 계획법

1. 개요

2. 구현

2.1. 접근

• f(a,b) = f(a-1,b) + f(a,b-1) (a,b >= 1 )
• f(0,0) = 1, 임의의 자연수 n에 대해 f(n,0) = f(0,n) = 1

2.2. 예시

2.2.1. 재귀함수 형태의 피보나치 수열

f(0) = 1
f(1) = 1
f(n) = f(n-1) + f(n-2) when n > 1

#!syntax cpp
int f(unsigned int n)
{
    if(n <= 1)
        return 1;
    else
        return f(n-1)+f(n-2);
}

2.2.2. 동적 계획법 형태의 피보나치 수열

#!syntax cpp
int memo[100]; //메모이제이션 공간. 전역 변수이므로 0으로 초기화
int fibonacci(unsigned int n)
{
    if (n <= 1)  //0번째, 1번째 피보나치 수
        return n;
    
    if (memo[n]!=0)  //메모가 있는지 확인(0으로 초기화되었으므로 0이 아니라면 메모가 쓰인 것임)
        return memo[n]; //메모 리턴
    
    memo[n] = fibonacci(n-1) + fibonacci(n-2); //작은 문제로 분할

    return memo[n];
}

#!syntax cpp
int f_data[N] = {1, 1}; // N은 정의하기 나름
int last_pos = 1; // 마지막으로 계산한 지점. 이 코드에선 이미 f_data[1]까지 정의되어있기 때문에 1로 초기화한다.
int f(int n) //피보나치 수열의 제 n항을 구한다. 배열의 관점에서는 n-1번째 요소를 구하는 것.
{
    int i;
    if(f_data[n-1] == 0)  // f(n)을 아직 구한 적이 없다면 구한다
    {
        for(i=last_pos+1; i < n; ++i)
        {
            f_data[i] = f_data[i-1] + f_data[i-2];
        }
        last_pos = n-1;
    }
    return f_data[n-1];
}

[JavaScript]

#!syntax javascript
function fibonacci(n) {
   function fibHelp(lastTwo, x) {
      const sum = lastTwo[0] + lastTwo[1];
      return x == 2 ? sum : fibHelp([lastTwo[1], sum], x - 1);
   }
   return n < 2 ? n : fibHelp([0, 1], n);
}

bottom-up, 혹은 tabulation이라고 하는 방법. 시간복잡도는 O(n), 공간복잡도는 O(1)다. 사실 F(n)을 찾으려면 F(n - 1)와 F(n - 2)만을 기억하고 있으면 되므로 숫자 2개를 가지고 있는 리스트만 있으면 된다.

2.3. 메모이제이션

3. 기타

• 3항 이상의 재귀 수열
• 0-1 배낭 문제(0-1 Knapsack Problem): 견딜 수 있는 무게가 제한된 배낭에 가장 많은 가치의 물건을 넣기. 모든 무게를 정수로 볼 수 있다면, 배낭의 최대 무게 W일 때 O(W)로 구할 수 있다. 그게 아닌 경우라면 NP-hard이므로 근사 알고리즘을 써야 한다. 비슷한 것으로 Rational Knapsack Problem이 존재하는데, 이는 보통 그리디 알고리즘으로 사용된다. 0-1 Knapsack과 다른 점은 단순히 물건을 넣느냐 빼느냐가 아니라, 잘라서 (일부분만) 넣을 수 있게 하는 것이다.
• 가장 긴 증가 수열 문제(LIS Problem): 아무 수열이나 주고, 순서를 바꾸지 않은 상태로 뽑아서 만들 수 있는 가장 긴 증가수열의 길이 구하기. O(N²)이며, 이진 탐색을 사용할 줄 안다면 O(NlogN)으로도 줄일 수 있다.
• 연쇄 행렬 곱셈 문제: 주어진 연쇄행렬들의 곱셈을 각 원소의 곱셈 횟수를 최소로 할 수 있는 행렬곱셈의 순서를 찾는 최적화 문제이다. 동적 계획법과 메모이제이션을 적용할 수 있는 대표적인 알고리즘들 중 하나이다.
• 그래프 상의 최단거리 문제 - 벨먼-포드 알고리즘, 플로이드-워셜 알고리즘: 점 개수가 V일 때 O(V³)으로 구할 수 있다. Floyd-Warshall은 모든 출발점과 도착점에 대해 최단거리를 구할 수 있고, Bellman-Ford는 거리 합이 음수인 사이클이 있을 때에 대해서도 구할 수 있다. (다익스트라 알고리즘은 일종의 BFS이다.)