이 포스팅은 Nitish Kumar 의 기사를 참고하여 만들었습니다. [출처]
동적계획법 (Dynamic Programming), DP 는 다항(Polynomial)한 시간안에 특정 문제를 풀기위한 기술입니다. DP 를 이용한 솔루션은 지수형태의 단순한 방법보다 훨씬 빠르고, 솔루션이 맞다는것을 쉽게 증명할 수 있습니다.
DP를 풀기위한 4 step
문제가 DP 를 쓰면 풀리는지 확인하기
최소 매개변수를 이용해 어떻게 상태를 표현할지 정하기
상태 관계를 수식화 하기
도표 작성(tabulation) 하기 (또는 메모이제이션(memoization) 을 추가하기)
Step 1 : DP 문제를 어떻게 구분하나요?
-
일반적으로, 특정 수량의 최대 최소를 구하는 문제들 (대표적으로는 Knapsack 문제), 특정 조건을 만족하는 배열 갯수를 세는 문제 (대표적으로는 edit 문제) , 특정 확률 문제(대표적으로는 동전 교환 문제, 이부분은 확실치 않네요.)들은 DP 로 풀 수 있습니다.
-
모든 DP 문제들은 중복되는 서브문제 성질을 만족합니다. (피보나치 수를 구할때 트리에서 중복되는 함수들을 생각) 그리고 대부분의 클래식한 DP 문제들은 최적화 구조 성질을 만족합니다.
Step 2 : 상태(state) 정하기
DP 문제들은 모두 상태와 이전(transition)에 대한 문제들입니다. 상태 이전에 대한건 가장 기초가 되는 step 이면서도 굉장히 조심스럽게 이뤄져야 합니다. 왜냐하면 상태 이전은 우리가 상태에 대한 정의를 어떻게 하냐에 따라 달라지기 때문입니다. 그러면, 상태("state")라는것이 과연 무엇을 의미하는지 알아보겠습니다.
상태(State) 는 주어진 문제에서 특정 위치나 현 상태를 나타낼 수 있는것들을 개별적으로(uniquely) 표현할 수 있는 어떤 묶어져있는 매개변수(the set of parameters)를 말합니다. 공간을 절약하기 위해서 이 매개변수 묶음은 최대한 줄어들어야 하죠.
예를 들어보겠습니다. DP 로 유명한 문제 Knapsack 문제를 보면, 여기서 우리는 문제에 대한 상태를 두가지 매개변수를 사용하여 정의하겠습니다. 인덱스(index) 와 무게(weight) 입니다. i.e. DP[index][weight]. 이제 DP[index][weight]는 범위가 0부터 index 까지의 물건(item)을 집었을때 가방에 차게되는 무게(weight) 중에 가장 최대의 이익을 얻을 수 있는 value 가 어느정도 인지 말해줍니다. 그래서 매개변수 index 와 weight 를 한데 뭉치면 Knapsack 문제를 잘개 쪼갰을때의 서브문제들을 개별적으로 정의할수 있게 해줍니다.
- 최대 용량을 초과하지 않으면서 최대의 Value를 가지는 item의 조합을 고르는 Knapsack 문제
그래서, 주어진 문제가 DP 문제인지 확인한다음 해야될 일은 문제에 대한 상태를 정하는것이 저희가 가장 우선적으로 처리해야될 문제가 됩니다.
아시다시피, DP는 이미 계산된 결과들을 이용해서 최종 결과값을 계산하는 것입니다. 그래서, 다음에 해야될 step은 현재 상태와 이전 상태의 관계를 찾는 작업을 해야합니다.
Step 3 : 상태들끼리의 관계를 수식화 하기
이 부분이 DP 문제를 푸는데 가장 힘든 부분입니다. 많은 본능과 직감, 관찰 그리고 무엇보다 연습이 필요합니다. 샘플 문제를 통해서 이해해 보겠습니다.
주어진 3개의 숫자들 {1, 3, 5} 을 이용해서 숫자 'N' 을 구성할 수 있는 방법이 총 몇개가 있는지 알아내야 합니다.
(덧셈을 사용해야 하고 숫자들의 중복 사용은 가능합니다.)
N = 6일때 6을 만들 수 있는 방법은 총 8가지 입니다. :
1+1+1+1+1+1
1+1+1+3
1+1+3+1
1+3+1+1
3+1+1+1
3+3
1+5
5+1
이 문제를 DP 스럽게 생각해 보겠습니다. 첫째로, 주어진 문제에 대해 상태를 정해야 합니다. 매개 변수 n 을 서브 문제를 개별적으로 구별하기 위해 선택해 보겠습니다. 그러면, 우리의 dp 상태는 이런식으로 표현됩니다.
state(n)
state(n) 은 {1, 3, 5} 을 이용하여 n 을 구성하는데 이용할 수 있는 방법의 총 개수를 말합니다. 이제 state(n) 을 계산할 차례입니다.
어떻게 하죠?
이제 우리의 본능적 직감이 활약할때가 왔습니다. 1, 3 또는 5 만 이용해서 주어진 숫자 n 을 만들어야 합니다.
가정하기를, n 이 1,2,3,4,5,6 일때는 저희가 정답을 안다 합시다. 즉, state(n=1,2,3,4,5,6) 에 대한 값이 이미 저장되있다고 가정하겠습니다.
이제 우리가 알고싶은것은 state(n=7) 값 입니다. 우리는 오직 1, 3, 5 만 추가할 수 있습니다. 7은 아래와 같은 3가지 방법으로 7을 만들 수 있습니다.
1) state(n=6) 일때의 모든 가능한 조합에 1을 더한다.
Eg : [ (1+1+1+1+1+1) + 1][ (1+1+1+3) + 1]
[ (1+1+3+1) + 1][ (1+3+1+1) + 1]
[ (3+1+1+1) + 1][ (3+3) + 1]
[ (1+5) + 1][ (5+1) + 1]
2) state(n=4) 일때의 모든 가능한 조합에 4을 더한다.
Eg : [(1+1+1+1) + 3][(1+3) + 3]
[(3+1) + 3]
3) state(n=2) 일때의 모든 가능한 조합에 5을 더한다.
Eg : [(1+1) + 5]
위의 3개의 경우의 수들을 통해서 덧셈을 이용해 7을 만드는 모든 가능한 조합들을 확인할 수 있습니다.
따라서, state(7) 을 찾자면,
state(7) = state(6) + state(4) + state(2)
또는
state(7) = state(7-1) + state(7-3) + state(7-5) 로 표현할 수 있습니다.
일반적으로는,
state(n) = state(n-1) + state(n-3) + state(n-5) 라고 표현되고,
코드로 표현하자면 이렇습니다.
// Returns the number of arrangements to
// form 'n'
int solve(int n)
{
// base case
if (n < 0)
return 0;
if (n == 0)
return 1;
return solve(n-1) + solve(n-3) + solve(n-5);
} 하지만 위의 코드는 이미 계산된 state를 계산하고 또 계산하기 때문에 지수형태의 시간 복잡도가 나오게 됩니다.(
n
α
) 그래서 이를 해결하기 위해 memoization 을 추가하겠습니다.
Step 4: 상태에 memoization 이나 tabulation 을 추가하기
이 부분은 DP 솔루션을 구하는 과정에서 가장 쉬운 파트입니다.
단지 state의 값을 메모리에 저장하고 그 값들이 필요할때 꺼내쓰기만 하면 됩니다.
memoization 을 추가한 코드는 다음과 같습니다.
// initialize to -1
int dp[MAXN];
// this function returns the number of
// arrangements to form 'n'
int solve(int n)
{
// base case
if (n < 0)
return 0;
if (n == 0)
return 1;
// checking if already calculated
if (dp[n]!=-1)
return dp[n];
// storing the result and returning
return dp[n] = solve(n-1) + solve(n-3) + solve(n-5);
}또 다른 방법은 tabulation 을 추가해서 솔루션을 반복문(iterative) 형태로 만드는 것입니다.
(tabulation 과 memoization 의 다른점에 대한 포스팅은 다음에 작성하겠습니다.)
동적 계획법은 많은 연습을 해야만 숙달될 수 있습니다. 처음에는 다양하고 클래식한 DP 문제를 우선적으로 풀어봐야 합니다. 문제들은 여기서 찾을 수 있습니다.
출처: https://zzonglove.tistory.com/13 [난뭐야]
