동적 계획법

개요

Dynamic Programming; DP

특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다. 동적 계획법은 "어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는" 방식의 알고리즘을 총칭한다. 답을 구하기 위해서 했던 계산을 또 하고 또 하고 계속해야하는 류의 문제의 구조를 Optimal Substructure라고 부른다. 동적 계획법은 이런 문제에서 효과를 발휘한다. 동적 계획법을 영문으로는 다이나믹 프로그래밍(dynamic programming)이라 표기하는데, 이름과는 달리 딱히 다이나믹하지도 않고 프로그래밍이라는 단어와도 큰 연관이 없다. 사실 동적 계획법은 다른 널리 알려진 이름으로는 Memoization즉 메모이제이션이라는 이름으로 불리기도 한다.

구현

동적 계획법의 접근 방식은 기본적으로 분할 정복 알고리즘과 비슷하다. 위에서도 설명했지만 동적 계획법을 사용하는 알고리즘 역시 주어진 문제를 부분 문제로 나누어 각 부분 문제의 답을 계산하고, 이 계산한 결과값을 이용해 원래 문제의 답을 산출하기 때문이다. 여기서 분할정복과 차이가 생기는 부분은 원래의 문제를 부분 문제로 나누는 방식에 있다. 동적 계획법의 경우 주어진 문제를 나눌 때 부분 문제를 최대한 많이 이용하도록 나눈 다음, 주어진 부분 문제의 정답을 한 번만 계산하고 저장해둔 뒤 다시 한 번 이 부분 문제를 이용할 때에는 저장해둔 정답을 바로 산출하여 이용함으로써 속도를 향상시킨다.

예

접근

동적 계획법의 개념과 구현에 대해 정확하게 짚고 넘어가기 위해 동적 계획법을 적용시킬 수 있는 예에 대해 알아보자.

* 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

위와 같이 정의된 함수에서 주어진 임의의 a,b에 대해 f(a,b)의 값을 효율적으로 구하고자 할 때 동적 계획법을 적용시킬 수 있다.

순서대로 계산횟수를 구해보면 f(2,2)를 구하기 위해 총 5번의 연산을 거쳐야한다. 이 때 중복되는 부분 문제[* overlapping subproblems - 두 번 이상 계산되는 부분 문제]에 대한 답을 미리 계산해놓고 연산한다고 가정했을 때 계산횟수를 구해보면 f(2,2)를 구하기 위해 4번의 연산을 거쳐야한다. 이 경우 간단한 예라 중복되는 부분 문제가 f(1,1) 하나 뿐이기 때문에 큰 속도의 이득을 볼 수 없지만 a,b의 값이 커질 수록 속도 면에서 엄청난 이득을 볼 수 있다. 실제로 a,b가 1증가할 때마다 연산 횟수는 기하급수적으로 증가하며, 이 때 중복되는 부분 문제를 적절히 처리해줌으로써 높은 계산효율을 얻을 수 있는 것이다.

예

LIS

LIS 란 최장 증가 부분수열을 구하는 문제이다. 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다. 예를 들어 다음 수열이 주어졌다고 하자.

3 5 7 9 2 1 4 8

위 수열에서 몇 개의 수를 제거해 부분수열을 만들 수 있다.

3 7 9 1 4 8 (5, 2 제거) 7 9 1 8 (3, 5, 2, 4 제거) 3 5 7 8 (9, 2, 1, 4 제거) 1 4 8 (3, 5, 7, 9, 2 제거)

이들 중 세번째, 네번째 수열은 오름차순으로 정렬되어 있다. 이들을 '증가 부분 수열'이라고 한다.

그리고 이런 증가 부분 수열 중 가장 긴 수열을 '최장 증가 부분 수열 (LIS)'이라 한다. 부분수열 3 5 7 8은 LIS이다.

한 수열에서 여러 개의 LIS가 나올 수도 있다. 예를 들어 수열

5 1 6 2 7 3 8

에서 부분수열

1 2 3 8 5 6 7 8

은 모두 길이가 4인 LIS이다.

 #include <iostream>
 #include <algorithm>

 using namespace std;

 int N;

 int main(void) {

    cin >> N;

    int* arr = new int[N];
    int* mem = new int[N];

    for(int i=0;i<N;i++) {
        cin >> arr[i];
        mem[i] = 1;
    }

    for(int i=1;i<N;i++) {
        for(int j=0;j<i;j++) {
            if(arr[j] < arr[i] && mem[i] <= mem[j]) {
                mem[i] = mem[j] + 1;
            }
        }
    }

    sort(mem,mem + N);

    printf("%d\n",mem[N-1]);

    delete[] arr;
    return 0;
 }