[Algorithm] LCS(최장 공통 부분 수열)

input: 두 문자열
output: 겹치는 최장 길이 문자열 

LCS: Longest Common Subsequence

백준에서 LCS문제를 풀게 되었는데 이것 자체가 하나의 알고리즘이라고 해서 정리하게 되었다. 

LCS는 DP기반의 알고리즘이고, Subsequence이므로 꼭 연속은 아니어도 된다. 부분부분 잘라서 존재하기만 해도 ㄱㅊ

 

 

백준에서 들은 예는 다음과 같다. 

 

ACAYKP
CAPCAK

에서 LCS는 ACAK이다. 

 

 

 

 

이렇게 세팅해놓고 시작한다. 

 

 

글자가 같을때는 그 전줄전의값 + 1 해서 넣어주면 되는데, 다를때는 윗줄과 옆칸을 비교해서 더 큰값을 넣어준다. 

 

 

코드 !!

 

import sys

str1 = sys.stdin.readline().rstrip('\n')
str2 = sys.stdin.readline().rstrip('\n')

data = [[0] * (len(str1) + 1) for _ in range(len(str2) + 1)]
for row in range(1, len(str2) + 1):
    for j in range(1, len(str1) + 1):
        if str1[j - 1] == str2[row - 1]:
            data[row][j] = data[row-1][j - 1] + 1
        else:
            data[row][j] = max(data[row][j - 1], data[row - 1][j])
# print(data)
print(data[-1][-1])

 

근데 너무 어렵다;;