[LCS] Longest Common Subsequence, 최장 공통 부분 수열

두가지 LCS 

두 문자열의 연속된 공통 부분 : longest common substring

두 문자열의 공통 부분 : longest common subsequence

 

DP

이 문제의 핵심 풀이법은 DP 입니다.

 

연속된 공통 부분 (LCSubstring) 찾기

1. DP 채우기

집중하는 DP 칸의 문자가 서로 같다면, 그 앞까지의 문자열 LCS 값을 확인하고 +1 을 해줍니다.

if str1[i1] == str2[i2] :
    DP[i1][i2] = DP[i1-1][i2-1] + 1

 

2. 문자열 찾기

가장 값이 큰 DP 지점을 찾습니다.

거기서부터 왼쪽 방향으로 이동하면서 연속되는 문자열이 같은 부분만 뽑아냅니다.

 

공통 부분 (LCSubsequence) 찾기

1. DP 채우기

타겟 문자가 같은 경우

LCSubstring 과 같은 방식입니다.

타겟 문자가 다른 경우

이전까지의 문자열 중 LCS 값이 더 큰 걸 유지합니다.

 

2. 문자열 찾기

맨 끝 (DP 우하단) 에서부터 위의 과정을 거꾸로 진행하면 됩니다.

DP를 채울때 문자가 같은 경우 좌상칸에서 +1 해주었습니다. 문자가 다른 경우 좌 혹은 상칸에서 그 값을 그대로 가져왔습니다. 이 과정을 거꾸로 진행합니다.

1. 좌 or 상칸에 같은 값이 있다 -> 그곳으로 이동

2. 같은 값이 없다 -> 지금 칸의 문자를 결과 리스트에 저장하고 좌상칸으로 이동

끝까지 탐색하고나면 결과 리스트에는 찾고자하는 LCS의 역순 문자열이 저장됩니다.

 

아래 글이 이해에 큰 도움이 되었습니다

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence