최대 1 분 소요

LCS란

두 개의 문자열에서 공통으로 나타나는 가장 긴 부분 수열을 찾는 문제입니다. 여기서 부분 수열이란 원래 문자열에서 문자의 순서를 유지하면서 몇몇 문자를 제거해 얻을 수 있는 새로운 문자열을 의미합니다.

ACAYKP
CAPCAK
# 결과값 : 4 (ACAK)

예를 들면 위 예시와 같이 ACAYKP, CAPCAK의 LCS는 ACAK로 4의 값을 가집니다.

LCS의 접근방식

LCS 문제는 DP을 이용해서 풀수 있습니다. 두 문자열의 각 문자를 비교하면서 공통된 부분을 찾아내고, 이를 바탕으로 최장 길이의 부분 수열을 구하는 방식입니다. 이 과정에서 2차원 배열을 사용해, 중복되는 계산을 피하고 효율적으로 LCS를 구할 수 있습니다.

DP를 이용한 LSC Algorithm

두 문자열 ‘ACAYKP’, ‘CAPCAK’를 가지고 LCS를 구하는 방법을 알아보겠습니다.
두 문자열 X = ‘ACAYKP’, Y = ‘CAPCAK’의 길이를 각각 m, n이라고 합니다. 만약 $x_{1},x_{2},…,x_{i}(1 \leq i \leq m)$와 $y_{1},y_{2},…,y_{j}(1 \leq j \leq n)$가 있을 때 $x_{i}$와 $y_{j}$가 같으면 해당 문자를 제외한 LCS(i-1,j-1)에 1을 더한 값이 되고, 같지 않으면 Max(LCS(i-1,j), LCS(i,j-1))이 됩니다.

UDP

Python Code

import sys
input = sys.stdin.readline
x = input().rstrip()
y = input().rstrip()

table = [[0] * (len(x)+1) for _ in range(len(y)+1)]
for i in range(1,len(y)+1):
    for j in range(1,len(x)+1):
        # x_i 와 y_j가 같을때
        if x[j-1] == y[i-1]:
            table[i][j] = table[i-1][j-1]+1
        # x_i 와 y_j가 다를때
        else:
            table[i][j] = max(table[i-1][j], table[i][j-1])

print(table[-1][-1]) # output : 4

참고