[TIL] 동적 프로그래밍 문제 풀이

1. DP 문제 풀이

1. 9084번 - 동전

import sys

T = int(sys.stdin.readline())
for _ in range(T) :
    N = int(sys.stdin.readline())
    coin = list(map(int, sys.stdin.readline().split()))
    M = int(sys.stdin.readline())
    
    dp = [0] * (M+1) # 각각의 금액에 대한 동전으로 만들 모든 방법의 수 저장
    dp[0] = 1 # 기저 값으로 지정
    for c in coin :
        for i in range(1, M+1) :
            if i >= c :
                dp[i] += dp[i-c]
    print(dp[M])

내가 이해한 방식

간단하게 생각하면 간단하다고 할 수 있지만 저 방식을 생각해내는 것 자체가 힘들었다. 다른 동료분의 힌트를 듣고 겨우 알았다..😭

---

2. 9251번 - LCS

부분 수열(부분 시퀀스) : 어떤 수열의 부분 수열은 그 수열에서 0개 이상의 요소를 뺀 것과 같다.

수열 X = (x1,x2, ....xm) 에 대해 다른 수열 Z = (z1, z2, ....zk)가 X의 부분 수열이 되기 위해서는
j = 1, 2, ....k에 대해 xij = zj 인 염격히 증가(strictly increasing)하는 X의 인덱스 시퀀스(i1, i2, .... ik)가 존재해야한다.

공통 부분 수열(Common Subsequence)
:  두 수열 X, Y에 대해 수열 Z가 두 가지 모두에 대해 부분 수열이라면 Z를 X, Y의 공통 부분 수열이라고 한다.

1. LCS 특성

    : 부분 문제들은 자연스럽게 두 입력 수열의 접두사 쌍에 대응된다.

      수열 X = (x1, x2, .... , xm)의 i번째 접두사는 Xi = (x1, x2, ..., xi)로 정의된다.

      X0 = (),  X1 = (x1), X2 = (x1, x2) 와 같이 정의된다.

 

2. LCS의 최적 부분 구조

입력 수열 X = (x1, x2, ..., xm) / Y = (y1, y2, ....., yn) 의 LCS Z = (z1, z2, ..., zk) 에 대해

• xm = yn 이면, zk = xm = yn이고 Zk-1 = Xm-1 와 Yn-1 의 LCS이다.
• xm ≠ yn 이면, zk ≠ xm은 Z  = Xm-1 과 Y의  LCS이다.
• xm ≠ yn 이면, zk ≠ yn은 Z  = X 과 Yn-1의  LCS이다.

3. 재귀해

• xm = yn일 경우 Xm-1 와 Yn-1 의 LCS 를 찾는다.
• xm ≠ yn일 경우
  • Xm-1 과 Y의  LCS 를 찾는다.
  • X 과 Yn-1의  LCS 를 찾는다.
  • 위의 경우 중에서 더 긴 것이 LCS가 된다.

 

4. 구현

import sys

X = list(sys.stdin.readline().strip())
Y = list(sys.stdin.readline().strip())

def LCS_Length(x, y) :
    m, n = len(x), len(y)
    dp = [[0] * (n+1) for _ in range(m+1)]
    for i in range(1, m+1) :
        for j in range(1, n+1) :
            if x[i-1] == y[j-1] : # 두 문자가 같을 경우
                dp[i][j] = dp[i-1][j-1] + 1
            # 같지 않을 경우 두 값 중 큰 값 선택
            elif dp[i-1][j]  >= dp[i][j-1] : 
                dp[i][j] = dp[i-1][j]
            else :
                dp[i][j] = dp[i][j-1]
    print(dp[m][n])
LCS_Length(X, Y)

어려워서 알고리즘 책을 참고하여 풀었다. 솔직히 완벽하게 이해했다고는 할 수 없지만 이런식으로 푼다는 것은 알았다.
주의할 점은 dp 테이블에서는 1번 인덱스 부터 시작하기 때문에 i,j 역시 1부터 시작한다. 그러므로 입력받은 수열에 접근할 때
1씩 빼준 후 접근해야 올바른 값이 나온다.

