Python으로 알고리즘 공부 11. 최장 공통 부분 수열

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

• 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제

• 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

• diff 명령은 LCS 문제를 해결하는 데 기반을 둔다.

diff utility

다음과 같이 두 항목이 있다고 하자.

a b c d f g h j q z

a b c d e f g i j k r x y z

여기서 공통이 되는 가장 긴 부분은 다음과 같다.

a b c d f g j z

두개 항목을 비교하여 추가(+)되거나 삭제(-)된 부분을 다음과 같이 나타낸다.

e   h i   q   k r x y
+   - +   -   + + + +

LCS 함수의 정의

• 두 수열은 다음과 같이 정의.

• ​, ​.

Python Code

A = "ACAYKP"
B = "CAPCAK"
​
lcs = [[0 for i in range(len(A)+1)] for j in range(len(B)+1)]
​
for i in range(1, len(A)+1):
    for j in range(1, len(B)+1):
        if A[i-1] == B[j-1]:
            lcs[i][j] = lcs[i-1][j-1] + 1
        else:
            lcs[i][j] = max(lcs[i][j-1], lcs[i-1][j])
                        
print(lcs[len(A)][len(B)])

lcs 출력결과

0 0 0 0 0 0 0 
0 0 1 1 1 1 1 
0 1 1 1 2 2 2 
0 1 2 2 2 3 3 
0 1 2 2 2 3 3 
0 1 2 2 2 3 4 
0 1 2 3 3 3 4 

참조

• https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

• https://en.wikipedia.org/wiki/Diff_utility

• https://www.acmicpc.net/problem/9252