알고리즘
[백준] 9251번(LCS) with Python
철갑
2020. 10. 17. 20:50
728x90
문제
9251번: LCS
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
풀이
먼저 LCS(Longest Common Subsequence, 최장 공통 부분 수열)는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 부분을 말한다.
예시로 ACAYKP와 CAPCAK를 이용해 표를 그려보았다.
ACAYKP를 비교 대상으로 잡고 CAPCAK 문자열 하나씩 추가하면서 공통 수열 길이 값을 표시해준다.
위와 같이 반복을 하다보면 규칙을 찾을 수 있다.
행은 이전 행의 값과 같고, 같은 문자가 나오는 경우 이전 값에 +1을 하고 있는 것을 알 수 있다.
최종으로 작성된 표는 이렇게 나오게 된다. 즉, LSC는 4라는 것을 알 수 있다.
답
import sys
A = sys.stdin.readline().strip().upper()
B = sys.stdin.readline().strip().upper()
lcs = [[0] * (len(A)+1) for _ in range(len(B)+1)]
for i in range(1,len(B)+1) :
for j in range(1,len(A)+1) :
if B[i-1] == A[j-1] :
lcs[i][j] = lcs[i-1][j-1] + 1
else :
lcs[i][j] = max(lcs[i][j-1], lcs[i-1][j])
print(lcs[-1][-1])728x90