다이나믹 프로그래밍 - 바킹독 유튜브보고 정리

개념

• 여러개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘
• 다양한 문제를 접해보고 풀어보는 것이 좋다.
• 문제를 해결하기 위한 점화식을 찾아낸 후 점화식을 차례로 구해나가면서 답을 알아내는 형태의 알고리즘

DP 푸는 과정

• 테이블 정의하기
• 점화식 찾기
• 초기값 정하기

boj-1463

1. 테이블 정의하기
   1. D[i]= i를 1로 만들기 위해 필요한 연산 사용 횟수의 최소값
2. 점화식 찾기
   1. D[12] =?
   2. 세가지 연산이 가능하다.
      1. 3으로 나누거나(D[12] = D[4] +1)
      2. 2로 나누거나(D[12] = D[6] +1
      3. 1을 빼거나(D[12] = D[11] +1)
   3. 결국 D[k]는 min(D[k/3]+1, D[k/2]+1, D[k-1]+1) 형태라는 것을 알 수 있다.
3. 초기값 정의하기
   1. D[1] = 0
   2. 초기값을 D[1]로 설정해주면 바로 점화식대로 연산이 가능하다.

X = int(input())

dp = [0] * (X+1)

for i in range(2, X+1):
    dp[i]= dp[i-1] +1
    if not i % 3: dp[i] = min(dp[i//3] +1, dp[i])
    if not i % 2: dp[i] = min(dp[i//2]+1, dp[i])

print(dp[X])

boj-9095

1. 테이블 정의하기
   1. D[i]= i를 1, 2, 3의 합으로 나타내는 방법의 수
2. 점화식찾기
   1. D[4]
   2. 1+1+1+1, 3+1, 2+1+1, 1+2+1(3을 1,2,3의 합으로 나타내는 방법) +1 D[3]
   3. 1+1+2, 2+2 (2를 1,2,3의 합으로 나타내는 방법) +2 D[2]
   4. 1+3(1을 1,2,3의 합으로 나타내는 방법) +3 D[1]
   5. D[4] = D[1] + D[2] + D[3]
   6. D[k] = D[k-3] + D[k-2] + D[k-1]
3. 초기값 정하기
   1. 점화식 형태가 k-3의 형태이기 때문에 초기값은 3까지 주어져야 한다.

T = int(input())
dp = [0] * (11)
dp[1] = 1
dp[2] = 2
dp[3] = 4

for _ in range(T):
    n = int(input())

    for i in range(4, n+1):
        dp[i] = dp[i-3] + dp[i-2] + dp[i-1]
    print(dp[n])

boj-2579

1. 테이블 정의하기
   1. D[i] = i번째 계단까지 올라섰을 때 점수 합의 최댓값(연속한 계단을 밟지 않아야 한다는 조건을 충족시키기 어렵다.)
   2. D[i][j] = 현재까지 j개의 계단을 연속해서 밟고 i번째 계단까지 올라섰을 때 점수 합의 최댓값, 단 i번째 계단은 반드시 밟아야 함(2차원이 된 이유 계단을 연속해서 밟은 정보를 저장해야한다.)
2. 점화식 찾기
   1. D[k][1] = ?
      1. 현재까지 1개의 계단을 연속해서 밟고 k번째 계단까지 올라섰을때 점수합의 최댓값
      2. 1개의 계단을 연속해서 밟았다는 의미는 k-1번째 계단을 밟지 않았다는 의미이다. 그렇다면 k-2번째 계단을 밟은 것이다.
   2. D[k][1] = max(D[k-2][1], D[k-2][2]) + S[k]
   3. D[k][2] = D[k-1][1], + S[k]
3. 초기값 정하기
   1. k-2 형태가 존재하기 때문에 dp테이블을 인덱스 2까지 초기화 해준다.
      1. dp[1][1] = stairs[1]
      2. dp[1][2] = 0
      3. dp[2][1] = stairs[2]
      4. dp[2][2] = stairs[1] + stairs[2]

N = int(input())
stairs = [0] + [int(input()) for _ in range(N)]

dp = [[0] * 3 for _ in range(N+1)]

dp[1][1] = stairs[1]
dp[1][2] = 0
dp[2][1] = stairs[2]
dp[2][2] = stairs[1]+ stairs[2]

for i in range(3, N+1):
    dp[i][1] = max(dp[i-2][1] , dp[i-2][2])+ stairs[i]
    dp[i][2] = dp[i-1][1] + stairs[i]
    
print(max(dp[N][1], dp[N][2]))

boj-2579를 1차원 배열 dp로 스스로 생각해서 바꿔보기

관점을 달리하면 또 다른 dp식이 도출 될 수 있다.

1. 테이블 정의하기

   1. D[i] = i번째 계단까지 올라섰을 때 밟지 않을 계단의 합의 최솟값, 단 i번째 계단은 반드시 밟지 않을 계단으로 선택해야함

2. 점화식 찾기

   1. k번째 계단을 밟지 않았으면 k-1번째 계단은 무조건 밟아야 한다.
   2. k-2번째 계단이나 k-3번째 계단 중에서 하나는 무조건 밟은 계단으로 선택해야 한다.
   3. D[1] = 10, D[2] = 20 D[3] = 15 D[4] = D[1]을 안 밟거가 D[2]를 안 밟는 방법 두가지가 있고 그 중 최소값을 구하고 계단값을 더해준다.

3. 초기값 설정

   1. dp 1,2,3 모두 계단 123으로 초기화해준다.
   2. 밟지않는 최소값으로 계산하는 것이고 세번째까지는 자기 자신 하나만 안 밟을 수도 있기 때문에 계단값으로 초기화 해준다.

   import sys
   input = sys.stdin.readline
   
   N = int(input())
   
   stairs = [0] + [int(input()) for _ in range(N)]
   
   dp = [0] * 301
   
   if N <=2:
       print(sum(stairs))
       sys.exit(0)
   
   dp[1] = stairs[1]
   dp[2] = stairs[2]
   dp[3] = stairs[3]
   
   for i in range(4, N):
       dp[i] = min(dp[i-2] , dp[i-3]) + stairs[i]
   
   print(sum(stairs) - min(dp[N-1] , dp[N-2]))

   boj-1149

   1. 테이블 정의하기

      1. d[i][0] = i번째 집까지 칠할 때 비용의 최솟값, i번째 집은 빨강
      2. d[i][1] = i번째 집까지 칠할 때 비용의 최솟값, i번째 집은 초록
      3. d[i][2] = i번째 집까지 칠할 때 비용의 최솟값, i번째 집은 파랑

   2. 점화식 찾기

      1. d[k][0] = min(d[k-1][1], dp[k-1][2]) + color[k][0]
      2. d[k][1] = min(d[k-1][0], d[k-1][2]) + color[k][1]
      3. d[k][2] = min(d[k-1][0], d[k-1][1] )+ color[k][2]

   3. 초기값 설정

      dp[1][0] = colors[1][0]
      dp[1][1] = colors[1][1]
      dp[1][2] = colors[1][2]

      첫번째 dp 테이블에 각 색깔 값만 지정해주면 된다.

N = int(input())

colors = [0]+[list(map(int, input().split())) for _ in range(N)]

dp = [[0] * 3 for _ in range(N+1)]

dp[1][0] = colors[1][0]
dp[1][1] = colors[1][1]
dp[1][2] = colors[1][2]

for i in range(2, N+1):
    dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + colors[i][0]
    dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + colors[i][1]
    dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + colors[i][2]

print(min(dp[N]))

boj-11762

1. 테이블 정의하기
   1. D[i] = 2 X i 크기의 직사각형을 채우는 방법의 수
2. 점화식찾기
   1. 왼쪽부터 타일을 채워나간다고 했을 때 타일을 채우는 방법은 2가지가 있다.
   2. 1x2로 채우는 방법 2x1로 채우는 방법
   3. 예를 들어보자 n개의 타일을 채운다는 가정하에
   4. 2 x 1 로 채우면 남는 타일은 한 줄을 뺀 나머지 2 x n-1이 남게 된다.
   5. 1 x 2로 채우면 2 x n-2 + 2 가 되는데 사실 이 2는 1 x2 타일이 아니면 채울 수 없으므로 2 x n-2와 같다고 볼 수 있다.
   6. 따라서 d[n] = d[n-1] + d[n-2]라는 점화식을 얻을 수 있다.
3. 초기값설정
   1. d[2]까지 설정을 해주면 된다.

import sys
N = int(sys.stdin.readline())
dp = [0] * (N+1)
dp[0] = 1
dp[1] = 1
for i in range(2, N+1):
    dp[i] = dp[i-2] + dp[i-1] % 10007

print(dp[N])

그 밖의 다른 문제들

• 구간합 boj-11659
  • 배열의 인덱스까지의 모든 합을 구해준다.
  • 특정 구간의 합을 구하고 싶다면 prefix[j] - prefix[i-1] 를 해주면 i부터 j까지의 구간합을 O(1)로 구할 수 있기 때문에 유용하다.
• 경로추적 boj-12852
  • 지금까지 지나온 구간들의 경로를 저장해두는 테이블을 따로 만들어준다.
  • 그 테이블을 역으로 추적하면서 지나온 경로들을 알 수 있다.

N = int(input())

path = [0] * (N+1)
dp = [0] * (N+1)

for i in range(2, N+1):
    dp[i] = dp[i-1]+1
    path[i] = i-1
    
    if i % 2 == 0 and dp[i] > dp[i//2] +1:
        dp[i] = dp[i//2] +1
        path[i] = i//2
        
    if i % 3 == 0 and dp[i] > dp[i//3] +1:
        dp[i] = dp[i//3] +1
        path[i] = i//3
print(dp[N])
cur_num = N
while True:
    print(cur_num, end = " ")
    if cur_num == 1:
        break
    cur_num = path[cur_num]

이번주 목표 문제

• boj-1943 동전 분배 Gold3
• boj-23257 승부조작 Gold3