[백준] (9252) LCS 2 [Python]

문제 링크

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

문제

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

• 입력
  • 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.
• 출력
  • 첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.
  • LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

예제 입력	예제 출력
ACAYKP CAPCAK	4 ACAK

---

LCS 문자열 복원 원리

(9251) LCS 문제에서 이어진다. 우리는 이미 dp[i][j] 테이블을 가지고 있다. 이제 거꾸로 dp[n][m]부터 시작해서, 어떤 문자가 LCS에 포함되었는지를 찾아서 모으면 된다.

 

복원 알고리즘 (역방향)

1. i = len(A), j = len(B)부터 시작
2. 문자가 같으면 → LCS에 포함시키고 i -= 1, j -= 1
3. 문자가 다르면:
   • dp[i-1][j] > dp[i][j-1]이면 i -= 1
   • 아니면 j -= 1
4. i나 j가 0이 되면 종료
5. 추적한 문자열을 역순으로 뒤집기

주어진 예제에 대해서, 다음과 같은 dp 테이블이 생성되었다.

	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

먼저 dp의 마지막부터 탐색을 수행하고, 해당 자리에 있는 인덱스 문자열 값을 비교해 값이 같으면 최장 증가 수열에 해당하는 문자로 기록하고, 왼쪽 대각선으로 이동한다. 비교한 값이 다르면 테이블의 왼쪽과 위쪽 값 중 큰 값으로 이동한다.

---

코드

A = input()
B = input()
a, b = len(A), len(B)

dp = [[0] * (b+1) for _  in range(a+1)]
for i in range(1, a+1):
    for j in range(1, b+1):
        if A[i-1] == B[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])

def LCS(i, j):
    if i == 0 or j == 0:
        return
    if A[i-1] == B[j-1]:
        answer.append(A[i-1])
        LCS(i-1, j-1)
    else:
        if dp[i-1][j] > dp[i][j-1]:
            LCS(i-1, j)
        else:
            LCS(i, j-1)

answer = list()
LCS(a, b)
answer.reverse()
print(''.join(answer))