문서 편집 권한이 없습니다. 다음 이유를 확인해주세요: 요청한 명령은 다음 권한을 가진 사용자에게 제한됩니다: 사용자. 문서의 원본을 보거나 복사할 수 있습니다. [[분류: 알고리즘 패러다임]] == 개요 == 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이다. <syntaxhighlight lang="c"> #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; } </syntaxhighlight> 동적 계획법 문서로 돌아갑니다.