동적 계획법(DP, Dynamic Programming)

동적 계획법(DP, Dynamic Programming)은 복잡한 문제를 작은 하위 문제로 나누어 풀고, 그 결과를 저장하여 큰 문제를 풀어나가는 것입니다.
문제에서 규칙 또는 점화식을 발견한다면, 동적 계획법(DP)를 사용하여 문제를 해결할 수 있습니다. 중복되는 계산 과정을 저장하여 시간을 절약할 수 있습니다.
DP는 너무나도 많은 유형이 있고, 직접 다양한 문제들을 경험하며 실력을 키워나가야 합니다.
- 어떤 것을 메모이제이션(memoization)해서 이용할 것인가가 가장 중요합니다. (큰 문제를 작은 문제로 나눠서 풀때 중복되는 부분을 찾아야 합니다.)

예시

예시 1 (피보나치 수)

가장 대표적인 예시인 백준 2748 피보나치 수 2 문제를 살펴보도록 하겠습니다.
- 참고 : 피보나치 수는 풀이과정이 상당히 많이 존재합니다. 그중에서 우선적으로 DP 방식을 살펴보도록 하겠습니다.
- fibo(5)를 구하는 예시를 살펴보도록 하겠습니다. 연산과정 중 내려가다 보면 반복되는 연산이 매우 많은 것을 확인할 수 있습니다. 이처럼 반복되는 연산을 기록해 두게 되면은 다음에 똑같은 연산이 나왔을 때 또다시 연산하지 않고 저장된 값을 그대로 불러와서 사용하게 되면 시간을 절약하게 됩니다. 이와 같은 방법을 메모이제이션(memoization)이라고 합니다.
- 이와 같은 DP 문제를 풀 때는 위에서부터 연산을 하는 탑다운(Top-down) 방식과, 아래서부터 하나하나 연산하는 바텀업(Bottom-up) 방식이 있습니다.
  - 탑다운 방식은 가독성이 좋고, 본래 점화식을 이해하기 쉽습니다.
  - 바텀업 방식은 함수를 별개로 부르지 않아 시간과 메모리를 소량 더 절약할 수 있습니다.
  - 저는 보통 바텀업 방식을 선호합니다. 본인이 선호하는 방식으로 구현하면 됩니다.
  - 탑다운(Top-down) 방식 구현
    - ```
    n= int(input())
    
    dp=[-1]*(n+1)
    dp[0]=0
    dp[1]=1
    
    def fibo(x):
        if dp[x]!=-1:
        	return dp[x]
        dp[x]=fibo(x-1)+fibo(x-2)
        return dp[x]
    
    print(fibo(n))
```
- 바텀업 (Bottom-up) 방식 구현
  - ```
  n= int(input())
  
  dp =[0] * (n+1)
  dp[1]=1
  
  for i in range(2,n+1):
      dp[i]=dp[i-1]+dp[i-2]
      
  print(dp[n])
```

예시 2 (평범한 배낭)

