다이나믹 프로그래밍(Dynamic Programming)이란 최적의 해를 구하기에는 시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제에서, 메모리 공간을 조금 더 사용하여 연산 속도를 비약적으로 증가시키는 방법 중 하나로 동적 계획법이라고도 한다.

참고자료

• 동적 계획법

• 코딩테스트, 기초, 다이나믹 프로그래밍, dynamic programming

• 이것이 취업을 위한 코딩테스트다 - 나동빈

동적할당의 Dynamic vs DP의 Dynamic

동적할당의 다이나믹(’프로그램이 실행되는 도중’이라는 의미)과는 다른 의미이며, 탐색해야 할 범위(해가 될 수 있는 공간)를 ‘진전’하면서 결정한다는 의미이다.

다이나믹 프로그램이과 분할 정복의 차이점

분할된 작은 문제가 중복이 일어나는지의 여부

⇒ 다이나믹 프로그래밍은 문제들이 서로 영향을 미친다.

• 조건
  • 큰 문제를 작은 문제로 나눌 수 있다.
  • 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. (최적 부분구조)
  • 재귀적 해법으로 풀면 같은 문제에 대한 재귀호출이 심하게 중복된다. (재귀 호출 시 중복)
• 피보나치 수열
  • 단순 재귀 구현

    // 피보나치 함수를 재귀함수로 구현
    def fibo(x):
    	if x == 1 or x == 2:
    		return 1
    	return fibo(x-1) + fibo(x-2)

    문제점: 동일한 함수의 중복 호출로 인해 연산 횟수가 기하급수적으로 늘어난다. ⇒ 다이나믹 프로그래밍(탑다운 방식 or 보텀업 방식)으로 해결 [자료구조 알고리즘] 피보나치수열의 시간복잡도

    재귀적 해법이 치명적인 예 vs 바람직한 예

    피보나치 수 구하기, 행렬곱셈 최적순서 구하기 ↔ 퀵정렬, 병합정렬 등의 정렬 알고리즘, 계승(factorial) 구하기, 그래프 DFS

    탑다운 vs 보텀업

    둘 중 어느 방식으로 푸는 지는 정해져있지 않다. 다만 하위문제의 복잡도로 인한 점화식 추출의 어려움이 있다면 탑다운 방식을 먼저 적용해보며, 효율성(시간복잡도) 고려시 보텀업 방식을 먼저 적용해보는 것을 고려하는 것이 좋다.

    cf) 재귀함수는 관계중심으로 문제를 파악함으로써 문제를 간명하게 볼 수 있다는 장점이 있다.
    • 피보나치 수열 (보텀업)
      $dp[i] = dp[i-1] + dp[i-2]$

      # DP 테이블 (보텀업 방식에서의 결과 저장용 리스트)
      dp = [0] * 100
      
      dp[1] = 1
      dp[2] = 1
      n = 99
      
      # 피보나치 함수를 보텀업 방식으로 구현
      for i in range(3, n + 1):
      		dp[i] = dp[i - 1] + dp[i - 2]

• 메모제이션 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로 메모제이션(Memoization) 기법을 사용할 수 있다. 이는 다이나믹 프로그래밍과는 별도의 개념으로, 다이나믹 프로그래밍에 활용되지 않을 수도 있다. 메모제이션은 한 번 구한 결과를 메모리 공간에 메모해두고, 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 방식을 취한다.
  • 값을 저장하는 방법이므로 캐싱(Caching)이라고도 한다.
  • 한 번 구한 정보를 리스트에 저장함으로써 구현

개념

탑다운 방식

💡 상태트리를 먼저 그려라

탑다운 방식(Top-Down, 하향식)은 재귀함수를 이용한 다이나믹 프로그래밍 소스코드를 작성하는 방법으로, 큰 문제를 해결하기 위해 작은 문제를 호출한다.

탑다운 방식도 다이나믹 프로그래밍?

일반적으로 다이나믹 프로그래밍은 보텀업 방식을 일컫는 말이지만, 넓은 의미에서는 재귀호출의 풀이 방식이 점화식의 형태(보텀업 풀이)와 비슷하기에 탑다운 방식 또한 다이나믹 프로그래밍으로 보는 견해도 있다.

[출처: ’이것이 취업을 위한 코딩테스트다’ 중]

• 피보나치 수열 (탑다운)

  # 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
  dp = [0] * 100
  
  # 피보나치 함수를 탑다운 방식으로 구현
  def fibo(x):
  	**// 이미 계산한 적 있는 문제라면 그대로 반환**
  	if dp[x] != 0:
  		return dp[x]
  	if x == 1 or x == 2:
  		return 1
  	dp[x] = fibo(x - 1) + fibo(x - 2)
  		return dp[x]

보텀업 방식

💡 점화식을 먼저 세워라

보텀업 방식(Bottom-Up, 상향식)은 반복문을 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법으로, 작은 문제부터 차근차근 답을 도출한다.

