동적프로그래밍(Dynamic Programming)이란? 에서는 동적프로그래밍 개념을 알아 보았다.
여기서는 동적프로그래밍으로 문제를 해결하는 방법에 대해서 설명한다.
동적프로그래밍 문제를 풀기위한 단계는 다음과 같다.
step1. 요놈이 동적프로그래밍(DP) 방식으로 풀수 있을지 없을지부터 구분해라.
문제를 만나면 DP로 분류되는 문제인지 판단해야 한다.
DP로 분류될수 있는 문제는 몇가지 특성이 있는데
문제의 해가 중복되는 하위문제(subproblems) 해를 사용하여 풀 수 있는 (Overlapping Subproblems) 특성이 있는지 또는 문제의 최적 해가 그 하위 문제의 최적 해로부터 얻을 수 있는 최적 하부 구조를 갖는 문제(Optimal Substructure)를 갖고 있는지 확인해라.
주어진 문제에서 이러한 속성(Overlapping Subproblems or Optimal Substructure)이 관찰되면 DP를 사용하여 해결할 수 있다.
보통 최적하부구조 특성을 갖는 문제들은 일반적으로 어떤 조건이나 확률을 주고 특정 수량이나 카운팅을 최대, 최소화하라는 문제가 대부분이며 DP를 사용하여 풀수 있다.
step2. 하위문제를 구분하기위한 매개변수 정의
DP 문제를 풀다보면 하위문제들로 나눌수 있고 각 하위문제의 특정 위치를 고유하게 식별 할 수있는 매개변수가 필요하다.
예를들어 피모나치 수열에서 각 하위문제의 상태를 f(n) , f(n-1) .. 로 구분하는데 n 은 특정 하위문제를 고유하게 식별할수 있는 매개변수가 된다. 따라서 두번 번째 단계는 문제가 DP 문제임을 확인한 후 하위문제를 고유하게 식별할수있는 매개변수를 결정하는 것이다.
DP는 이전 계산 하위문제들의 결과를 사용하여 최종 결과의 해를 찾기위해 공식화하는 것이 전부인데 이전 상태들 사이의 관계를 발견하여 현재 상태에 도달하기 위해 유니크한 하위문제의 매개변수를 정의하는것은 기본이 된다.
step3. 하위문제의 패턴을 찾아 공식화 하기
동적프로그래밍 문제를 푸는 단계중 가장 어려운 부분인데 하위문제의 패턴을 찾아 공식화 (점화식을 세운다라고 얘기함) 한다는 것은 예를들어 피보나치 수열을 DP로 푼다면 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이라는 패턴을 찾고 그림1과 같이 공식화 하는 것이다.
피보나치 수열은 일반적으로 많이 알려진거라 공식화 하는데 크게 어려움이 없지만 모든 DP문제의 공식화가 쉬운건 아니다.
위 단계들을 이용하여 numbers = { 1, 3, 5 } 가 있다면 1, 3, 5를 반복적으로 사용하여 합이 N인 숫자를 만들수 있는 경우의 수를 찾는 DP 문제를 풀어보자.
총합이 N = 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)을 계산해야하는데 state(n) 이 어떻게 동작하는지 알아보자
주어진 숫자를 만들기 위해 1, 3 또는 5 만 사용할 수 있다.
n = 1,2,3,4,5,6에 대한 결과를 알고 있다고 가정하자.
이 것은 state (n = 1), state (n = 2), state (n = 3) ……… state (n = 6) 결과를 의미하는 것이 된다.
이제 state (n = 7) 결과를 알고 싶다고하자.
오직 1, 3, 5 만 추가 할 수 있고. 다음 3 가지 방법으로 합계 7을 얻을 수 있다.
1) state(n=6) 의 모든 경우의 수에 1을 추가하는 방법
[ (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) 의 모든 경우의 수에 3을 추가하는 방법
[(1+1+1+1) + 3]
[(1+3) + 3]
[(3+1) + 3]
3) state (n=2) 의 모든 경우의 수에 5를 추가하는 방법
[ (1+1) + 5]
이제 위의 세 가지 케이스가 state(n=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) 가 되고 재귀로 풀어보자
|
1
2
3
4
5
6
7
8
9
|
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);
}
Colored by Color Scripter
|
공식을 보면 최종 결과값을 구하기위해 하위문제로 나눌수 있으니 dp 문제로 분류 가능하다.
그리고 이전 결과값을 탑다운 or 바텀업을 통해 룩업테이블 메모리에 저장해놨다가 필요할때 재사용하도록 하여 풀수 있다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
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);
}
Colored by Color Scripter
|
알고리즘 대회에서 DP문제는 매우 자주 출제되는데 공식화하는게 어렵기 때문에 다양한 DP문제를 풀어보면서 감각을 익히는것이 중요하다
레퍼런스
'알고리즘(Algorithm) > 동적프로그래밍(Dynamic Programming)' 카테고리의 다른 글
| 동적 프로그래밍 basic 문제-이항계수(Binomial Coefficient) - DP1 (0) | 2019.08.07 |
|---|---|
| 동적프로그래밍(Dynamic Programming)이란? (0) | 2019.07.05 |
