[BOJ] 9251번: LCS (Python)

백준 9251번: LCS
Dynamic Programming

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

9251번: LCS

1. 문제 설명

LCS는 두개의 문자열이 주어졌을때, 공통적으로 가장 긴 subsequence를 찾는 문제이다.

이때, substring과 달리 subsequence는 문자열이 연속적이지 않아도 된다.

 

만약, 문자열 X와 Y가 다음과 같다고 하자.

X = <A, B, C, B, D, A, B>
Y = <B, D, C, A, B, A>

이때 생성될 수 있는 subsequence는 <A, B, A>, <C, B, A>, <B, D, A, B>, <B, C, A, B> 등이 있을 수 있고,

<B, D, A, B>, <B, C, A, B>는 LCS에 해당한다. (subsequence의 길이가 5인 것은 존재하지 않는다.) 

 

---

2. 문제 접근

a. Naive approach

문자열 X의 길이를 n, 문자열 Y의 길이를 m이라 하자.

가장 단순한 방법으로는 Y의 subsequence를 모두 구하고, 이를 X와 비교하면 될 것이다.

subsequence에서 각 문자별로 select 유무를 결정하므로 

따라서 시간복잡도는 O(n·2^m)이 될 것이다. (무조건 시간초과)

 

b. Dynamic Programming

Dynamic Programming으로 해결하려면 Optimal substructure를 세워야 한다.

Optimal substructure은 subproblem을 해결하기 위한 case로 구성된다.

들어가기 앞서 X_i는 X 문자열의 i번째 문자를 의미한다. 

 

case 1) X_i = Y_j인 경우 : 마지막 문자열이 일치하므로 X_i을 keep하고, X_i-1과 Y_j-1 간의 LCS를 해결한다. 

case 2) X_i ≠ Y_j인 경우 : 마지막 문자열이 일치하지 않으므로

X_i-1과 Y_j 간의 LCS를 계산하고 X_i과 Y_j-1 간의 LCS를 계산하여 둘 중에 최대값을 선택한다.

 

위의 case를 이용하여 nested loop를 돌면서 순차적으로 채워주면 된다.

따라서 시간복잡도는 O(n·m)이 될 것이다. (두 문자열의 길이의 곱만큼 2차원 배열을 채워주면 끝!)

 

---

3. 구현 코드

from sys import stdin

X = stdin.readline().strip()
Y = stdin.readline().strip()
len1, len2 = len(X) + 1, len(Y) + 1
dp = [[0] * len2 for _ in range(len1)]

for i in range(1, len1):
    for j in range(1, len2):
        if X[i - 1] == Y[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1            # case 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) # case 2
            
print(dp[-1][-1])

만약 예제가 다음과 같다면, dp는 아래와 같다.

ACAYKP
CAPCAK

 

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