1 분 소요

[Gold V] LCS - 9251

문제 링크

성능 요약

메모리: 55708 KB, 시간: 568 ms

분류

다이나믹 프로그래밍, 문자열

제출 일자

2024년 3월 31일 10:43:20

문제 설명

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

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

입력

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

출력

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

풀이

LCS는 Longest Common Subsequence의 약자로 최장 공통 부분 수열이라고도 한다. 두 수열을 비교해서 공통으로 존재하는 부분 수열 중 가장 긴 것을 찾는 문제이다. ACAYKP와 CAPCAK를 비교하면 LCS는 ACAK가 되고 길이는 4가 된다. LCS를 구하기 위한 점화식은 다음과 같다.

 # 문자가 존재하지 않는 부분 0으로 저장
 if i==0 or j==0:
    LCS[i][j] = 0

 # 문자가 같은 경우, LCS[i-1][j-1]의 값에 + 1
 elif A[i] == B[j]:
    LCS[i][j] = LCS[i-1][j-1] + 1

 # 문자가 다른 경우, 현 위치에서 직전 길이의 최대값 저장
 else:
    LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1])

아래는 그림으로 표현한 LCS 길이값을 구하는 과정이다.

빨간색으로 되어있는 위치는 이전값에 +1이 된 경우이다. 즉, 공통된 수열을 찾은 경우를 나타낸다. 탐색을 마친 후에는 가장 끝 인덱스인 초록색으로 된 값이 이 문제의 출력이 된다.

전체 코드

 import sys
input = sys.stdin.readline
 
A = input().rstrip()
B = input().rstrip()
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]: # A와 B는 0부터 시작이므로 인덱스에 -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[-1][-1])

댓글남기기

참고