동적 계획법

개요

Dynamic Programming; DP

특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다. 동적 계획법은 "어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는" 방식의 알고리즘을 총칭한다. 답을 구하기 위해서 했던 계산을 또 하고 또 하고 계속해야하는 류의 문제의 구조를 Optimal Substructure라고 부른다. 동적 계획법은 이런 문제에서 효과를 발휘한다. 동적 계획법을 영문으로는 다이나믹 프로그래밍(dynamic programming)이라 표기하는데, 이름과는 달리 딱히 다이나믹하지도 않고 프로그래밍이라는 단어와도 큰 연관이 없다. 이에 대해 이광근 교수의 저서 "컴퓨터 과학이 여는 세계"에서는 다이나믹 프로그래밍을 본질적인 의미를 더 살려서 기억하며 풀기로 더욱 적절하게 번역하였다.

구현

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

예

접근

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

* 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;
}