[스터디] 9252번 LCS 2

🗃️문제 설명

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

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

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

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

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

🖥️코드

import sys
input = sys.stdin.readline

string1 = list(input().strip())
string2 = list(input().strip())

dp = [[""] * (len(string2) + 1) for _ in range(len(string1) + 1)]

for i in range(1, len(string1) + 1):
    for j in range(1, len(string2) + 1):
        if string1[i-1] == string2[j-1]:
            dp[i][j] = dp[i-1][j-1] + string1[i-1]
        else:
            if len(dp[i-1][j]) >= len(dp[i][j-1]):
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = dp[i][j-1]

if len(dp[-1][-1]) == 0:
    print(0)
else:
    print(len(dp[-1][-1]))
    print(dp[-1][-1])

🧠아이디어

알고리즘 : LCS(Longest Common Subsequence)

• LCS는 최장 공통 부분수열이라고 한다.
• 최장 공통 부분수열에 대한 베이스 지식이 약해서 찾아보던 도중에 아주 자세하게 설명이 되어 있는 글이 있어 해당 내용을 참고했다.

• 핵심 점화식을 이해

for i in range(1, len(string1) + 1):
    for j in range(1, len(string2) + 1):
        if string1[i-1] == string2[j-1]:
            dp[i][j] = dp[i-1][j-1] + string1[i-1]
        else:
            if len(dp[i-1][j]) >= len(dp[i][j-1]):
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = dp[i][j-1]

• 문자열A와 문자열B 한 글자씩을 비교한다.
• 두 문자가 같다면 좌상향 위의 값을 찾아 +1 한다.
• 두 문자가 다르다면 왼쪽 값과 위쪽 값 중 큰 값을 찾아 +1 한다.
  • 왜 이렇게 과정을 달리 해야하는지?
    • 연속성을 보장하지 않는다. → 현재의 문자를 기준으로 비교하는 과정 이전의 최대 공통 부분수열은 유지가 된다.

[참고 링크] : 최장 공통 부분수열 설명(LCS, Longest Common Subsequence)