[Python - Dynamic Programming] 9251 LCS

📌 문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

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

📌 입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

📌 출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

📌 문제 풀이

👨‍🏫 접근

처음에는 이 문제를 다이나믹 프로그래밍으로 풀 수 있나 싶었다. 각 문자열에서 가능한 최대 문자열의 길이를 저장하고 그 데이터를 활용함으로써 풀어야 하지만, 쉬워보이지 않았기 때문이다. 문제를 풀어냈을 때는 꽤 간단한 로직이었다.

 

기준 문자열을 하나 정한 다음, 그 기준 문자열 1개씩 비교 문자열을 순회하면서 값을 저장하면 된다. 이때, 매번 테이블의 모든 값을 최대로 해야 하므로, 모든 단어를 순회하면서 그 단어의 LCS 길이를 임시 변수에 저장한다. 어차피 임시변수에 각 단어의 LCS 값을 저장해도 순회하면서 더 이상 문자열이 없다면 LCS을 수정할 수 없기 때문에 값을 수정하지 않게 된다.

 

예를 들어, 기준 문자열이 CAPCAK이고, 비교 문자열이 ACAYKP라면,

첫 번째 문자인 C로 비교 문자열을 탐색한다.

A	C	A	Y	K	P
0	1	0	0		0

여기서 가장 긴 문자열이 0이므로, C와 같은 문자열에 대하여 LCS + 1 값인 1을 저장해둔다.

두 번째 문자인 A로 비교 문자열을 탐색한다.

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

첫 번째 A도 마찬가지로 가장 긴 문자열이 0이기 때문에 LCS + 1인 1을 저장한다. 그 다음 C에서 LCS가 1이기 때문에 임시 변수에 LCS 값을 1로 수정해두고 다음 문자로 넘어간다. 다음 문자인 A가 일치하기 때문에, LCS + 1인 2의 값을 저장한다.

세 번째 문자인 P로 비교 문자열을 탐색한다.

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

같은 이유로 임시변수에 2를 저장하고 P가 일치하기 때문에 3을 저장한다.

네 번째 문자인 C로 비교 문자열을 탐색한다.

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

LCS + 1인 2를 저장한다.

다섯 번째 문자인 A로 비교 문자열을 탐색한다.

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

같은 이유로 값을 수정한다.

마지막으로 K를 통해 비교 문자열을 탐색하면,

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

최종적인 LCS 테이블이 완성된다. 이때, K가 가장 큰 값이므로 max(LCS 테이블)을 출력한다.

👨‍🏫 문제 풀이

📄 전체 코드

import sys
input = sys.stdin.readline

w1 = input().strip()
w2 = input().strip()

len_w1, len_w2 = len(w1), len(w2)
d = [0] * len_w2

for i in range(len_w1):
    tmp = 0 # 임시로 받을 변수
    for j in range(len_w2):
        if tmp < d[j]: # 더 긴 LCS를 발견하였다면, 값을 수정
            tmp = d[j]
        elif w1[i] == w2[j]:
            d[j] = tmp + 1
    print(d)

print(max(d))

📄 준비

import sys
input = sys.stdin.readline

w1 = input().strip()
w2 = input().strip()

len_w1, len_w2 = len(w1), len(w2)
d = [0] * len_w2

기준 문자열에 대해서 LCS를 담을 dp 테이블을 초기화한다.

📄 풀이

for i in range(len_w1):
    tmp = 0 # 임시로 받을 변수
    for j in range(len_w2):
        if tmp < d[j]: # 더 긴 LCS를 발견하였다면, 값을 수정
            tmp = d[j]
        elif w1[i] == w2[j]:
            d[j] = tmp + 1
    print(d)

print(max(d))

첫 번째로 받은 문자열의 각 글자를 통해 두 번째 문자열을 순회한다. tmp는 각각 상황에서의 가장 큰 LCS를 담을 임시 변수이다.

 

더 긴 LCS를 발견할 때마다 그 값을 저장한다. 만약 더 길지 않으며 동시에 둘의 문자가 일치한다면 그것은 LCS이기 때문에 tmp 에서 +1 한 다음 저장한다.

📌 총평

미친 난이도.