위의 코드 동작 과정

 

5. 9252번 - LCS 2

import sys

X = list(sys.stdin.readline().strip())
Y = list(sys.stdin.readline().strip())

def LCS_Length(x, y) :
    m, n = len(x), len(y)
    dp = [[0] * (n+1) for _ in range(m+1)]
    for i in range(1, m+1) :
        for j in range(1, n+1) :
            if x[i-1] == y[j-1] : # 두 문자가 같을 경우
                dp[i][j] = dp[i-1][j-1] + 1
            # 같지 않을 경우 두 값 중 큰 값 선택
            elif dp[i-1][j]  >= dp[i][j-1] : 
                dp[i][j] = dp[i-1][j]
            else :
                dp[i][j] = dp[i][j-1]
    print(dp[m][n])
    
    # 9252번 - LCS2 
    # https://www.acmicpc.net/problem/9252
    # dp 배열을 반대로 타고 올라가기!!
    if dp[m][n] > 0 :
        i, j = m, n
        result = ''
        while i != 0 and j != 0 :
            if x[i-1] == y[j-1] :
                result = x[i-1] + result
                i -= 1
                j -= 1
            elif dp[i-1][j]  >= dp[i][j-1] :
                i -= 1
            else :
                j -= 1
        print(result)
                    
LCS_Length(X, Y)

관련 문제 중에서 LCS 수열도 출력하는 문제가 있어 풀어보았다.
처음에는 새로운 배열을 만들어서 해야하나 생각했는데 어차피 만들어진 dp배열을 이용하는 것이 좋을 것 같아 
동료분의 힌트를 듣고 구현해보았다.

가장 좋았던 힌트는 만든 것을 거꾸로 타고 올라가는 방식을 생각하는 것이었다!

 

6. 1958번 - LCS 3

import sys

X = list(sys.stdin.readline().strip())
Y = list(sys.stdin.readline().strip())
Z = list(sys.stdin.readline().strip())

def LCS_Length(x, y, z) :
    m, n, k = len(x), len(y), len(z)
    dp = [[[0] * (n+1) for _ in range(m+1)] for _ in range(k+1)]
    for l in range(1, k+1) :
        for i in range(1, m+1) :
            for j in range(1, n+1) :
                if x[i-1] == y[j-1] == z[l-1] :
                    dp[l][i][j] = dp[l-1][i-1][j-1] + 1
                else :
                    dp[l][i][j] = max(dp[l-1][i][j], dp[l][i-1][j], dp[l][i][j-1])
    print(dp[k][m][n])
                    
LCS_Length(X, Y, Z)

처음에 푼 LCS 문제에서 3차원으로 바꾼 것뿐이다. 이제 어느 정도 원리가 이해가 되었다. 😁

---

3. 12865번 - 평범한 배낭

0/1 Knapsack Problem
: item 을 분할 할 수 없다. 즉, 선택하거나 선택하지 않는 경우만 존재

import sys

N, K = map(int, sys.stdin.readline().split())

# dp[i][j] = i번째 가방까지 가능하고 j 용량일 때 최대 가치
dp = [[0] * (K+1) for _ in range(N+1)]
# obj[0] = 무게 / obj[1] = 가치
obj = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

for i in range(1, N+1) :
    w, v = obj[i-1]
    for j in range(1, K+1) :
        # 가능한 용량 j보다 현재 물건의 용량이 클 경우
        if w > j :
            dp[i][j] = dp[i-1][j]
        # 작을 경우
        # 1. 전의 물건을 넣었을 경우
        # 2. 현재 물건을 넣고 나머지 용량에 대한 가치를 더한 경우
        else :
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)       
             
print(dp[N][K])

동작 그림

몇 시간을 고민해서 문제를 풀었지만 틀리거나 시간 초과가 계속 발생했다.
dp를 어디에 적용해야할지는 알겠는데 이의 점화식을 찾아내는 것이 어려웠다.
결국 블로그를 참고했지만, 우선 앞선 동전 문제와 비슷하다는 것을 알았다.

< 참고 블로그 > https://gom20.tistory.com/80