[Dynamic Programming] 다이나믹 프로그래밍의 기초

코드없는 프로그래밍님의 강의 수강

 

 

Dynamic Programming

조건

• 문제가 더 작은 subproblem으로 쪼개질 때
• subproblem의 solution으로 더 큰 problem의 문제를 해결할 수 있을 때
• 나눈 subprolem이 겹칠 때 -> 필요한 계산 수를 줄일 수 있다.

 

피보나치 수열

대표적인 동적 프로그래밍의 예시

피보나치 수열 F(7)을 구하고 싶다면?

F(7) = F(6) + F(5)

F(7) = F(5) + F(4) + F(4) + F(3)

F(7) = F(4) + F(3) + F(3) + F(2) + F(3) + F(2) + F(2) + F(1)

.

.

.

시간 복잡도는?

층이 늘어날 때마다 2가 곱해지고 총 n개의 층이기 때문에 $$O(2^n)$$

def fib_naive(n):
  if n == 0:
	return 0
  elif n == 1:
	return 1
  else:
	fib = fib_naive(n-1) + fib_naive(n-2)
	return fib

 

 

다이나믹 프로그래밍으로 적용해보자구

• 결과 값의 array를 미리 만들어 둔다.
• 나눠지는 subproblem에서 필요한 값을 array에서 찾는다.
• 값이 없으면 그 때 계산해서 넣어주면 된다.

fib_array = [0,1]

def fib_recur_dp(n):
  if n < len(fib_array): # 구해야 할 n번째 피보나치 수가 배열에 존재하면 그 값을 return
  	return fib_array[n]
    
  else:
	fib = fib_recur_dp(n-1) + fib_recur_dp(n-2)
	fib_array.append(fib)
	return fib

이렇게 계산하면 시간 복잡도는 다음과 같다. $$O(n)$$

 

하지만 위의 함수에서 fib_recur_dp(10000)과 같이 큰 숫자를 구하려면 재귀 깊이 초과 에러가 나온다.

가장 위의 숫자 n부터 쪼개나가면서 해결하려고 하기 때문에 top-down 방식의 다이나믹 솔루션이라고 한다. 쌓아가는 stack의 한계가 있기 때문에 좋은 solution은 아니다.

 

Bottom up 다이나믹 솔루션

가장 작은 F(0) 부터 F(1), F(2) ... 쌓아나가는 것

def fib_dp(n):
  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)

시간 복잡도: O(n)

공간 복잡도: O(n)