Dynamic Programming, DP, 동적 계획법

• 문제를 작은 문제로 분할하여 분할된 문제의 해답을 기록해 놓은 후 더 큰 문제의 해답을 계산할 때 재사용하는 방법을 의미
  • 문제의 해답의 성질을 분석해 적절하게 작은 문제로 분할
  • 분할된 문제의 해답이 표에 기록되어 있다면, 그 해답들을 조합해 더 큰 문제의 해답을 계산하여 다시 표에 기록

Dynamic Programming의 조건

1. 최적 부분 구조 (Optimal Substructure)
   • 부분 문제들의 최적의 답을 이용해서 기존 문제의 최적의 답을 구할 수 있다는 것
2. 중복되는 문제 (Overlapping Subproblem)
   • 부분 문제들을 해결하기 위해 중복되는 연산을 수행

DP 알고리즘의 4단계

1. 해답의 구조를 파악 → 부문제(Subproblem) 나누기

2. 부문제의 해답을 조합 → 더 큰 문제의 해답을 도출해낼 수 있는 식 마련

   ⇒ 보통 점화식으로 표현

3. 부문제에서 큰 문제로 적당한 순서에 따라 해답을 계산하여 DP 테이블에 저장, 재사용

4. 위의 단계들이 원래 문제의 답을 항상 출력함을 증명, 답 리턴

DP 알고리즘의 2가지 방법

• Memoization

  • 중복되는 계산은 한 번만 계산 후 메모
  • cache라는 것을 사용하여, 중복 값 가져오기
  • 하향식 접근 (Top-Down Approach)
  • 재귀 기반 ⇒ 호출 스택 제한이 있음
  • 필요한 계산만을 수행

  def fib_memo(n, cache):
      # base case
      if n < 3:
          return 1
  
      # 이미 n번째 피보나치를 계산했으면:
      # 저장된 값을 바로 리턴
      if n in cache:
          return cache[n]
  
      # 아직 n번째 피보나치 수를 계산하지 않았으면:
      # 계산을 한 후 cache에 저장
      cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
  
      # 계산한 값을 리턴
      return cache[n]
  
  def fib(n):
      # n번째 피보나치 수를 담는 사전
      fib_cache = {}
      return fib_memo(n, fib_cache)
  

  ⇒ 수행시간 = $O(n)$

• Tabulation

  • 중복되는 부분부터 해결 → 상향식 접근(Bottom-Up Approach)
  • Table 방식으로 정리
  • 반복문 기반 ⇒ 중간에 필요 없는 계산이 포함될 수 있음.

  def fibo_tab(n):
  		# 이미 계산된 피보나치 수를 담는 리스트
      DP = [0, 1, 1]
  
      # n번째 피보나치 수까지 리스트를 하나씩 채워 나간다
      for i in range(3, n + 1):
          DP(DP[i - 1] + DP[i - 2])
  		
  		return DP[n]
  

  ⇒ 수행시간 = $O(n)$, 공간 복잡도 = $O(n)$

• 특수 경우

  • 모든 계산 값을 저장할 필요가 없을 때
  • 공간 사용을 최적화

  def fib_optimized(n):
      prev = 0
      current = 1
      # [1, 1]
      if n < 2:
          return current
      for i in range(1, n):   # 반복문을 돌면서 n까지 값을 더해감
          prev, current = current, current + prev
      return current
  

  ⇒ 수행시간 = $O(n)$, 공간 복잡도 = $O(1)$

최대 합 계산하기

정수 n개의 수열이 A에 주어질 때, 이 수열에서 A[i] + A[i + 1] + ... + A[j]의 합이 최대가 되는 인덱스 i, j를 계산하고, 그 최대 합을 출력하라

• 4단계 분석

  1. 부문제로 분할하기

     • 최대합이 A[i] + A[i + 1] + ... + A[j] 라고 할 때, **A[i] + A[i + 1] + ... + A[j - 1] 은 A[j - 1]로 끝나는 구간 중에 합이 최대인 구간**이 되어아 함
     • 최대합이 A[j]로 단 하나의 숫자로만 구성될 수도 있음
     • 최대합은 **A[j] 자체** or **A[j - 1] 로 끝나는 최대 구간 합 + A[j]**

  2. 부문제의 답을 큰 문제의 답으로 표현

     • A[0], ..., A[i]에 대해서, A[i]가 마지막에 포함되는 최대합을 S[i] 라고 하면,
     • S[i]는 S[i - 1] + A[i] 혹은 A[i] 둘 중 큰 값이 된다

     $\therefore$ S[i] = max(S[i - 1] + A[i], A[i])

  3. 적당한 순서로 테이블 채우기

     • S를 리스트로 표현, S[i]를 계산하기 위해서는 S[i - 1]을 알아야 하므로, Tabulation 방식으로 계산

  4. 항상 옳은 답을 내는지 확인, 답 출력