문제 링크: https://www.acmicpc.net/problem/9251

Thumbnail: Photo by Sven Brandsma (Unsplash)

LCS(Longest Common Subsequence) 를 구하는 문제입니다.

풀이

문제 이름 그대로 LCS (Longest Common Subsequence)를 구하는 문제입니다.

LCS 알아보기

LCS는 크게 2가지 존재합니다.

• Longest Common String, 최장 공통 문자열
  • 부분 수열이 아니므로, 하나로 이어져 있는 문자열만 가능합니다.
• Longest Common Subsequence, 최장 공통 부분 수열
  • 부분 수열이므로, 문자 사이를 건너뛰며 공통 부분 수열을 찾을 수 있습니다.

자료 출처: emplam27.log
[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

이 문제에서는 Longest Common Subsequence을 다루지만, 풀이가 더 간단한 Longest Common String에 대해 먼저 알아봅시다.

Longest Common String, 최장 공통 문자열

LCS 알고리즘은 2차원 배열을 사용해 결과를 계산합니다. 두 문자열 \(A\)와 \(B\)의 길이를 열과 행의 길이로 가지는 2차원 배열 LCS를 정의합니다. (행과 열의 순서가 바뀌어도 상관없습니다.)

input = open(0).readline
A = input().strip()
B = input().strip()
a_length = len(A)
b_length = len(B)

LCS = [[0 for _ in range(a_length + 1)] for _ in range(b_length + 1)]

이때, 배열의 0번 행과 열은 계산의 편의를 위해 마진으로 0을 채워넣습니다.

이제 점화식을 사용해 LCS배열을 채워야 합니다. (맞습니다. DP입니다!)

for b_idx in range(1, b_length + 1):
    for a_idx in range(1, a_length + 1):
        if A[a_idx - 1] == B[b_idx - 1]: # 현재 비교하는 두 글자가 같다면
            LCS[b_idx][a_idx] = LCS[b_idx - 1][a_idx - 1] + 1 # LCS 값 갱신
        else:
            LCS[b_idx][a_idx] = 0

배열을 채우는 과정을 그림으로 보며 알아봅시다.

1. 먼저, LCS 배열을 초기화합니다.
   0번 행과 열은 마진 값으로 사용되므로 0으로 채웁니다.

2. 이제 A, B 두 문자열의 각 문자를 서로 비교하며, 점화식에 따라 칸을 채웁니다.

여기서, LCS[2][2]는 \(A_i = B_i\)이므로, 점화식에 따라 LCS[2][2] = LCS[2-1][2-1] + 1로 채워집니다.

LCS[3][3]도 \(A_i = B_i\)이므로, 점화식에 따라 LCS[3][3] = LCS[3-1][3-1] + 1로 채워집니다.

나머지도 동일한 규칙에 따라 계속 채워나가면 됩니다.

이후, 찾은 최장 공통 문자열의 길이는 LCS 배열 내 최댓값과 같습니다.

Longest Common Subsequence, 최장 공통 부분 수열

앞선 Longest Common Substring을 구하던 과정과 유사하게, LCS배열을 점화식을 사용해 채워 나갑니다. 다만, 부분 수열이라는 특징 상, 단어가 연속되지 않을 수 있기에 점화식이 조금 다릅니다.

for b_idx in range(1, b_length + 1):
    for a_idx in range(1, a_length + 1):
        if A[a_idx - 1] == B[b_idx - 1]: # 현재 비교하는 두 글자가 같다면
            LCS[b_idx][a_idx] = LCS[b_idx - 1][a_idx - 1] + 1 # LCS 값 갱신
        else:
            LCS[b_idx][a_idx] = max(LCS[b_idx - 1][a_idx], LCS[b_idx][a_idx - 1])

마찬가지로, LCS 배열이 채워지는 과정을 그림으로 보면서 이해해봅시다.

1. 먼저, 최장 공통 문자열과 동일하게 0번 행과 열은 마진 값인 0으로 채웁니다.

2. 이제 A, B 두 문자열의 각 문자를 서로 비교하며, 점화식에 따라 칸을 채웁니다.

최장 공통 부분 수열의 점화식이 최장 공통 부분 문자열을 구하는 과정과 다른 이유는, 부분 수열의 특징 상 원소가 연속되지 않아도 되기 때문입니다.
따라서, 점화식에서 현재 비교하는 두 문자가 같지 않은 경우 이전 경우의 최대 길이를 그대로 LCS 배열의 값으로 저장하고 있습니다.
아래 그림의 경우, 노란색 칸은 문자가 일치해 길이가 증가한 칸이고, 초록색 칸은 이전 경우의 최대 길이를 그대로 참고하는 경우입니다.

이후 완성된 최장 공통 부분 수열의 길이는 배열의 우측 하단 (LCS[B의 길이][A의 길이])에서 찾을 수 있습니다.

전체 코드

input = open(0).readline
A = input().strip()
B = input().strip()
a_length = len(A)
b_length = len(B)

LCS = [[0 for _ in range(a_length + 1)] for _ in range(b_length + 1)]

for b_idx in range(1, b_length + 1):
    for a_idx in range(1, a_length + 1):
        if A[a_idx - 1] == B[b_idx - 1]:
            LCS[b_idx][a_idx] = LCS[b_idx - 1][a_idx - 1] + 1
        else:
            LCS[b_idx][a_idx] = max(LCS[b_idx - 1][a_idx], LCS[b_idx][a_idx - 1])

print(LCS[b_length][a_length])

번외) LCS 출력하기

LCS(최장 공통 부분 수열)의 길이는 찾았지만, 이 LCS가 어떤 원소로 구성되었는지는 아직 모릅니다. 이를 계산해내는 방법에 대해 알아봅시다.

기본적인 방법은 다음과 같습니다:

1. LCS[b_length][a_length]에서 탐색을 시작합니다.
2. 이제, 점화식에서 이전 행/이전 열의 최댓값을 사용했던 것에서 착안해
   이전 행 또는 이전 열에 현재 칸과 같은 값이 저장되어 있는지 확인합니다.
   1. 만약 같은 값이 저장되어 있다면, 계속해서 이 과정을 반복합니다.
   2. 이전 행과 이전 열 모두 다른 값이 저장되어 있다면, 점화식에서 최댓값을 갱신하던 부분에서 착안해
      대각선으로 1칸 이전의 칸 \((r-1, c-1)\)로 이동하고, 해당 칸의 문자를 LCS 결과 배열에 저장합니다.
3. 위 과정을 LCS 결과 배열을 모두 채울 때 까지 반복합니다.

# 문제 답이랑 상관 없는, LCS의 가능한 값 찾기
lcs_length = LCS[b_length][a_length]
result = ["" for _ in range(lcs_length)]
cur_r = b_length
cur_c = a_length
for i in range(lcs_length):
    while True:
        if LCS[cur_r - 1][cur_c] == LCS[cur_r][cur_c]:
            cur_r -= 1
        elif LCS[cur_r][cur_c - 1] == LCS[cur_r][cur_c]:
            cur_c -= 1
        else:
            cur_r -= 1
            cur_c -= 1
            break
    result[i] = B[cur_r]
print(result[::-1])