[🥇5 / 백준 9252 / 파이썬] LCS 2

 

9252번: LCS 2

 

문제

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

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

입력

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

출력

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

LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

 

예제 입력  ACAYKP CAPCAK

예제 출력  4 ACAK

 

풀이

 

LCS의 기본적인 풀이법은 아래 포스팅에 기재돼 있다.

 

[🥇5 / 백준 9251 / 파이썬] LCS

 

대략 요약하자면 일단 불필요한 연산을 줄이기 위해 문자열 앞에 아무거나 하나 붙인 뒤 입력받는다. (이렇게 안해도 크게 상관은 없다.)

그리고 두 문자열의 길이와 일치하는 2차원 dp 배열을 선언한다.

문자열을 각각 가로, 세로로 생각하고 비교하여 최장 길이를 갱신해준다.

 

이제 문자열 각각을 비교할 때의 최장 길이가 dp 배열에 저장되어 있다.

예제로 예시를 들자면 dp 배열은 아래와 같다.

 

 

이제 dp 배열을 거슬러 올라가며 문자열을 추적한다.

맨 오른쪽 아래에서부터 시작하여 자신과 일치하는 숫자 방향으로 인덱스를 이동시킨다.

주위에 같은 숫자가 없다면 해당 인덱스에 맞는 문자를 담은 뒤, 대각선 왼쪽 위 방향으로 이동한다.

 

 

import sys
input = sys.stdin.readline

A,B = "-"+input().rstrip(),"-"+input().rstrip()
dp = [[0]*(len(A)) for _ in range(len(B))]

for i in range(1,len(B)):
    for j in range(1,len(A)):
        if A[j] == B[i]:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = max(dp[i][j-1],dp[i-1][j])
print(dp[-1][-1])

i,j = len(B)-1,len(A)-1
ans = ""
while i>0 and j>0:
    if dp[i][j] == dp[i][j-1]:
        j-=1
    elif dp[i][j] == dp[i-1][j]:
        i-=1
    else:
        ans = A[j] + ans
        i-=1; j-=1
if ans:
    print(ans)

 

문제를 해결한 이후에 좀 더 찾아보니 최단거리 역추적이 필요한 LCS 문제에서는 복잡한 역추적 연산을 피하기 위해 숫자로 이루어진 2차원 dp 배열 대신, LCS 자체를 dp에 갱신해나가는 방식을 사용하는 것 같았다. 위 방법도 무리없이 AC를 받긴 하지만, 조금 더 효율적인 코드를 작성하기 위해선 후자인 방법을 고려해보는 것도 좋겠다.