백준 9251번_LCS (Python)

문제

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

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

 

코드

s1 = input()
s2 = input()
l1 = len(s1)
l2 = len(s2)

dp = [[None]*l2 for _ in range(l1)]
if s1[0] == s2[0]:
    dp[0][0] = 1
else:
    dp[0][0] = 0

for i in range(l1):
    for j in range(l2):
        if i==0 and j==0:
            continue
        if s1[i] == s2[j]:
            if i==0 or j==0:
                dp[i][j] = 1
            else:
                dp[i][j] = dp[i-1][j-1]+1
        else:
            if i==0:
                dp[i][j] = dp[i][j-1]
            elif j==0:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i][j-1], dp[i-1][j])
print(dp[l1-1][l2-1])

 

풀이

(편의상 최대 길이 부분 문자열의 길이를 LCS로 부르겠다.)

두 문자열을 S1, S2로 두고 그 길이를 L1, L2로 두고, L1*L2 크기의 배열 D를 만들자.

그리고 D에서 (i, j) 좌표의 칸에는 두 문자열의 첫째 항부터 S1의 i번째 항까지를 모은 부분문자열, S2를 1번째부터 j번째 항까지를 모은 부분문자열의 LCS를 저장해준다.

문제에서 예시로 든 ACAYKP와 CAPCAK를 살펴보자.

 

우선 배열 D의 완성된 모습은 다음과 같다.

S2\S1	A	C	A	Y	K	P
C	0	1	1	1	1	1
A	1	1	2	2	2	2
P	1	1	2	2	2	3
C	1	2	2	2	2	3
A	1	2	3	3	3	3
K	1	2	3	3	4	4

(실제 코딩에서 사용되는 0~n-1의 인덱스 설정 대신 편의상 1~n의 인덱스 설정을 사용하겠다.)

우선 (1,1)을 보면, A와 C는 공통 문자열이 없으므로 0이다. 그뒤 (2,1)을 보면, AC와 C는 공통 문자열 C가 생겨서 LCS가 1이다. 그 뒤로 (3, 1)부터 (6, 1)까지는 전부 AC~~와 C를 비교하게 되므로 LCS가 1이다.

 

그다음 S2에서 CA와 S1의 부분 문자열들을 비교해보자. 지금부터는 비교하는 문자열들의 맨 마지막 문자를 기준으로 비교할 것이다. 그 앞까지의 문자들은 이미 위의 배열에서 검토되었기 때문이다.

(1, 2): CA와 A: A가 겹치니 LCS 1(A)

(2, 2): CA와 AC: A와 C는 다르니 CA와 A의 LCS 또는 C와 AC의 LCS중 최댓값이 (2, 2)의 LCS가 될 것이다. (아래 해설 참고)

(3, 2): CA와 ACA: A가 겹치니 CA에서 A를 뺀 C, ACA에서 A를 뺀 AC의 가장 긴 공통 부분 문자열에다가 A를 더한 것이 CA와 ACA의 가장 긴 공통 부분 문자열이다. (아래 해설 참고)

(4, 2): CA와 ACAY: (2, 2)와 같이 (3, 2)과 (4, 1)의 LCS 중 최댓값인 2

(5, 2)와 (6, 2)도 (4, 2)와 비슷하게 흘러간다.

 

 

그럼 (2, 2)같은 경우, 왜 (i, j)에서 맨 마지막 문자가 다를 경우, (i-1, j)와 (i, j-1)의 LCS의 최댓값이 (i, j)의 LCS의 최댓값이 될까?

 

(i, j)에서 비교하는 두 부분 문자열을 XA, YB로 두자. A, B가 각각 마지막 문자고, X와 Y는 그 앞까지의 문자열이다.

XA와 YB의 마지막 문자는 서로 다르므로 이들 중 하나만을 뺀다면 XA와 Y 혹은 X과 YB가 될것이다. 이 두 경우들만 비교해도 왜 XA와 YB를 비교하는 것과 동일하는건지 지금부터 설명하겠다.

 

(여기서, 아래부터 나올 'A, B로 끝나는 경우'는 각각 XA의 A에 대응되는 A로 끝나는 경우와 YB의 B에 대응되는 B로 끝나는 경우를 뜻한다. X와 Y의 안에만 속해있는데 A 혹은 B와 같은 종류의 문자는 다른 것으로 취급한다.)

