Dynamic Programming

다이나믹 프로그래밍이란

1. 복잡한 문제를 sub-problem들로 나누고 
2. 중복된 계산을 피하기 위해 sub-problem들을 풀어낸 결과를 저장하고 사용하는 것을 말한다.

 

DP의 두가지 속성

1. Overlapping SubProblem
2. Optimal Substructure Property

 

 

 

---

DP의 두가지 속성

1. Overlapping Subproblem

 

  분할정복에서와 같이 DP는 문제를 sub-problem들로 쪼개고 다시 합치는 방식으로 문제를 풀어나가기 때문에 문제를 쪼갤 수 있다면 DP를 적용 할 수 있다.

 

2. Optimal SubStructure Property

 

  주어진 문제를 sub-problem에서 최적화된 답을 사용해서 최적화된 답을 얻을 수 있다면 Optimal Substructure Property를 가진다고 한다.

 

 

 

---

풀어내는 과정

 

1. DP를 적용 할 수 있는 문제인지 알아내기.

• 대게 특정 수량이나 count들을 maximize하거나 minimize하는 문제들은 DP를 적용할 수 있다. 
• 특정 조건 또는 특정 확률 문제에서 배열등을 세는 문제도 DP를 적용할 수 있다.
• 대부분의 DP문제는 Overlapping Subproblem을 충족하며, 고전적인 문제는 Optimal Substructure Property도 충족하기 때문에, 이러한 속성이 문제에 있다면 DP를 적용할 수 있다.

 

2. 'state' 결정하기

• DP문제는 'state'와 이 스테이트의 전이상태를 결정하는 문제라고 볼 수 있다.
• 'state'는 특정 위치 또는 문제를 식별 할 수 있는 매개 변수의 집합이다. 
• 'state'는 state space를 줄이기 위해 작으면 작을수록 좋다.

 

3. 'state' 사이의 관계를 공식화하기.

 

 

4.  'state'에 memorization이나 tabulation을 추가하기

 

 

---

Tabulation vs Memorization

 

DP를 푸는 방법에는 두가지가 있다.

1.  Tabulation: Bottom-Up
2.  Memorization: Top-Down

 

 

Tabulation(Bottom-Up)

팩토리얼 문제를 푼다고 생각해보자. State를 x의 팩토리얼 값 -> dp[x]라고 정의하면 state사이의 공식은 dp[x+1] = dp[x] * (x+1)이라고 볼 수 있다. 이때 tabulation을 이용해 다음과 같이 코드를 짤 수 있다.

 

int dp[MAXN];
 
int dp[0] = 1;
for(int i = 1; i <= n; i++) {
  dp[i] = d[i-1] * i;
}

 

 * dp[0]부터 시작해 순차적으로 올라가 목적 값인 dp[n]까지 올라가는데 이럴 때 bottom-up 방법을 사용한다고 보면 된다.

 

 

 

 

Memorization(Top-down)

dp[n]에서 시작해서 기본 state인 dp[0]까지 도달하여 값을 묻고, dp[n]의 값을 가져오는 방식이 top-down approach이다. 재귀를 풀어내는 것과 유사하다.

 

Factorial을 top-down으로 풀어내면 다음과 같다. 

 

int dp[MAXN]
 
// return fact x
int solve(int x)
{
  if(x==0)
    return 1;
  if(dp[x] != -1)
    return dp[x];
  
  return (dp[x] = x * solve(x-1)); 
}

* 값들을 dp[x]라는 캐시안에 넣어주기 때문에 더욱 빨리 계산이 된다.

 

---

 

References

 

www.geeksforgeeks.org/overlapping-subproblems-property-in-dynamic-programming-dp-1/

Overlapping Subproblems Property in Dynamic Programming | DP-1 - GeeksforGeeks

www.geeksforgeeks.org/optimal-substructure-property-in-dynamic-programming-dp-2/

Optimal Substructure Property in Dynamic Programming | DP-2 - GeeksforGeeks

www.geeksforgeeks.org/tabulation-vs-memoization/

Tabulation vs Memoization - GeeksforGeeks

www.geeksforgeeks.org/solve-dynamic-programming-problem/

How to solve a Dynamic Programming Problem ? - GeeksforGeeks