BaekJoon 9252번 : LCS 2 (python)

BaekJoon 9252번 : LCS 2 (G4 37.888%)

LCS 2 문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
이전의 LCS 1에서는 LCS의 길이만 찾으면 됬었지만 이번엔 역추적을 통한 LCS를 구성하는 알파벳을 찾아야 한다.

• 기본적인 LCS길이를 구하는 알고리즘은 DP를 이용하여 구하는데 sequence1,2를 순회하며 sequence1,2가 같아지는 부분을 발견했을 때 현재의 index dp[i][j] = dp[i-1][j-1] +1 해주게 된다. 만약 현재 i-1,j-1이 같지 않다면 현재 LCS 길이를 유지해야하기 때문에 왼쪽과 위쪽에서의 최댓값을 받아와 LCS길이를 유지해준다.
  • 여기서 대각선의 dp값에서 1을 더해주는 이유는 sequence1[i-1]과 sequence2[j-1]두 위치에서 공통되어 부분수열의 길이가 1증가되기 때문에 두 위치에서의 dp값에서 1을 더하여 길이를 늘려주는 방식이다.
• dp를 통한 역추적은 위에서 값을 구해왔던 방식과 동일하게 진행할 수 있다. i와 j를 sequence1,2의 길이로 부터 시작해서 역추적을 진행한다. 만약 sequence1[i-1] == sequence2[j-1]의 조건을 충족하면 answer값에 원소를 추가해주고 i와 j는 이전에 대각선으로 증가했던 것 처럼 대각선으로 감소하게 된다.
• 만약 sequence1[i-1] != sequence2[j-1] 이라면 dp[i-1][j]와 dp[i][j-1]중 더 큰 값의 index를 1줄여주게 된다.
  • 이러한 알고리즘은 해당 sequence1[i-1]이나 sequence2[j-1]을 포함하지 않아도 LCS 길이가 유지된다는 것을 의미한다.

import sys
input = sys.stdin.readline

sequence1 = input().rstrip()
sequence2 = input().rstrip()

dp = [[0]*(len(sequence2)+1) for _ in range(len(sequence1) + 1)]
for i in range(1, len(sequence1)+1) :
    for j in range(1, len(sequence2)+1) :
        if sequence1[i-1] == sequence2[j-1] :
            dp[i][j] = dp[i-1][j-1] + 1
        else :
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

answer = ''
while i != 0 and j != 0 :
    if sequence1[i-1] == sequence2[j-1] :
        answer += sequence1[i-1]
        i, j = i-1, j-1
    else :
        if dp[i-1][j] >= dp[i][j-1] :
            i -= 1
        else :
            j -= 1
print(dp[-1][-1])
print(answer[::-1])