[백준알고리즘] 9251번: LCS -Python

[백준알고리즘] 9251번: LCS -Python

https://www.acmicpc.net/problem/9251

9251번: LCS

이번 문제는 LCS(Longest Common Subsequence) 문제이다.

임의의 두 문자열에서 각각의 sub sequence가 같을 때, 가장 긴 길이를 구하는 문제다.

이와 같은 문제를 전에 풀었었는데 엉뚱한 데에 정신이 팔려서 시간을 많이 잡아먹었다..

 

문제를 풀기 위해서는 작은 sub sequence에서부터 직접 하나씩 늘려주었다.

예를 들어 문제의 예시에 나온 두 문장을 비교해보겠다.

ACAYKP

CAPCAK

앞의 문자열의 sub sequence를 S1, 뒤의 문자열의 sub sequence를 S2라고 했을 때 문자를 하나씩 늘려가면서 비교해보도록 하겠다.

 

S1: A

S2: C

두 문자열로 만들 수 있는 LCS의 길이는 0이다.

 

S1: A

S2: CA

두 문자열로 만들 수 있는 LCS의 길이는 1이다.

 

S1: A

S2: CAP

두 문자열로 만들 수 있는 LCS의 길이는 1이다.

 

S1: A

S2: CAPC

두 문자열로 만들 수 있는 LCS의 길이는 1이다.

위와 같이 S2가 끝까지 CAPCAK까지 구하게 된다면 S1을 하나씩 늘려주면 된다.

 

S1: AC

S2: C

두 문자열로 만들 수 있는 LCS의 길이는 1이다.

 

S1: AC

S2: CA

두 문자열로 만들 수 있는 LCS의 길이는 1이다.

.. 반복하면 된다!

 

표를 만들고 채우기 위해 값이 증가하는 방식을 살펴보면 다음과 같이 정의할 수 있다.

 

S1과 S2에 가장 최근에 추가된 글자가 서로 같을 때

matrix[i][j] = matrix[i - 1][j - 1] + 1                          // 길이는 (두 글자가 추가되기 전 가장 큰 길이 + 1)이 됨

추가된 글자가 서로 다르다면

matrix[i][j] = max(matrix[i][j - 1], matrix[i - 1][j])          // 기존에 주어진 문자열로 만들 수 있던 최대 길이를 갖게 됨

 

표를 보여주고 설명을 덧붙이자면,

	0	C	A	P	C	A	K
0	0	0	0	0	0	0	0
A	0	0	1	1	1	1	1
C	0	1	1	1	2	2	2
A	0	1	2	2	2	3	3
Y	0	1	2	2	2	3	3
K	0	1	2	2	2	3	4
P	0	1	2	3	3	3	4

위 표를 matrix라고 하면, 빨간색 부분인 matrix[3][6]는 두 sub sequence가 ACA와 CAPCA일 때의 상황으로, 추가된 문자가 A로 일치하기 때문에 이 문자를 LCS에 포함시킨다고하면 AC와 CAPC일 때의 최대 길이 +1을 해주면 된다.

matrix[3][6] = matrix[2][5] + 1

 

보라색 부분인 matrix[7][7]은 두 sub sequence가 ACAYKP와 CAPCAK로 추가된 문자가 서로 다르기 때문에 추가된 문자를 LCS에 포함시킬 수 없는 상황이다. 따라서 ACAYK와 CAPAK일 때의 LCS 길이와 ACAYKP와 CAPCA일 때의 LCS 길이 중 더 큰 값이 현재 만들 수 있는 가장 큰 LCS 길이 값이다.

matrix[7][7] = max(matrix[6][7], matrix[7][6])

 

코드는 아래와 같다.

import sys

S1 = sys.stdin.readline().strip().upper()
S2 = sys.stdin.readline().strip().upper()
len1 = len(S1)
len2 = len(S2)
matrix = [[0] * (len2 + 1) for _ in range(len1 + 1)]

for i in range(1, len1 + 1):
    for j in range(1, len2 + 1):
        if S1[i - 1] == S2[j - 1]:
            matrix[i][j] = matrix[i - 1][j - 1] + 1
        else:
            matrix[i][j] = max(matrix[i - 1][j], matrix[i][j - 1])

print(matrix[-1][-1])

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다