우선 XA와 Y를 비교하는 경우, YB에서 B를 빠진다는 것은 YB의 B가 들어가는 공통 부분 문자열을 제외하고 생각하겠다는 것이다. X와 YB를 비교하는 것도 XA의 A가 들어가는 공통 부분 문자열을 제외하고 생각하는 것이다. 이런 생각들은 전체 집합 중 어떤 부분집합을 고려하는 것이니 완전하게 만들려면 그 여집합을 고려해야 한다. 즉, YB의 B가 들어가는 공통 부분 문자열을 고려하는 경우가 전부 X와 YB를 고려하는 경우에 들어가야 하고 XA의 A가 들어가는 공통 부분 문자열을 고려하는 경우가 전부 XA와 Y를 고려하는 경우에 들어가야 한다는 것이다.

YB의 B가 들어가는 부분 문자열은 결국 B로 끝나는 문자열이다. YB의 부분 문자열이 B로 끝나지 않고 다른 문자로 끝난다면, YB에서도 B 뒤에 다른 문자가 있어야 하기 때문에 B가 마지막 문자라는데 모순이기 때문이다. XA의 A가 들어가는 부분 문자열도 마찬가지로 A로 끝나는 문자열이다. 그리고 부분 문자열은 A가 마지막 문자거나, B가 마지막 문자거나, 혹은 제 3의 문자가 마지막 문자가 되는 경우만 존재한다. A, B 둘다 동시에 마지막 문자가 되는 것은 불가능하다.

 

이제 앞에서 말한 XA와 Y를 고려하는 경우, X와 YB를 고려하는 경우의 집합을 벤다이어그램으로 표현해보자.

A로 끝나는 경우, B로 끝나는 경우, A와 B 둘중 어느 하나로도 끝나지 않는 경우를 모두 모으면 전체 집합, 즉 XA와 YB의 부분문자열을 고려하는 것과 동일하다.

그리고 XA와 YB는 (i, j)라고 했으니, XA와 Y/X와 YB를 고려하는 것은 (i-1, j) 또는 (i, j-1) 중 하나다. 이들을 모두 미리 고려하도록 반복문 코드를 작성하면, (i-1, j)와 (i, j-1)의 LCS들을 바탕으로 (i, j)의 LCS을 구할 수 있을 것이다. 그리고 LCS는 결국 '최대'를 생각하는 코드이므로 (i-1, j)와 (i, j-1)의 LCS중 최댓값을 생각하면 된다.

 

 

그리고 (i, j)에서 마지막 문자가 서로 같으면, (i-1, j-1)의 최대 길이 부분 문자열에 이 마지막 문자를 더한 것이 부분 문자열이 되는 것은 당연히 받아들일 수 있을 것이다. 하지만 꼭 이 경우가 최대라는 보장이 있을까? 위의 방식처럼 (i, j-1) 혹은 (i-1, j)의 LCS를 가져오는 게 더 클 수도 있지 않을까?

 

(i, j)에서 XA와 YA를 비교한다고 가정하자. X와 YA를 비교하는 경우를 보자. 최대 길이 부분 문자열이 YA의 A를 사용하지 않는다면 이는 결국 X와 Y를 비교하는 것과 결과가 동일하다. 즉, (i-1, j-1)과 결과가 동일하고, 우리는 그저 X와 Y의 최장 부분 문자열에 A를 더해주면 된다.

 

반면 최대 길이 부분 문자열이 YA의 A를 사용한다면, 그 문자열의 끝은 반드시 A다. 이때, X에 A를 더해주어 XA와 YA를 비교해준다면,

위와 같이 원래는 YA의 A와 X 안의 A 간의 연결(붉은색)을 XA의 추가된 A로 대응으로(푸른색) 바꿔주자. 그러면 남은 건 X와 Y의 비교다. 만약 X와 Y를 비교해서 원래의 붉은색 연결이 있을 때(YA와 X의 비교)보다 파란색 연결로 바꾸었을 때(YA와 XA의 비교) 더 LCS가 길다면? 그러면 애초에 YA와 X를 비교했을 때도 굳이 이 붉은색 연결을 고집하지 않고 더 LCS가 긴 쪽으로 갔을 것이다. 하지만 파란색 연결로 바꾸어도 X와 Y 간에 LCS에 변함이 없다면 그대로 X와 Y를 비교하는 (i-1, j-1)의 LCS를 가지고 와도 될 것이다.

 

즉, 이런 경우들을 고려하여 (i-1, j-1)의 LCS에 1을 더해주기만 해도 (i, j)의 LCS를 구할 수 있음을 알 수 있다.

 

 

이 두 방법을 이용해서 L1*L2의 경우를 모두 탐색하면서 결과적으로는 (L1, L2) 칸의 LCS를 출력하면 정답이 된다.