또 다른 DP의 대표적인 예시인 백준 12865 평범한 배낭 문제를 살펴보겠습니다.
- DP의 전형적인 문제인 Knapsack Problem입니다.
- 문제를 살펴보게 되면, 한정된 무게 K라는 공간에 물건들의 가치를 최대로 넣게 되었을 때 그때의 물건들의 가치의 최댓값을 구하는 문제입니다.
- (무게 범위 : 0~K) 가방 공간에 가치를 최대로 넣기 위해서는 각 무게에서 가치가 최대로 계속해서 유지가 되어야 합니다. 즉 이 말은 1만큼 무게를 실었을 때도 가치가 그 중에서도 최대가 되어야하고, 2만큼 무게를 실었을때도 가치가 최대, .. , K만큼 무게를 실었을때도 가치가 최대가 되어야 합니다.
- 따라서 새로운 물건(무게 W, 가치 V)을 넣게 될 때마다 (무게 범위 : W~K) 가방 공간을 업데이트해줘야 합니다. ( (무게 범위 : 0~W-1) 까지는 어차피 현재 물건을 넣지 못하기 때문에 그전 값을 그대로 유지하면 됩니다.)
  - (W~K)를 업데이트하는 현재 위치를 point라고 했을 때, point-W만큼 무게에 현재 물건을 넣게 되면 point 무게가 됩니다. 즉, 현재 물건을 넣었을 때와, 그전 point만큼 물건을 넣었을 때의 가치를 비교해서 더 큰 쪽을 넣어주어야 합니다.
  - 따라서 점화식을 세우게 되면 dp[point] = max(dp[point], dp[point-W]) 가 됩니다. (여기서 우측항은 이전 범위를 포함하지 않은 것입니다.
- 코드를 살펴보면 더 이해가 쉽게 될 것입니다.
  - ```
  import sys
  
  input = sys.stdin.readline
  
  n, k = map(int, input().split())
  
  arr = [list(map(int, input().split())) for _ in range(n)]
  
  dp = [0 for _ in range(k + 1)]
  
  for w, v in arr:
      for i in reversed(range(w, k + 1)):
          dp[i] = max(dp[i], dp[i - w] + v)
  
  print(max(dp))
```

예시 3 (행렬 곱셈 순서)

마지막 DP 예시 문제로 백준 11049 행렬 곱셈 순서 문제를 살펴보겠습니다.
- 행렬 N개를 곱하는데 필요한 곱셈 연산의 수를 최소로 만드는 것입니다.
- 만약에 A, B, C, D 행렬이 있다고 하면, ((AB)(CD)) / (((AB)C)D) / ((A(BC))D) / (A((BC)D) // ... 처럼 모든 쌍들에 대해 어떤 순서로 연산해야지 곱셈 연산의 수가 최소가 되는지 살펴봐야 합니다.
  - 모든 쌍을 고려한다는 것은 많은 시간이 걸리게 됩니다.
  - 시간을 줄이는 방법을 고민하다 보면 중복되는 연산이 존재한다는 것을 파악할 수 있을 것입니다.
  - 가장 먼저 이러한 규칙성을 찾아보는 방법은 N=1일 때부터 N=최대일 때까지 문제를 차근차근 접근해 보는 것입니다.
    - 여기서 N=1일 때는 최솟값이 0입니다.
    - N=2일 때는 무조건 AB 연산 개수입니다.
    - N=3일 때는 (AB)(C) 또는 (A)(BC) 둘 중 연산 개수가 작은 것이 답입니다.
    - N=4일 때는 ((AB)(CD)) // (((AB)C)D) // ((A(BC))D) , ... 에서 연산 개수가 작은 것이 답이 됩니다.
    - 이렇게 해본 결과 뒤에 새롭게 추가가 되면 또다시 CD 연산하는 과정 때문에 새로운 연산이 추가되게 됩니다. 그래서 이전 값들을 이용한 점화식은 찾지 못했습니다. 다른 방식을 통해서 규칙을 찾아보도록 하겠습니다.
  - 또 다른 규칙성을 찾아보는 방법은 N 그 자체에서 문제를 작은 문제들로 나눠서 차근차근 살펴보는 것입니다.
    - 행렬이 N개인 것을 작은 문제로 나누게 된다면 먼저 행렬 N개에 대해서 행렬 2개 끼리 연산된 것들에 대해 곱셈 연산의 수가 최소가 되는 것 먼저 기록해 두는 것입니다.
    - 그 후에 행렬 3개끼리 연산된 것들에 대해 곱셉 연산의 수가 최소가 되는 것을 기록합니다.
    - 그럼 그 값들은 어떻게 업데이트가 될까요? 행렬의 개수가 4개일 때 그전 값들을 어떻게 이용하는지 한번 살펴보도록 하겠습니다.
      - ABCD를 두 부분으로 나눈다면 다음과 같이 나눌 수 있습니다. (A)(BCD) // (AB)(CD) // (ABC)(D)
      - 그럼 이제 A, BCD, AB, CD, ABC, D 모두 이전 단계에서 곱셈 연산의 수가 최소가 되는 경우가 기록되었을 것입니다.
      - 그럼 여기에 추가될 연산은 두 개의 쌍 사이에 연산되는 횟수가 될 것입니다. 즉 (A)(BCD)는 행렬 A의 row x 행렬 A의 column x 행렬 D의 column 이 될 것이고 (AB)(CD)는 행렬 A의 row x 행렬 B의 column x 행렬 D의 column이 될 것입니다. 마지막 (ABC)(D)는 행렬 A의 row x 행렬 C의 column x 행렬 D의 column이 될것입니다.
      - 이처럼 연산 횟수는 이미 기록된 A, BCD, AB, CD, ABC, D 에다가 추가적으로 그 쌍에 대해 연산되는 횟수를 추가시켜 주면 됩니다. 위의 모든 경우 중에서 연산 횟수가 가장 작은 값으로 ABCD가 업데이트 되게 될 것입니다.
      - 위 방식은 Bottom-Up DP 방식입니다.
  - 코드
    - ```
    import sys
    
    input = sys.stdin.readline
    
    n = int(input())
    
    arr = [list(map(int,input().split())) for _ in range(n)]
    
    dp = [[0 for _ in range(n)] for _ in range(n)]
    
    for sub_len in range(2,n+1):
        for start_idx in range(n-sub_len+1): # 스타트 인덱스
            
            end_idx = start_idx+sub_len-1
            dp[start_idx][end_idx]=float('inf')
            for k in range(start_idx,end_idx):
                dp[start_idx][end_idx] = min(dp[start_idx][end_idx],dp[start_idx][k]+dp[k+1][end_idx]+arr[start_idx][0]*arr[k][1]*arr[end_idx][1])
    
    print(dp[0][n-1])
```

예시 4 (구간 나누기)

[백준 2228] 구간 나누기
- dp 문제는 완전 탐색을 이전값들을 이용해서 빠르게 해준다고 생각하면 됩니다.
- 이 문제처럼 두 개의 변수가 주어질때 두 개의 변수를 이용해 점화식을 찾는 방법도 있다는 것을 생각해주어야합니다.
- 우선적으로 n,m의 조합을 쭈욱 나열해서 하나씩 이전값을 사용하는 방식이 있는지 생각해봐야합니다.
  - dp에 m 구간과 n길이에 현재 값을 포함해서 계산한 결과와 현재 값을 포함하지 않은 결과를 저장합니다.
  - 이렇게 설정해두면 다음과 같은 점화식이 생성됩니다.
    - dp[row][column][0] = max(dp[row][column-1][0] +arr[column] , dp[row-1][column-1][1] +arr[column])
    - dp[row][column][1] = max(dp[row][column-1][0] , dp[row][column-1][1])
  - 아무것도 없는 것에서 a1, a2, a3 등 단일 값이 추가될때는 그전 값에서 더해질때 그전값이 -inf면 안됩니다. 따라서 dp[0] 에는 0값으로 초기화를 진행해줍니다.
- 코드
  - ```
  import sys
  
  input = sys.stdin.readline
  
  n, m = map(int, input().split())
  
  arr = [0] + [int(input()) for _ in range(n)]
  
  dp = [[[-float("inf"), -float("inf")] for _ in range(n + 1)] for _ in range(m + 1)]
  dp[0] = [[0, 0] for _ in range(n + 1)]
  
  for row in range(1, m + 1):
      for column in range(1, n + 1):
          dp[row][column][0] = max(
              dp[row - 1][column - 1][1] + arr[column],
              dp[row][column - 1][0] + arr[column],
          )
          dp[row][column][1] = max(dp[row][column - 1][0], dp[row][column - 1][1])
  
  print(max(dp[-1][-1]))
```

예시 5 (산 모양 타일링)

[프로그래머스] 산 모양 타일링
- 점화식을 찾는 문제의 dp 문제입니다.
- 점화식을 찾는 것이 다소 어려울 수 있는데 앞에서부터 차근차근 접근하다보면, 문제의 규칙이 발견됩니다.
- 전체의 개수는 n개로 나오지만, 전체 dp 길이는 2n개로 풀어야하는 문제였습니다.
- 이런 유형의 문제를 풀때는 항상 모든 값들을 그려보고, 다음 단계에서 추가되는것을 체크를 해줍니다. 이런식으로 진행해 나아갈때 어떤것들이 추가되었는지 확인하고 점화식을 세워주면 됩니다.
- 전체가 삼각형으로 채워진 것은 1개밖에 없고, 나머지는 모두 마름모가 1개이상 있는 경우 입니다. 즉, 마름모 타일이 채워질 수 있는 경우의 수를 구해야합니다.
  - 먼저 위 삼각형이 없을 경우(top이 0일 경우)를 그래보면 아래와 같이 규칙이 발생하게 됩니다.
    - 오른쪽에 하나씩 생겨날때마다 빨간색 동그라미 하나가 생겨나게 되고, 바로 전단계 개수와 바로 전전단계에 이어 붙인 모습이 됩니다.
    - 이를 이용하여 점화식을 생성하게 되면
    - dp[i]=dp[i-1]+dp[i-2]+1 가 됩니다.
  - 마찬가지로 위에 삼각형이 있을 경우(top이 1일 경우)에 대한 점화식을 구해보면 아래와 같습니다.
    - dp[i]=dp[i-1]+dp[i-2]+1+dp[i-1]+1
    - 그림을 그려보면 dp[i-1]+1이 왜 더해지는지 감이 올 것입니다.
    - 위에 삼각형이 있기때문에 삼각형부분에 마름모가 채워지게 되면, dp[i-1] 을 한번더 사용할 수 있습니다.또한 마름모가 1개일때 삼각형부분에 마름모 1개가 채워질때가 생기므로 +1이 한번더 됩니다.
    - 이 경우는 위에 삼각형이 있을 때만 가능하기기때문에 i가 홀 수 일때만 위에 삼각형이 있는지 체크하고 없으면 dp[i] = dp[i-1]+dp[i-2]+1을 사용하고, 있으면 dp[i]=dp[i-1]+dp[i-2]+1+dp[i-1]+1 이점화식을 사용하면 됩니다.
- 코드
  - ```
  def solution(n, tops):
      
      dp = [0 for _ in range(n*2+1)]
      if tops[0]==1:
          dp[1]=2
      else:
          dp[1]=1
      for i in range(2,n*2+1):
          if i%2==1:
              if tops[i//2]==1:
                  dp[i]=dp[i-1]+dp[i-2]+1+dp[i-1]+1
              else:
                  dp[i]=dp[i-1]+dp[i-2]+1
          else:
              dp[i]=dp[i-1]+dp[i-2]+1
          dp[i]=dp[i]%10007
                  
      return (dp[-1]+1)%10007
```

'Algorithm > Concepts' 카테고리의 다른 글

최단 경로 (다익스트라(Dijkstra)) (0)	2023.10.16
BFS(Breadth-First Search, 너비 우선 탐색), DFS(Depth-First Search, 깊이 우선 탐색) (0)	2023.10.16
이분 탐색(Binary Search) (1)	2023.10.14
분할 정복(Divide and Conquer) (0)	2023.10.12
탐욕법(Greedy) (1)	2023.10.10

컴돈AI

동적 계획법(DP, Dynamic Programming)

동적 계획법(DP, Dynamic Programming)

예시

예시 1 (피보나치 수)

예시 2 (평범한 배낭)

예시 3 (행렬 곱셈 순서)

예시 4 (구간 나누기)

예시 5 (산 모양 타일링)

'Algorithm > Concepts' 카테고리의 다른 글

티스토리툴바

동적 계획법(DP, Dynamic Programming)

동적 계획법(DP, Dynamic Programming)

예시

예시 1 (피보나치 수)

예시 2 (평범한 배낭)

예시 3 (행렬 곱셈 순서)

예시 4 (구간 나누기)

예시 5 (산 모양 타일링)

'Algorithm > Concepts' 카테고리의 다른 글

관련글

티스토리툴바