백준 9251번 LCS

정보

문제 바로가기 [클릭]

난이도: Gold5

관련 개념: #다이나믹 프로그래밍

---

조건

시간 제한	메모리 제한
1 초	256 MB

---

문제

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

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

---

입력

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

---

출력

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

---

예제 입출력 1

입력

ACAYKP
CAPCAK

출력

4

---

코드(파이썬)

import sys


line1 = sys.stdin.readline().rstrip()
line2 = sys.stdin.readline().rstrip()

if len(line1) > len(line2):
    line1, line2 = line2, line1

dp = [0 for _ in range(len(line2)+1)]

for ch1 in line1:
    tmp = dp.copy()
    
    for j, ch2 in enumerate(line2, 1):
        if ch1 == ch2:
            tmp[j] = dp[j-1] + 1
        else:
            tmp[j] = max(dp[j], tmp[j-1])
    dp = tmp

print(dp[-1])

---

특이사항

• DP로 해결할 수 있는 문제 중 하나
• 두 문자열이 같을 떄 값을 갱신하는 방식에서 헤매어 다음 참고문헌을 통해 학습

---

참고문헌

• emplam27, “[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence”, emplam27.log, https://velog.io/@emplam27/알고리즘-그림으로-알아보는-LCS-알고리즘-Longest-Common-Substring와-Longest-Common-Subsequence