LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
입력
첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.
출력
첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다. LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.
풀이 과정
해당 문제는 LCS 알고리즘을 사용한 문제로, 다음과 같은 방식으로 문제를 풀 수 있었다. 2차원 배열을 사용하여 코드를 작성하였는데, 각 문자의 길이만큼 배열을 만들어주고, 규칙성을 찾아내어 정보를 담아준다. i for문과 j for문을 사용해 두 문자열을 비교해주고, 이때 일치하면 dp [i][j] = dp [i - 1][j - 1] + 문자 저장해준다. 일치하지 않으면 d[i-1][j] 와 dp [i][j-1]에서 길이가 긴 것을 dp [i][j]에 넣어준다.
이 문제에 사용된 핵심 알고리즘인 LCS에 대해 살펴보자.
LCS 알고리즘 LCS는 주로 최장 공통 부분수열(Longest Common Subsequence)을 말합니다만, 최장 공통 문자열(Longest Common Substring)을 말하기도 한다.
문자열 ABCDEF와 GBCDFE를 이용하여 차이점을 예시로 들어보면 해당 예시에서 최장 공통 부분수열(Longest Common Subsequence)은 BCDF, BCDE가 될 수 있다. 부분수열이기 때문에 문자 사이를 건너뛰어 공통되면서 가장 긴 부분 문자열을 찾으면 된다. 최장 공통 문자열(Longest Common Substring)은 BCD이다. 부분문자열이 아니기 때문에 한번에 이어져있는 문자열만 가능하다.
코드를 작성하고 실행시키는 과정에서 생각보다 시간초과 오류가 많이 발생하여 여러번의 수정 끝에 문제를 해결할 수 있었다.
import sys
input = sys.stdin.readline
# 두 개의 입력 문자열 A와 B를 준비하고 각 문자열의 시작에 빈 문자열을 추가
A = [""] + list(input().rstrip())
B = [""] + list(input().rstrip())
# A와 B의 길이에 따라 빈 문자열로 초기화된 2차원 배열 LCS를 생성
LCS = [[""] * len(B) for _ in range(len(A))]
# 동적 프로그래밍을 사용하여 LCS 배열을 채움
for i in range(1, len(A)):
for j in range(1, len(B)):
# 현재 A[i]와 B[j]가 같으면 대각선 이전 셀 값에 현재 문자를 추가하여 업데이트
if A[i] == B[j]:
LCS[i][j] = LCS[i-1][j-1] + A[i]
else:
# 다르면 이전 행 또는 열에서의 최대 길이의 LCS를 선택하여 현재 셀을 업데이트
if len(LCS[i-1][j]) >= len(LCS[i][j-1]):
LCS[i][j] = LCS[i-1][j]
else:
LCS[i][j] = LCS[i][j-1]
# 최종 LCS의 결과를 변수에 저장하고 출력
result = LCS[-1][-1]
print(len(result), result, sep="\n")
