[동적계획법/DP] 백준 9251 LCS - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

9251번: LCS

 

 

 

2. 문제 풀이

ACAYKP
CAPCAK

 두 문자열의 LCS(Longest Common Subsequence, 최장 공통 부분 수열)을 구하는 문제입니다. 단순히 부분 문자열을 구하는 게 아니라, 떨어져 있어도 순서만 맞으면 공통 부분 수열이 될 수 있습니다.

 

 

2022.02.12 - [Algorithm] - [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

[Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

 DP를 이용해서, 한 문자열을 기준으로 같은 철자가 몇 개나 있는지 계산합니다.

 

 

 1차원 배열로, 누적해서 '공통 부분 수열'을 구합니다. 철자 하나씩 같은지 비교하며, 같은 철자를 찾으면 이전까지 같았던 철자 수 + 1로 갱신합니다. 

 

 

 

3. 코드

import sys
input = sys.stdin.readline

# 입력
a = input().rstrip()
b = input().rstrip()

# DP
len_a, len_b = len(a), len(b)
cache = [0] * len_b
for i in range(len_a):
    cnt = 0
    for j in range(len_b):
        # 최대 누적값 유지
        if cnt < cache[j]:
            cnt = cache[j]
        # 철자가 같으면 cnt + 1
        elif a[i] == b[j]:
            cache[j] = cnt + 1
print(max(cache))