[백준] LCS(9251) - python

문제 링크 : https://www.acmicpc.net/problem/9251

문제 요약

LCS는 두 수열이 주어졌을 때, 두 수열의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제입니다.

 

풀이

LCS(Longest Common Subsequence) 알고리즘은 두 문자열에서 순서대로 존재하는 가장 긴 공통부분 수열을 찾는 알고리즘입니다. 이 알고리즘은 동적 계획법(Dynamic Programming)을 사용하여 두 문자열 간의 부분 수열을 비교해 나가는 방식으로 구현됩니다. 이때, 문자열의 각 문자를 비교하며 공통된 문자가 나오면 그 문자까지의 LCS 길이를 갱신합니다.

 

점화식

각 문자열을 리스트로 만들어주고 문자를 하나씩 늘려가며 비교해주는 방식을 점화식으로 나타내면 다음과 같이 식을 세워볼 수 있습니다.

(여기서 i는 str2의 i번째 까지의 길이를 의미하고 j는 str1의 j번째 문자까지 길이를 의미합니다.)

if str1[j-1] == str2[i-1]:
    lcs[i][j] = lcs[i-1][j-1] + 1
else:
    lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1])

정답 코드

위의 점화식을 이용해서 아래와 같이 코드를 작성해 보았습니다.

import sys
input = sys.stdin.readline

def main():
    str1 = list(input().rstrip())
    str2 = list(input().rstrip())
    str1Len = len(str1)
    str2Len = len(str2)
    lcs = {i:[0]*(str1Len+1) for i in range(str2Len+1)}
    for i in range(1,str2Len+1):
        for j in range(1,str1Len+1):
            if str1[j-1] == str2[i-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[str2Len][str1Len])
    return

if __name__ == "__main__":
    main()