[BOJ]9251. LCS

문제:

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

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

입력:

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

출력:

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

풀이방법:

LCS(Longest Common Subsequence)는 여러 개의 수열 모두의 부분수열이 되는 수열들 중 가장 긴 것을 찾는 문제다. 만약 이 문제를 가능한 모든 경우를 비교해본다면 엄청 큰 시간복잡도를 가지게 될 것이다. 따라서 이를 DP를 사용해서 시간복잡도를 줄이도록 한다.

문자열 ACAYKP와 CAPCAK를 테이블로 추적하며 LCS 함수의 정의를 알아본다. 

 

1. 우선 부분수열이 비어있는 경우도 존재할 수 있기 때문에 각 문자열에 0번째 인덱스를 추가한다. (0ACAYKP, 0CAPCAK)

그 후 문자열들의 크기(len(string1) x len(string2))만큼의 0행렬을 초기화한다.

	0	A	C	A	Y	K	P
0	0	0	0	0	0	0	0
C	0	0	0	0	0	0	0
A	0	0	0	0	0	0	0
P	0	0	0	0	0	0	0
C	0	0	0	0	0	0	0
A	0	0	0	0	0	0	0
K	0	0	0	0	0	0	0

 

2. 세로축의 문자열이 C라고 고정하고, 가로축의 문자열을 하나씩 증가하면서 부분수열을 찾는다.

(C와 A 중 LCS 값, C와 AC 중 LCS 값, C와 ACA 중 LCS 값, ....)

 

그러면 표는 아래와 같이 값이 구해지게 될 것이다.

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

 

이제 세로축의 문자열을 하나씩 늘리고, LCS 함수의 규칙에 따라 진행을 하면 다음과 같이 표들을 얻을 수 있다.

• LCS(CA,ACAYKP)

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

• LCS(CAP,ACAYKP)

	0	A	C	A	Y	K	P
0	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

위 표들은 다음 2가지 케이스에 대해서 업데이트 되는 것을 알 수 있다.

1. 두 부분 수열들이 같은 원소로 끝나는 경우
   1. LCS(CAP,ACAYKP)중 CAP과 ACAYKP를 비교할 때가 이 경우의 예시다. 이 때 맨 마지막 P가 일치한다. 이러한 경우에는 두 부분수열에서 P를 제거한다. 그러면 연산해야 하는 LCS는 다음 두 부분수열이다. (CA, ACAYK)
   2. 이 부분수열의 LCS는 CA임을 이전 행들에서 알 수 있다.
   3. 삭제했던 부분수열 P를 다시 붙이면 CAP이 되고, 이것이 CAP과 ACAYKP의 LCS다.
   4. 이를 LCS의 길이를 구하는 표에서 보면 왼쪽 위 값에 1을 더한것과 같다.
      1. if str1[i]==str2[j], then LCS[i][j]=LCS[i][j]+1와 같다.
2. 두 부분 수열들이 같은 원소로 끝나지 않는 경우
   1. LCS(CAP,ACAYKP)중 CAP과 ACA를 비교하는 경우다. 이 때는 각 부분수열들의 맨 끝 문자를 제거한 뒤에 둘 중 큰 LCS를 택하면 된다.
   2. 즉, max(LCS(CA,ACA), LCS(CAP,AC))와 같다.
      1. 따라서 LCS(CA,ACA)는 CA이므로 LCS(CAP,ACA)는 CA가 된다.

 

따라서 이 규칙들에 따라서 끝까지 진행하면 다음과 같다.

	0	A	C	A	Y	K	P
0	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

 

따라서 LCS의 길이만 구하고 싶다면 4가 답이 된다.

만약 subsequence 문자열을 알고 싶다면 각 행을 역추적하면서 가장 큰 숫자가 시작 된 곳을 체크한다.(값이 일치하면서 +1 된 곳이기 때문이다.)

 

	0	A	C	A	Y	K	P
0	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

 

따라서 ACAK가 LCS임을 알 수 있다.

A='0'+input().rstrip()
B='0'+input().rstrip()
 
if len(A) < len(B):
    A,B = B,A
 
LCS=[[0 for i in range(len(A))]for j in range(len(B))]
 
for i in range(1,len(B)):
    for j in range(1,len(A)):
        if A[j]==B[i]:
            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(B)-1][len(A)-1])

문제링크:

www.acmicpc.net/problem/9251

9251번: LCS