[알고리즘] DP 박살내기 1. 문제 해결하기

DP가 어떤 경우에 사용될 수 있는지 저번 글을 통해 알아봤다.
이번에는 본격적으로 문제를 DP적으로 접근하는 방법 에 대해 공부하자.
GeeksforGeeks - How to solve a Dynamic Programming Problem ?

1. DP 문제인지 파악

• 특정 조건 하에 최대의, 최소의 양을 구하거나 counting 하는 문제들은 DP를 사용해 해결할 수 있다.
• 모든 DP 문제들은 Overlapping Subproblem이나 Optimal substructure 의 구조를 만족한다. 이런 부분이 문제에서 보인다면 DP를 사용해 해결할 수 있다.

2. 상태(State) 결정하기

DP 문제는 상태(State)와 상태간의 전이(Transition)을 통해 진행된다.

State란?
A state can be defined as the set of parameters that can uniquely identify a certain position or standing in the given problem. This set of parameters should be as small as possible to reduce state space.

상태는 문제 내에서 주어진 조건을 고유하게 정의할 수 있는 파라미터로 정의된 집합을 말한다. 파라미터는 상태 공간을 최소한으로 정의할 수 있어야 한다.

문제 해결 방향은 즉,
문제가 DP인지 파악 → 상태 정하기 → 이전 상태에서 다음 상태로 가는 관계 찾기 라고 할 수 있다.

3. 상태간의 관계 공식화하기

문제 해결에 있어 연습, 직관이 제일 많이 필요한 부분이다.

3개의 숫자 [1,3,5]가 주어졌을 때 N을 만들 수 있는 모든 경우의 수 구하기

n을 만드는 경우의 수를 state(n)이라고 하자.
state(1), state(2) ··· state(6)을 알고 있다고 할 때 state(7)을 구하려고 할 때 방법은 다음과 같다.

(1) state(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(4)에서 3 더하기
[(1+1+1+1) + 3] 
[(1+3) + 3] 
[(3+1) + 3] 

(3) state(2)에서 7 더하기
[ (1+1) + 5]

다음과 같은 관계가 유추된다.
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)

def solve(n):
  # Base case
  if n < 1:
    return 0
  if n == 1:
    return 1
  return (solve(n - 1) + solve(n - 3) + solve(n - 5))

이제 문제 해결을 위해 memoization or tabulation 을 사용하면 된다.

4. Memoization or Tabulation

재사용할 수 있도록 계산된 결과를 기억해 둔다.
DP 박살내기 0. 기본 개념 - Memoization, Tabulation

이제 문제를 직접 도전해볼 차례이다. DP만 진득하게 풀다보면 내 것이 되겠지