다이나믹 프로그래밍(Dynamic Programming)은 복잡한 문제를 해결하기 위한 컴퓨터 프로그래밍 기법 중 하나다. 이 기법은 같은 문제가 반복적으로 해결되는 경우에 사용되며, 이전에 계산한 결과를 저장하고 재사용함으로써 중복 계산을 피하고 실행 속도를 높이는 효과가 있다. 아래는 다이나믹 프로그래밍의 개념, 접근 방법, 구현 방법, 활용 사례 등에 대해 정리한 내용이다.

개념

• 다이나믹 프로그래밍은 재귀함수 또는 반복문을 이용하여 문제를 여러 단계로 쪼개고, 이전 단계들의 해(=결과 값)를 이용해서 다음 단계의 해를 구해나가는 기법이다.

• 다이나믹 프로그래밍은 이전 단계들의 해를 Cache(임시 데이터 저장소)에 저장하여 중복 계산을 피하고 시간복잡도를 줄일 수 있다.

  • Memoization & Tabulation

    • Memoization
    • 함수 호출 결과를 캐시에 저장하여, 이후 같은 입력에 대한 함수 호출이 필요할 때, 이전에 계산된 결과를 반환하는 것
    • 주로 top-down 방식에서 사용
    • Tabulation
    • 계산한 값을 배열에 저장하여 다음 계산 때 해당 값을 이용하는 것
    • 주로 bottom-up 방식에서 사용

    ⇒ 엄밀히 구분하자면 차이가 있긴하지만, 보통 momoization이라고 통칭하며 더 큰 문제를 해결하는데 사용하기 위해 작은 부분 문제들의 해를 배열에 임시로 저장하는 것이라고 이해하면 된다.

• 대부분의 다이나믹 프로그래밍 문제는 최적화 문제이며, 최적화 문제는 가능한 해 중에서 가장 좋은 해를 찾는 문제다.

• 동적계획법 vs 분할 정복

접근 및 구현 방식

다이나믹 프로그래밍은 보통 Top-down 방식 또는 Bottom-up 방식으로 접근한다.

• Top-down 방식: 큰 문제를 해결하면서 필요한 작은 하위 문제를 해결해 나가는 방식 일반적으로 재귀 함수와 memoization를 이용하여 구현
  • 일반적인 코드 형태
• Bottom-up 방식은 가장 작은 단계의 문제부터 해결하며, 그 결과를 이용하여 점차 최종 단계의 문제를 해결하는 방식 일반적으로 반복문과 tabulation을 이용하여 구현
  • 일반적인 코드 형태

시간복잡도

O(부분 문제의 개수 * 각 문제를 푸는 시간)

일반적으로 다이나믹 프로그래밍은 중복 계산을 줄이기 위해 이전 결과를 저장하고 재사용하는 memoization 기법을 사용하기에,

시간 복잡도는 하위 문제의 수와 각 하위 문제를 해결하는 데 필요한 시간에 따라 결정된다.

• 다음은 피보나치 수열을 완전탐색(Brute Force), DP(top-down), DP(bottom-up) 방식으로 푼 코드 예제이다.

  # recursion - O(2^n), if n == 50 -> 반복 횟수: **2075316483** 
  def fibo(n):
      if n <= 1:
          return 1
  
  		return fibo(n-1) + fibo(n-2)
  

  # dp(top-down) - O(2xn), if n == 50 -> 반복 횟수: **99** 
  def fibo(n):
  		global cache
  
      if n <= 1:
          return 1
  
      if cache[n] != 0:
          return cache[n]
  
      cache[n] = fibo(n-1) + fibo(n-2)
      return cache[n]
  

  # dp(bottom-up) - O(n), if n == 50 -> 반복 횟수: **49**
  def fibo(n):
      cache = [0] * (n + 1)
  
      cache[0] = cache[1] = 1
  
      for i in range(2, n + 1):
          cache[i] = cache[i-1] + cache[i-2]
  
      return cache[n]
  

  DP를 이용한 중복 계산 방지로 시간복잡도가 **O(2^n) → O(n)**으로 극적으로 바뀐 것을 알 수 있다.

  또한 top-down 방식에서는 재귀 함수의 특징으로 인해 여러번의 함수 호출이 필요하지만, bottom-up 방식은 반복문을 이용하기 때문에 큰 입력에 대해서도 top-down 방식보다 메모리 사용량이 적으며, 실행 속도도 빠르으로 더욱 효율적인 방법임을 알 수 있다.

하지만 (경험상)백준의 전형적인 DP 문제들은 봤을 때, 애초에 완전탐색(Brute Force)을 시도할 생각조차 못하는 문제들이 많기 때문에 시간복잡도를 줄이기 위해 DP를 사용할지 고민할 필요는 없음

오히려 DP로 시간초과가 발생하여 Greedy로 풀어야되는 지 고민되는 문제는 많을 것 같음