동적 프로그래밍, Dynamic Programming(DP)

DP란?

기본적으로 DP란 recursion 을 활용한 최적화 방법

문제를 여러 개의 부분 문제로 나누어 해결하고,

이를 저장해 둠으로써 다시 계산할 필요 없이 사용할 수 있도록 하는 것!

       → 가장 작은 부분의 결과를 저장 후, 이를 이용해 상위 문제를 풀어가는 방식

 

다음과 같은 경우에서 DP를 사용할 수 있다.

 반복을 시행하는 부분이 존재.
 동일 한복 연산 결과가 일정해야 함.

 

대표적인 예로 피보나치 수열 문제가 있다!

// recursion을 사용한 문제 해결
// 이 경우 실행 단계에 따라 계산 횟수가 기하급수적으로 증가함.
int fib(int n) {
    if (n <= 1)
        return n;
    return fib(n-1) + fib(n-2);
}

//DP를 사용한 문제 해결
//시간 복잡도가 linear하게 증가함
f[0] = f[1] = 0;
for(i = 2; i <= n; i++) {
    f[i] = f[i-1] + f[i-2];
}
return f[n];

재귀함수를 사용한다면 동일한 연산을 계속 반복해야 함.

DP를 사용하게 되면 연산 결과를 memoiaztion한 후, 저장 해 사용

값이 커질수록 효율적이다.

 

문제 구조 파악

💡 어떤 문제에 DP를 사용할 수 있을까??

1. Overlapping Subproblem(부분 반복 문제)

DP의 장점은 부분 문제를 재계산할 필요가 없음이다.

따라서 겹치는 부분 문제가 없다면 DP를 사용할 필요가 없다.

위 예의 피보나치 문제 역시 같은 계산이 여러 번 수행됨을 알 수 있다.

이를 해결하기 위해 값을 저장하는데 총 두가지 방식이 존재한다.

2. Optimal Substructure(최적 부분 문제)

주어진 문제의 최적의 해결 방안이 부분 문제의 최적의 해결 방안으로부터 얻어지는 경우

최단 경로 문제의 경우 노드 a 에서 노드 c 로 가는 경로에 노드 b가 있다면,

이 경로는 노드 a에서 노드 b로 가는 경로 +노드 b에서 노드 c로 가는 경로 와 같게 된다.

Memoization

• 중복되는 연산과정을 해결하기 위한 개념
• 동일한 계산을 반복해야할 경우 이전 결과값을 메모리에 저장하여 반복수행 제거 → 효율 업!

DP의 접근 방법

1.1 (Top down)

계산을 수행하기 전 값이 저장된 테이블(lookup table)을 살펴본 뒤 값이 존재하면 사용하고,

값이 존재하지 않으면 추후에 재사용할 수 있도록 계산된 결과를 저장하는 방식

def fib(n, lookup):
    if n <= 1:
        lookup[n] = n
        
    # 계산된 값이 존재하지 않는다면
    if lookup[n] is None:
        lookup[n] = fib(n-1 , lookup)  + fib(n-2 , lookup)
        
    return lookup[n]

1.2 Bottom up

원하는 계산 결과를 얻기 위해 가장 아래부터 채워나가는 방식

보통 for문을 이용하는 방식이 이에 해당함

def fib(n):
    f = [0] * n
    f[1] = 1
    
    for i in range(2, n+1):
        f[i] = f[i-1] + f[i-2]
    return f[n]

두 방식은 접근 방식에서 차이점을 보인다.

fib(n),fib(n-1) ··· fib(0) : Top-down 방향으로 진행되고,

fib(0), fib(1), ··· fib(n) : Bottom-up 방향으로 진행된다.

DP 문제인지 파악

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

상태(State) 결정하기

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

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

→ 문제의 해결 방향은 다음과 같다.

1. 문제가 DP인지 파악
2. 상태 정하기
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)에서 5 더하기
[ (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 이나 tabulation 을 사용하면 됨

 

정리해보긴 했지만 문제를 많이 풀어보면서 경험을 쌓는 방법이 최곤 거 같다..!