다이나믹 프로그래밍(기초)

다이나믹 프로그래밍 적용 가능 조건 3가지

1. Problem이 Sub problem으로 나눠진다.

2. Sub problem으로 더 큰 규모의 sub problem 의 solution을 구할 수 있다.

3. Sub problem이 겹친다. -- memoization 이용 가능

 

다이나믹 프로그래밍 적용 가능한 대표 문제로 피보나치 수열이 있다.

 

 

sub problem이 겹치는 것도 확인할 수 있다.

 

Recursive DP 로 풀어보면...

 

fib_array = [0, 1]

def fib_recur_dp(num:int) :
  if n < len(fib_array) :
    return fib_array[n]
  else:
    fib = fib_recur_dp(n-1) + fib_recur_dp(n-2)
    fib_array.append(fib)
    return fib

Recursive DP는 TopDown 방식이라고도 한다. 직관적이지만, 스택프레임이 한계를 넘어가면 exception 이 발생한다.

따라서 좋은 방법의 solution은 아니다.

 

이를 대체하여 BottomUp 방식을 적용할 수 있다. 가장 작은 값부터 계산하기 때문에 이와같은 이름이 붙었다.

 

def recur_dp(n:int):
  if n == 0 :
    return 0
  elif n == 1:
    return 1
  fib_array = [0, 1]
    
  for i in range(2, n+1):
    num = fib_array[i-1] + fib_array[i-2]
    fib_array.append(num)
  return fib_array[n]

 

위 코드의 space complexity를 O(N)에서 O(1)로 줄일 수 있다. 2개의 공간만 있으면 되기 때문이다.

 

출처 : (5) 코딩테스트, 기초, 다이나믹 프로그래밍, dynamic programming - YouTube