LCS(Longest Common Subsequence) 최장 공통 부분 수열

최장 공통 부분 수열 (Longest Common Subsequence) 문제란?

 주어진 여러개의 수열 모두 부분수열이 되는 수열중 가장 긴 것을 찾는 문제이다.

 이 문제와 아래 최장공통 부분 문자열 문제와 혼동하면 안된다.

 

최장 공통 부분 문자열(Longest Common Substring) 문제란?

 주어진 여러개의 문자열 모두 부분수열이 되는 문자열 중 가장 긴 문자열을 찾는 문제

 

예시

가나다라마바사

가하나카마바사

 

LCSubsequence

가나다라마바사

가하나카마바사

 

LCSubstring

가나다라마바사

가하나카마바사

 

LCS 문제는 더 작은 '부분문제'로 나뉠 수 있고 이것을 반복해 더 간단한 부분문제로 쪼갤 수 있다. 즉 동적 프로그래밍 문제풀이기법으로 접근될 수 있다.

 

부분문제는 수열이 짧아질 수록 간단해진다. 

아래 백준 LCS 문제의 예를 가져와 보았다.

백준 9251 LCS 문제

9251번: LCS

문제에서 주어진 두 수열은 ACAYKP, CAPCAK이다.

 

여기서 ACAYKP 를 X수열, CAPCAK를 Y수열이라 하고 X수열의 꼬리를 잘라 X가 포함하는 문자의 수로 정의한다면

X1 = A

X2 = AC

X3 = ACA

X4 = ACAY

X5 = ACAYK

X6 = ACAYKP

로 명명할 수 있다. 

 

LCS 를 구하는 원리

1. dp배열을 만들어 준다.
2. 배열 x와 배열 y를 비교하며 배열 y의 문자 하나를 배열 x1,x2,...xn 과 비교해 나간다.
3. 문자를 비교해서 값이 같다면 끝 문자가 같다는 의미는 두 문자열의 LCS는 최소 1이상이라는 의미로 마지막 문자를 자른 이전 LCS (xn-1)(yn-1) 값에 +1을 해준다.
   값이 다르다면? LCS(xn)(yn-1) or LCS(xn-1)(yn) 의 비교중 최댓값을 대입한다.
4. 모든 배열을 완성한 후 가장 큰겂이 최장공통 부분 문자열이다.

코드 구현(파이썬)

import sys
input = sys.stdin.readline

x = [0]+ list(map(str,input().strip()))
y = [0]+ list(map(str,input().strip()))
dp = [[0]*len(x) for _ in range(len(y))]

for i in range(1, len(y)):
    for j in range(1,len(x)):
        if y[i]==x[j]:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])

lcs = 0
for row in dp:
    lcs = max(lcs,max(row))
print(lcs)

 

 

<참고한 블로그및 사이트>

https://pangtrue.tistory.com/264

[알고리즘] LCS(Longest Common Subsequence)

https://ko.wikipedia.org/wiki/%EC%B5%9C%EC%9E%A5_%EA%B3%B5%ED%86%B5_%EB%B6%80%EB%B6%84_%EC%88%98%EC%97%B4

최장 공통 부분 수열 - 위키백과, 우리 모두의 백과사전

https://yunanp.tistory.com/20

[LCS] Longest Common Subsequence (최장 공통 부분 문자열)