⇒ 결과 저장용 리스트인 DP 테이블(배열)의 각 원소에 최종 결괏값이 저장된다.

• 풀이순서

  1. 점화식 세우기: 특정 위치에 대응하는 DP 테이블 값은 그 이전 위치에 대응하는 DP 테이블 값을 이용하여 나타낼 수 있다. dp[i]가 어떤 의미를 나타내는지 정확히 정의한다. (최우선적이고 가장 중요한 단계)

     cf) 특정 시점에서 이전 단계를 바라보았을 때, 해당 시점의 상태로 넘어오기 위해서 거칠 수 있는 여러 가능한 경로를 추상화하면 점화식을 보다 수월하게 도출할 수 있다.

  2. DP 테이블 생성: DP 테이블의 한계 인덱스를 어떤 기준으로 잡을지 고려

  3. 고정된 초깃값이 존재한다면 해당 위치에 대응하는 DP 테이블 값 갱신

  4. 반복문을 사용하여 점화식을 표현

응용

• 2차원 배열 최소비용
  $dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + stones[i][j]$

  n = int(input())
  stones = [list(map(int, input().split())) for _ in range(n)]
  dp = [[0] * n for _ in range(n)]
  dp[0][0] = stones[0][0]
  
  for i in range(n):
      for j in range(n):
          if i == 0 and j > 0:
              dp[i][j] = dp[i][j - 1] + stones[i][j]
          if i > 0 and j == 0:
              dp[i][j] = dp[i - 1][j] + stones[i][j]
          elif i > 0 and j > 0:
              dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + stones[i][j]
      
  print(dp[n - 1][n - 1])

  ⇒ 경우에 따라 2차원 DP 테이블을 만드는 것도 고려해야 한다.
  

• 냅색(배낭) 알고리즘
  $dp[j] = max(dp[j], dp[j - w] + v)$
  dp[j]: 가방에 j 무게만큼의 내용물을 담았을 때의 최대 가치 dp[j - w]: w 만큼의 무게를 이미 사용했다고 가정하고 남은 무게를 구성하는 경우의 수 중 가치의 최댓값(이미 최댓값으로 갱신되어있을 것)

코딩테스트, 중급, knapsack problem

    import sys
    input = sys.stdin.readline
    
    n, k = map(int, input().split())
    weight = [0] * (n + 1)
    value = [0] * (n + 1)
    for i in range(1, n + 1):
        weight[i], value[i] = map(int, input().split())
    
    dp = [[0] * (k + 1) for _ in range(n + 1)]
    
    for cur in range(1, n + 1):
        for limit in range(1, k + 1):
            if weight[cur] <= limit:
                dp[cur][limit] = max(dp[cur - 1][limit], dp[cur - 1][limit - weight[cur]] + value[cur])
            else:
                dp[cur][limit] = dp[cur - 1][limit]
    
    print(dp[-1][-1])

• 동전교환(냅색 알고리즘 응용)
  $dp[i] = min(dp[i], dp[i -coin] + 1)$

  n = int(input())
  coins = list(map(int, input().split()))
  coins.sort()
  exch = int(input())
  dp = [501] * (exch + 1)
  dp[0] = 0
  for coin in coins:
      for i in range(coin, exch + 1):
  	        dp[i] = min(dp[i], dp[i - coin] + 1)
  print(dp[exch])

  dp[i]: i 원을 거슬러 주는 데에 사용된 동전의 최소 개수 dp[i - coin]: coin 값 만큼의 금액을 이미 사용했다고 가정하고 남은 금액을 구성하는 가지 수 중 동전 구성 갯수의 최솟값(이미 최솟값으로 갱신되었을 것임)
  

• 최대점수 구하기(냅색 알고리즘 응용)
  • 2차원 리스트 구현

    n, m = map(int,input().split())
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        dp[i] = dp[i - 1].copy()
        score, time = map(int, input().split())
        for j in range(time, m + 1):
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - time] + score)
    print(dp[n][m])

    2차원 배열이 커질수록 메모리 낭비가 심해진다. ⇒ 1차원 배열을 제일 뒤의 원소부터 접근
    
  • 1차원 리스트 구현

    n, m = map(int,input().split())
    dp = [0] * (m + 1)
    
    for _ in range(n):
        score, time = map(int, input().split())
        for i in range(m, time - 1, -1):
            dp[i] = max(dp[i], dp[i - time] + score)
    print(dp[m])

• 플로이드-워샬
  그래프 상에서 최단경로를 구하는 알고리즘 중 하나인, 플로이드-워샬 알고리즘에도 DP의 개념이 사용된다.
  $graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])$

    	INF = int(1e9)
    	n, m = map(int, input().split())
    	graph = [[INF] * (n + 1) for _ in range(n + 1)]
    
    	for _ in range(m):
        	a, b, cost = map(int, input().split())
        	graph[a][b] = cost
    
    for k in range(1, n + 1):
        for a in range(1, n + 1):
            for b in range(1, n + 1):
                graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

- 연속 부분 수열의 최대합