문제:

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임을 알 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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])
cs

문제링크:

www.acmicpc.net/problem/9251

 

9251번: LCS

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

www.acmicpc.net

 

'Algorithm > Python' 카테고리의 다른 글

[BOJ]2096. 내려가기  (0) 2020.09.15
[BOJ]10972. 다음 순열  (0) 2020.09.10
[BOJ]17298. 오큰수  (0) 2020.09.03
[BOJ]16561. 3의 배수  (0) 2020.09.01
[BOJ]10989. 수 정렬하기3  (0) 2020.08.27

+ Recent posts