백준 9252번: LCS 2
Dynamic Programming

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

 

9252번: LCS 2

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

www.acmicpc.net

1. 문제 설명

이 문제는 LCS를 구하는 과정이 백준 9521번과 완전히 동일하다. (Input, Output 형식도 같다!)

따라서, LCS를 구하는 방법에 대해서는 이전 글을 참고하면 된다.

https://lucple.tistory.com/31

 

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

X = <A, C, A, Y, K, P>
Y = <C, A, P, C, A, K>

위의 예제에서 생성될 수 있는 LCS는 <A, C, A, K>이고, 길이는 4이다.

따라서 첫째 줄에 LCS의 길이인 4, 둘째 줄에 LCS인 ACAK를 출력하면 된다.

 

2. 문제 접근

이 글에서는 LCS를 구하는 과정에 대해서만 설명할 것이다.

LCS의 길이는 Dynamic Programming으로 2차원 배열을 잘 채우면..

 

물론 LCS를 구하기 위해서 Dynamic Programming를 한 번 더 사용할 것이다.

이전과 다른 것은 시작점의 위치이다.

LCS의 길이를 구하는 과정에서 X0과 Y0부터 비교하여 차례대로 nested loop를 돌았으나,

이번에는 Xn과 Ym에서 시작하여 두 문자열중 하나의 길이가 0일때까지 거꾸로 올라갈 것이다.

 

LCS의 길이를 채운 테이블을 dp[i][j]이라 하자. (문자열 X의 길이는 i, 문자열 Y의 길이는 j이다.)  

case 1) dp[i][j] == dp[i-1][j]인 경우 : Xi-1와 Yj을 비교한 값이 Xi와 Yj을 비교한 값과 같음을 의미하므로

Xi와 Yj가 같지 않은 경우이다. 따라서 i를 하나 감소시킨다.

 

case 2) dp[i][j] == dp[i][j-1]인 경우 : Xi와 Yj-1을 비교한 값이 Xi와 Yj을 비교한 값과 같음을 의미하므로

Xi와 Yj가 같지 않은 경우이다. 따라서 j를 하나 감소시킨다.

 

case 3) 위의 두 케이스에 해당하지 않는다면 Xi와 Yj가 같은 경우에 해당한다.

Xi와 Yj가 같으면 당연히 dp[i-1][j]와 dp[i][j-1]보다 클 것이기 때문이다. (2차원 배열을 그러한 규칙으로 채웠으니까!)

따라서 Xi (=Yj)를 출력하고, i와 j를 모두 하나씩 감소시킨다.

 

위의 case를 이용하여 dp[i][j] == 0일때까지 반복하면 된다.

따라서 시간복잡도는 O(n+m)이 될 것이다. (두 문자열의 길이의 합만큼 2차원 배열을 탐색하면 끝!)

 

3. 구현 코드

from sys import stdin, setrecursionlimit
setrecursionlimit(10**6)

def back_print(i, j):
    if dp[i][j] == 0:
        return

    if dp[i][j] == dp[i - 1][j]:
        back_print(i - 1, j)
    elif dp[i][j] == dp[i][j - 1]:
        back_print(i, j - 1)
    else:
        back_print(i - 1, j - 1)
        print(X[i - 1], end='')  # Y[j - 1]을 출력해도 같은 결과!


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
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
            
print(dp[-1][-1])

back_print(len1 - 1, len2 - 1)

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

ACAYKP
CAPCAK

이때 빨간색은 LCS(출력해야 하는 값)을 나타내고, 파란색은 백트래킹 과정에서 이동하는 경로를 나타낸다.

    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

 

 

 

티스토리툴바