01. 동적 계획법이란?

Dynamic Programming(동적계획법)

• 큰 문제를 작은 문제로 나누어푸는 방법으로,
  최초 한번 작은 문제를 한번만 풀고 그 정답을 기억(memo)해두어
  큰 문제를 푸는 동안 작은 문제가 반복되면 앞서 기억한 결과값을 가져오는 방식

02. 특징

단순히 반복되는 문제에 대한 비효율적 계산을 하지 않는다.

• 재귀함수 사용방식과 매우 유사하나 일반적인 재귀를 단순 사용 시
  동일한 작은 문제들이 여러번 반복되어 비효율적인 계산을 실행함.

시간복잡도가 작다.

• 피보나치 수열 함수의 경우,
  재귀 : O(n^2)
  DP : O(n)

03. 사용조건

① Overlapping Subproblems (겹치는 부분 문제)

• DP는 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용해서 전체 답을 구한다.
  그래서 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다.
  즉, DP는 부분 문제의 결과를 저장하여 재 계산하지 않을 수 있어야 하는데,
  해당 부분 문제가 반복적으로 나타나지 않는다면 재사용이 불가능하니
  부분 문제가 중복되지 않는 경우에는 사용할 수 없다.
  ex) 피보나치 수열 함수

② Optimal Substructure(최적 부분 구조)

• 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우를 의미한다.
  그래서 특정 문제의 정답은 문제의 크기에 상관없이 항상 동일하다.
  ex) 최단 경로 문제

04. 예시

피보나치 수열 함수 (TOP DOWN)

재귀 함수 (TOP DOWN)

def fib(n) :
  if n <= 2 :
    return 1

  else :
    return fib(n-1) + fib(n-2)

동적 프로그래밍 (BOTTOM UP)

def fibonacci(n) :
  dp = [0] * (n+1)
  dp[1]=1
  dp[2]=1
  for i in range(3,n+1) :
     dp[i] = dp[i-2]+dp[i-1]

  return dp[n]