오늘 배운 것들

2. LCS(백준 9251)

최장 공통 부분 수열(LCS)를 구하는 문제

2-1. 조건 확인

수열 $X=(x_0, x_1, ... , x_n), Y=(y_0, y_1, ... , y_m)$의 LCS($LCS_{XY}$)를 구한다고 하자.
부분 수열 $X_{n-1}=(x_0, x_1, ... , x_{n-1})$이라고 하면

1. 최적 부분 구조
   1. $x_n = y_m$일 때
      $LCS_{XY}=LCS_{X_{n-1}Y_{m-1}}+x_n$
   2. $x_n ≠ y_m$일 때
      $LCS_{XY}=max(LCS_{X_{n-1}Y_{m}}, LCS_{X_{n}Y_{m-1}})$
2. 중복 부분 문제
   $LCS_{X_{n-k}Y_{m-k}}(k>1)$를 구하는 것은 $LCS_{X_{n-1}Y_{m-1}}$, $LCS_{X_{n-1}Y_{m}}$, $LCS_{X_{n}Y_{m-1}}$을 구하는 문제의 부분 문제이다.

2-2. LCS 길이 찾기

반복문을 이용한 상향식(Bottom-up) 접근을 사용한다.

최적 부분 구조에서 살펴본 식을 살짝 변형하면 ($c[i, j] = length(LCS_{X_iY_j})$)

1. $x_i = y_j$일 때
   $c[i, j]=c[i-1,j-1]+1$
2. $x_n ≠ y_m$일 때
   $c[i , j]=max(c[i-1, j], c[i, j-1])$
   이므로 이를 이용하여
   수열 X의 개수를 1부터 늘려가며 수열 Y와의 LCS길이를 찾는다.
   $c[i-1, j], c[i, j-1], c[i-1,j-1]$는 이전에 계산한 값을 사용한다.(메모이제이션)

import sys

input = sys.stdin.readline

def main() -> None:
    A = input().rstrip()
    B = input().rstrip()
    N_A = len(A)
    N_B = len(B)
    arr = [[0]*(N_B+1) for _ in range(N_A+1)]

    for i in range(1, N_A+1):
        for j in range(1, N_B+1):
            if A[i-1] == B[j-1]:
                arr[i][j] = arr[i-1][j-1]+1
            else:
                arr[i][j] = max(arr[i-1][j], arr[i][j-1])

    print(arr[N_A][N_B])

if __name__ == "__main__":
    main()

2-3. LCS 수열 출력

2-2에서 구한 행렬$c$로 LCS수열을 역참조할 수 있다.
조건문을 역으로 뒤집으면 된다.

1. $c[i, j]=c[i-1,j-1]+1$일 때
   $x_i = y_j$
   $c[i-1,j-1]$를 탐색
2. $c[i , j]=c[i-1, j]$일 때
   $x_n ≠ y_m$
   $c[i-1, j]$를 탐색
3. $c[i , j]=c[i, j-1]$일 때
   $x_n ≠ y_m$
   $c[i, j-1]$를 탐색

3. 평범한 배낭(백준 12865)

0-1 배낭 문제
물건들의 무게와 가치가 주어지면, 제한된 무게 안에서 최대 가치를 가지는 조합을 찾는 문제

3-1. 조건 확인

물건들 $I=((w_0, v_0), (w_1, v_1), ... , (w_n, v_n))$, 담을 수 있는 최대 무게 $K$가 주어졌을 때 최대 가치 $V_{I, K}$를 구한다고 하자.
부분 수열 $I_{n-j}=((w_0, v_0), (w_1, v_1), ... , (w_{n-j}, v_{n-j}))(j>n)$과 최대 무게 $K_0(K_0<K)$가 주어졌을 때의 최대 가치를 $V_{I_{n-k},K_0}$라고 하면

1. 최적 부분 구조
   $V_{I,K}=max(V_{I_{n-1},K}, V_{I_{n-1}, K-w_n}+v_n)$
2. 중복 부분 문제
   위 값은 반복해서 나타난다.

3-2. 코드

반복문을 이용한 상향식 접근을 사용한다.

def main() -> None:
    N, K = map(int, input().split())
    ITEMS = [None] + [tuple(map(int, input().split())) for _ in range(N)]
    arr = [[0 for _ in range(K+1)] for _ in range(N+1)]

    for n in range(1, N+1):
        for k in range(1, K+1):
            w, v = ITEMS[n]
            if w <= k:
                arr[n][k] = max(arr[n-1][k], arr[n-1][k-w]+v)
            else:
                arr[n][k] = arr[n-1][k]

    print(arr[N][K])

if __name__ == "__main__":
    main()