[세호/week3] 동적 계획법

동적 계획법

동적 계획법은 큰 의미에서 분할 정복과 같은 접근 방식이다. 다만, 동적 계획법에서의 어떤 부분문제는 두 개 이상의 문제를 푸는데 사용될 수 있다. 그래서 그 부분문제의 답을 한번만 계산하고 저장해 두었다가, 나중에 같은 부분 문제를 풀 때 사용한다.  이때 결과 값을 저장해 두는 장소를 캐시(Cache)라고 한다.  

Example : 이항 계수의 계산

 nCr = n-1Cr-1 + n-1Cr 과 같이 표현될 수 있다.

 5C3 = 4C2 + 4C3 이고 4C2 = 3C1 + 3C2 3C1 = 2C0 + 2C1 3C2 = 2C1 + 2C2 2C1 = 1C0 + 1C1; 2C2 = 1   4C3 = 3C2 + 3C3 3C2 = 2C1 + 2C2 2C1 = 1C0 + 1C1; 2C2 = 1 3C3 = 1

위 계산 과정에서 보듯이 같은 이항계수의 계산이 여러번 호출되는 것을 알 수 있다. 따라서 각 이항 계수를 계산한 뒤에 캐시에 저장하였다가 다음 호출시에는 캐시에서 바로 꺼내어 사용하는 방식으로 속도향상을 기대할 수 있다. 이러한 기법을 **메모이제이션(memoization)** 이라고 한다.  

 이러한 메모이제이션은 **참조적 투명성(referencial transparency)** 을 갖는 경우에만 적용할 수 있다는 것에 유의해야한다. 참조적 투명성이란 함수의 반환값이 입력 값에만 영향을 받는 성질을 말한다. 입력값이 같은데 결과가 다른 경우라면 당연히 값을 저장해두어도 의미가 없을 것이기 때문이다.

LIS( longest Increasing Sub-sequence, 최장 증가 부분 수열) 문제

LIS 문제는 매우 유명한 동적 계획법 연습문제 중 하나이다.  

O(n2) 알고리즘

   새로운 배열 D를 정의하자. D[i]의 정의는 다음과 같다.    D[i] : A[i]를 마지막 값으로 가지는 가장 긴 증가부분수열의 길이    A[i]가 어떤 증가부분수열의 마지막 값이 되기 위해서는 A[i]가 추가되기 전 증가부분수열의 마지막 값이 A[i]보다 작은 값이여야 한다.

 따라서 A[i]를 마지막 값으로 가지는 '가장 긴' 증가부분수열의 길이는 A[i]가 추가될 수 있는 증가부분수열 중 가장 긴 수열의 길이에 1을 더한 값이 된다.

예시 출처 : 나무 위키   이 알고리즘은 N개의 수들에 대해 자기 자신 전의 모든 수를 다 훑어봐야 하므로 O(N2)의 시간복잡도를 가지는 알고리즘이 된다.  

LIS 문제에서 동적 계획법이 적용된 부분?

• 완전 탐색을 한다면, 각 위치에서 시작하는 가능한 모든 증가 부분수열을 구하고 그것의 길이를 비교하는 방식일 것이다.  
• 반면 위 방법에서는 D배열에 이전에 계산된 결과인 각 위치의 최대 증가 부분수열의 길이를 저장해 두고 그 다음 위치에서는 A의 크기를 비교하여 들어갈 수 있는 위치 중 가장 큰 D에 1씩 더하는 과정으로 계산한다. 즉 결과를 저장하여 이후 계산에 활용하는 동적 계획법이 적용되었다고 볼 수 있다.  

• 2019 14