백준(9251) - LCS Python

백준(9251) - LCS

문제풀이: LCS알고리즘, 파이썬

LCS (Longest Common Subsequence) 최장 공통 부 문자열 알고리즘 문제이다.

X = ACAYKP
Y = CAPCAK

X와 Y가 각각 위 처럼 주어졌을 때, 공통되는 부 문자열 중 가장 길이가 긴 문자열을 구해야 한다.

길이가 1인 부 문자열은 A, C, K, P 이고

길이가 2인 부 문자열은 AC, AA, Ak, CA …. 등이 있고

길이가 3인 부 문자열은 ACA, CAK, CAP

길이가 4인 부 문자열은 ACAK 이고 길이가 5인 부 문자열은 없으므로

위의 예제에선 길이가 가장 긴 부 문자열의 길이는 4가 된다.

• X의 문자열의 길이를 i, Y의 문자열의 길이를 j라고 하자.
• LCS(X(i), Y(j)) 가 최장 부 문자열을 구하는 연산이라고 가정하고, 맨 뒤의 문자열 부터 확인해 보자.
  • X[i]와 Y[j]가 같다면 문자열 길이를 1 증가 시키면 되므로 LCS(X(i), Y(j)) = LCS(X(i-1), Y(j-1)) + 1 라고 볼 수 있다,
  • X[i]와 Y[j]가 다르다면 LCS(X(i), Y(j)) = max(LCS(X(i), Y(j-1)), LCS(X(i-1), Y(j)) ) 라고 볼 수 있다.
• 위의 과정을 2차원 배열로 확인해 보자.

• 위의 주황색 영역을 구해본다고 하면, X[3]과 Y[2]의 값이 ‘A’로 서로 같으므로 arr[2][3] = a[1][2] + 1가 된다.

  👉 문자가 같을 경우 주황색 영역의 값은 노랑색 영역의 값 + 1

• 이번에는 문자값이 다른 경우이다. 이때는 두 노랑생 영역 중 큰 값을 넣어 줘야 한다.

여기서 우리는 arr[i][j] 의 값을 채우기 위해서는 arr[i-1][j-1], arr[i-1][j], arr[i][j-1]을 알아야 한다는 것을 알 수 있다.

• 따라서 2차원 리스트의 첫번째 인자에 0 을 넣어 처음에 0으로 초기화 시켜주는 과정이 필요하다.

• 위처럼 초기화가 되었다면 화살표 방향으로 순차적으로 비교하면서 채워주면 된다.

• 연산 수행결과 모습이고, 최장 수열의 길이는 4인 것을 확인할 수 있다.

import sys
input = sys.stdin.readline

S = input().rstrip()
P = input().rstrip()

n = len(S)
m = len(P)
arr = [[0] * (n+1) for _ in range(m + 1)]

for i in range(1, m + 1):
    for j in range(1, n + 1):
        if S[j-1] == P[i-1]:
            arr[i][j] = arr[i-1][j-1] + 1
        else:
            arr[i][j] = max(arr[i][j-1], arr[i-1][j])

print(arr[-1][-1])