LCS·부분 수열·표와 복원

두 기록에서 순서를 유지하며 공통으로 나타나는 가장 긴 부분은 무엇일까요? 목표는 부분 문자열과 부분 수열의 차이를 이해하고 두 입력 길이의 DP를 설계하는 것입니다. 문자열 인덱스와 DP 점화식을 복습하세요.

개념과 약속

부분 문자열은 연속된 구간입니다. 부분 수열은 중간 항목을 건너뛸 수 있지만 원래 순서를 바꾸지 않습니다. 미리 정렬한다는 뜻이 아닙니다. ABC에서 AC는 부분 수열이지만 연속 부분 문자열은 아닙니다. LCS는 두 문자열의 최장 공통 부분 수열입니다.

table[i][j]는 첫 문자열 앞 i글자와 둘째 문자열 앞 j글자의 LCS 길이입니다. 비어 있는 접두 구간은 0입니다. 마지막 글자가 같으면 대각선 앞부분의 길이에 1을 더하고, 다르면 첫 번째 문자열 또는 두 번째 문자열의 마지막 글자를 빼 본 위·왼쪽 값 중 큰 쪽을 택합니다. 아래 구현은 길이 표를 채운 뒤 큰 값을 따라 거슬러 올라가 한 LCS를 만듭니다. 길이가 같은 선택이 여러 개면 위쪽을 택합니다.

손으로 상태 추적하기

첫 문자열 ABC, 둘째 AC의 길이 표입니다.

마지막 C를 고르고 대각선으로 간 뒤 B를 건너뛰고 A를 고릅니다. 거꾸로 모은 C,A를 뒤집으면 AC가 됩니다.

직접 실행하기

아래 코드는 이 본문만으로 실행할 수 있습니다. lesson.py로 저장하고 첫 장에서 확인한 Python 명령으로 실행하세요.

def lcs(first, second):
    rows, columns = len(first), len(second)
    table = [[0] * (columns + 1) for _ in range(rows + 1)]
    for i in range(1, rows + 1):
        for j in range(1, columns + 1):
            if first[i - 1] == second[j - 1]:
                table[i][j] = table[i - 1][j - 1] + 1
            else:
                table[i][j] = max(table[i - 1][j], table[i][j - 1])
    answer, i, j = [], rows, columns
    while i and j:
        if first[i - 1] == second[j - 1]:
            answer.append(first[i - 1])
            i, j = i - 1, j - 1
        elif table[i - 1][j] >= table[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return "".join(reversed(answer)), table


answer, table = lcs("ABC", "AC")
print(answer)
for row in table:
    print(row)
print(lcs("", "ABC")[0] == "")

실행 결과:

AC
[0, 0, 0]
[0, 1, 1]
[0, 1, 1]
[0, 1, 2]
True

왜 맞고 언제 끝나는가

같은 마지막 글자를 끝에 붙일 수 있으면 그 앞의 최적 공통 수열에 하나를 더합니다. 서로 다르면 양쪽의 마지막 글자를 공통 수열의 끝 글자로 동시에 쓸 수 없으므로, 최적 답은 적어도 한쪽의 마지막 글자를 제외한 후보에 포함됩니다. 두 후보를 모두 비교해 최대를 보존합니다. 상태의 앞부분 길이가 줄어들어 계산 순서와 복원 종료가 정당합니다.

비용과 적용 범위

두 길이를 m,n으로 쓰면 시간 O(mn), 전체 표 공간 O(mn), 복원 시간 O(m+n)입니다. 길이만 필요하면 행 저장을 줄일 수 있지만 이 본문은 실제 답 복원을 위해 표를 남깁니다. 문자열 조각을 무작정 모두 생성하는 방법과 비교하면 중복 계산을 줄입니다.

스스로 풀어 보기

1. AB와 BA의 LCS 길이와 가능한 답을 쓰세요.
2. CAB를 정렬해 ABC로 바꾼 뒤 LCS를 구하면 원래 문제의 답을 보존할까요?

힌트

1. A와 B 둘 다 공통이지만 둘을 같은 순서로 쓸 수 없습니다.
2. 부분 수열은 원래 순서를 약속합니다.

해설

1. 길이 1이고 A 또는 B입니다. 서로 다른 최적 문자열이 나와도 길이·공통성·순서를 만족하면 정답입니다.
2. 일반적으로 보존하지 않습니다. 정렬은 위치 순서를 바꾸어 다른 문제로 만듭니다.

흔한 오해

LCS는 두 문자열에서 똑같이 연속되는 가장 긴 구간을 구하는 알고리즘이 아닙니다. 연속성의 제약이 다르면 상태와 점화식도 달라집니다.

복습과 다음 연결

다음 문자열 탐색은 주어진 패턴이 연속 구간으로 나타나는 모든 위치를 찾습니다.