[백준] 9251번: LCS (파이썬)

✅문제: 9251번

📌개념정리

(1) 최장 공통 부분 수열(LCS, Longest Common Subsequence)

• 정의: 최장 공통 부분 수열(LCS)은 두 시퀀스에서 모두 나타나는 연속되지 않은 서브시퀀스 중 가장 긴 것

📌문제풀이

a = input()
b = input()

LCS = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]

for i in range(1, len(a) + 1):
    for j in range(1, len(b) + 1):
        if a[i-1] == b[j-1]:
            LCS[i][j] = LCS[i - 1][j - 1] + 1
        else:
            LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1])

print(LCS[len(a)][len(b)])

두 문자열의 입력을 받고, 각 문자열의 길이를 기반으로 2차원 리스트 LCS를 초기화함. 이때, a[i-1]와 b[j-1]를 비교할 때 i와 j는 각각 1부터 시작해야 하므로 LCS의 크기는 1씩 더함.

 

 

이 문제를 응용해서 풀어보자면, LCS의 길이 대신 문자열을 출력하기 위해서 아래 코드와 같이 각 문자가 일치할 때 해당 문자를 추가하여 LCS 문자열을 구성하게 함.

a = input()
b = input()

n, m = len(a), len(b)
    
LCS = [[''] * (m + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    for j in range(1, m + 1):
        if a[i - 1] == b[j - 1]:
            LCS[i][j] = LCS[i - 1][j - 1] + a[i - 1]
        else:
            LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1], key=len)
            
print(LCS[n][m])

📌후기

• '17218번: 비밀번호 만들기'와 같은 비슷한 문제를 푼 경험이 있어 이해하기 쉬웠음. 

📌참고자료

1) emplam27, "[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence", 2021.01.02, https://velog.io/@emplam27/알고리즘-그림으로-알아보는-LCS-알고리즘-Longest-Common-Substring와-Longest-Common-Subsequence#최장-공통-문자열longest-common-substring