최장 공통 부분 수열

최장 공통 부분 수열은 두 나열에 똑같이 들어 있는 부분을 가장 길게 찾는 문제입니다. 넣는 것은 글자나 줄을 차례로 늘어놓은 나열 두 개입니다. 답은 양쪽에 같은 순서로 들어 있는 가장 긴 원소들입니다. 두 파일에서 안 바뀐 줄을 찾는 diff 가 이 문제를 풉니다.

상세

최장 공통 부분 수열은 줄여서 LCS(Longest Common Subsequence, 최장 공통 부분 수열)라고 씁니다. 이 이름은 먼저 푸는 문제를 가리킵니다. 그 문제의 답으로 나온 나열도 같은 이름으로 부릅니다. 답을 실제로 찾는 일은 문제를 푸는 풀이가 합니다.

이 편은 가장 흔한 풀이인 동적 계획법 풀이를 따라갑니다. 동적 계획법은 작은 문제의 답을 표에 적어 두는 방법입니다. 큰 문제를 풀 때 그 답을 꺼내 쓰므로 같은 계산을 되풀이하지 않습니다. 예는 ABCBD 와 BDCB 한 쌍으로 끝까지 봅니다.

부분 수열과 부분 문자열

수열은 원소를 순서대로 늘어놓은 것입니다. 글자를 늘어놓은 문자열도, 파일의 줄을 늘어놓은 목록도 수열입니다. 이 편에서는 수열을 「나열」이라고도 부릅니다.

부분 수열은 나열에서 원소 몇 개를 지우고 남은 것입니다. 남은 원소의 순서는 바꾸지 않습니다. ABCBD 에서 B 와 B 를 지우면 ACD 가 남습니다. 그래서 ACD 는 ABCBD 의 부분 수열입니다.

지운 원소 사이가 벌어져도 괜찮다는 점이 핵심입니다. ACD 의 A 와 C 는 원래 나열에서 붙어 있지 않았습니다. 순서를 뒤집은 DCA 는 부분 수열이 아닙니다.

이름이 닮은 부분 문자열은 붙어 있는 구간만 뜻합니다. ABCBD 의 부분 문자열은 BCB 나 CBD 처럼 한 덩어리로 이어진 조각입니다. ACD 는 부분 수열이지만 부분 문자열은 아닙니다.

붙은 구간을 가장 길게 찾는 문제는 최장 공통 부분 문자열이라는 별개의 문제입니다. 풀이 모양이 비슷해서 자주 헷갈립니다.

문제를 세우기

두 나열 양쪽의 부분 수열이 되는 나열을 공통 부분 수열이라고 합니다. ABCBD 와 BDCB 에서 BC 는 양쪽 모두의 부분 수열입니다. 그래서 BC 는 둘의 공통 부분 수열입니다.

최장 공통 부분 수열 문제는 공통 부분 수열 가운데 가장 긴 것을 찾습니다. ABCBD 와 BDCB 에서는 BCB 가 답이고 길이는 3 입니다.

가장 긴 것이 여럿일 수도 있습니다. AB 와 BA 에서는 A 와 B 가 둘 다 길이 1 인 답입니다. 이때 길이는 하나로 정해지지만 나열은 하나로 정해지지 않습니다.

그래서 이 문제는 두 가지를 물을 수 있습니다. 하나는 가장 긴 길이만 묻습니다. 다른 하나는 그 길이를 가진 나열 하나를 묻습니다. 아래 풀이는 길이를 먼저 구하고 나열은 그 뒤에 되짚어 얻습니다.

모두 따져 보면 안 되는 까닭

가장 쉬운 풀이는 한쪽 나열의 부분 수열을 전부 만들어 다른 쪽에 들어 있는지 보는 것입니다. 이 풀이는 맞는 답을 내지만 너무 오래 걸립니다.

원소마다 남기거나 지우거나 두 가지를 고를 수 있습니다. 그래서 길이 n 인 나열의 부분 수열은 2를 n 번 곱한 만큼 있습니다. ABCBD 다섯 글자면 32 개입니다.

길이가 30 이면 10억 개가 넘습니다. 길이가 50 이면 1000조 개가 넘습니다. 원소가 하나 늘 때마다 일이 두 배가 됩니다. 그래서 파일 비교에는 쓸 수 없습니다.

입력이 하나 늘 때마다 일이 몇 배씩 불어나는 이런 늘어남을 지수 시간이라고 합니다.

끝 원소 하나만 보는 식

이 소절은 문제를 한 원소 짧은 문제로 줄이는 식을 세웁니다. 식을 세우려면 「앞부분」이라는 낱말이 먼저 필요합니다.

나열의 앞에서부터 원소 몇 개를 잘라 낸 것을 접두사라고 합니다. ABCBD 의 앞 3 개 접두사는 ABC 입니다. 접두사를 쓰면 긴 나열의 문제를 짧은 나열의 문제로 줄여 말할 수 있습니다.

두 나열을 x, y 라고 합니다. x 의 앞 i 개와 y 의 앞 j 개를 비교한 답의 길이를 L[i][j] 라고 적습니다. 이 값은 x 를 행에, y 를 열에 놓은 표의 i 행 j 열 칸에 들어갑니다.

L[i][j] 는 두 접두사의 끝 원소를 비교해서 구합니다. 끝 원소는 x 의 i 번째 원소와 y 의 j 번째 원소입니다. 두 원소가 같은지 다른지에 따라 식이 둘로 갈립니다.

끝 원소가 같으면 그 원소를 답의 끝에 붙일 수 있습니다. 두 끝 원소를 떼고 남은 앞부분의 답에 하나를 더합니다. 식으로는 L[i][j] = L[i-1][j-1] + 1 입니다.

끝 원소가 다르면 둘 가운데 적어도 하나는 답에 못 들어갑니다. 그래서 x 쪽 끝을 뗀 경우와 y 쪽 끝을 뗀 경우를 둘 다 보고 큰 쪽을 고릅니다. 식으로는 L[i][j] = max(L[i-1][j], L[i][j-1]) 입니다.

어느 한쪽이 비어 있으면 공통 부분 수열도 비어 있습니다. 그래서 L[0][j] 와 L[i][0] 은 모두 0 입니다. 이렇게 긴 접두사의 칸 값을 짧은 접두사의 칸 값으로 적은 식을 점화식이라고 합니다.

두 식이 쓰는 칸은 표에서 이번 칸의 이웃입니다. i 가 하나 작으면 한 행 위 칸이고 j 가 하나 작으면 한 열 왼쪽 칸입니다. 그래서 L[i-1][j-1] 은 왼쪽 위 칸, L[i-1][j] 는 위 칸, L[i][j-1] 은 왼쪽 칸입니다.

flowchart TD
    UL["왼쪽 위 칸 · L[i-1][j-1]"]
    U["위 칸 · L[i-1][j]"]
    LF["왼쪽 칸 · L[i][j-1]"]
    C["이번 칸 · L[i][j]"]
    UL -->|"끝 원소가 같으면 여기에 1 을 더함"| C
    U -->|"끝 원소가 다르면 둘 중 큰 값"| C
    LF -->|"끝 원소가 다르면 둘 중 큰 값"| C

그림처럼 이번 칸 하나는 이웃한 세 칸만 봅니다. 그래서 위에서 아래로, 왼쪽에서 오른쪽으로 채우면 필요한 칸이 늘 먼저 채워져 있습니다.

두 식이 맞는 까닭

두 식이 가장 긴 답을 놓치지 않는다는 것을 두 경우로 나눠 확인합니다.

끝 원소가 같을 때를 먼저 봅니다. 가장 긴 답이 그 끝 원소를 안 쓴다고 해 봅니다. 이때 답의 마지막 원소를 두 끝 원소로 바꿔 봅니다.

답에서 마지막 원소보다 앞선 원소들은 x 와 y 모두에서 두 끝 원소보다 앞에 있습니다. 그래서 바꿔도 순서가 안 깨집니다. 바꾼 나열은 길이가 같은 공통 부분 수열입니다. 따라서 끝 원소를 쓰는 가장 긴 답이 언제나 하나는 있습니다.

끝 원소가 다를 때는 가장 긴 답이 두 끝 원소를 함께 쓸 수 없습니다. 나열의 끝 원소를 쓰면 그 원소는 답의 마지막 원소가 됩니다. 그 나열에는 끝 원소 뒤로 답에 넣을 원소가 남아 있지 않기 때문입니다.

두 끝 원소를 다 쓰면 둘이 함께 답의 마지막 원소 하나로 짝지어져야 합니다. 두 원소는 서로 다르니 그럴 수 없습니다. 그래서 x 의 끝을 떼거나 y 의 끝을 떼어도 답이 안 줄어드는 쪽이 반드시 있습니다.

큰 문제의 답이 작은 문제의 답으로 이루어지는 이 성질을 최적 부분 구조라고 합니다. 두 식은 이 성질에 기댑니다.

같은 작은 문제가 여러 번 나온다는 성질도 있습니다. 식을 재귀로 그대로 옮겨 보면 드러납니다. 재귀는 함수가 자기 자신을 다시 부르는 방식입니다.

L[i][j] 를 구하는 함수는 끝 원소가 다르면 L[i-1][j] 와 L[i][j-1] 을 부릅니다. 이 두 칸도 끝 원소가 다르면 둘 다 L[i-1][j-1] 을 부릅니다. 같은 칸을 두 번 구하는 셈입니다. 이렇게 같은 작은 문제를 겹쳐 부르는 성질을 중복 부분 문제라고 합니다.

flowchart TD
    A["이번 칸 · L[i][j]"]
    B["위 칸 · L[i-1][j]"]
    C["왼쪽 칸 · L[i][j-1]"]
    D["왼쪽 위 칸 · L[i-1][j-1] · 두 번 구함"]
    A --> B
    A --> C
    B --> D
    C --> D

한 층 더 내려가면 겹쳐 부르는 칸이 더 늘어납니다. 동적 계획법은 칸마다 답을 표에 한 번만 적어 둡니다. 다시 필요하면 표에서 꺼내 씁니다.

표를 채우는 과정

ABCBD 를 행에, BDCB 를 열에 놓고 표를 채웁니다. 맨 위 행과 맨 왼쪽 열은 빈 접두사라서 모두 0 입니다.

B 는 행에도 열에도 두 번씩 나옵니다. 위쪽 B 행을 첫 B 행, 아래쪽을 두 번째 B 행이라고 부릅니다. 열도 왼쪽부터 첫 B 열, 두 번째 B 열입니다.

A 행은 전부 0 입니다. BDCB 에 A 가 없어서 같은 원소가 한 번도 안 나옵니다.

C 행 C 열 칸은 2 입니다. 끝 원소가 C 와 C 로 같아서 왼쪽 위 칸의 1 에 하나를 더했습니다. 왼쪽 위 칸의 1 은 AB 와 BD 의 답 B 의 길이입니다.

두 번째 B 행의 마지막 칸은 3 입니다. 끝 원소가 B 와 B 로 같아서 왼쪽 위 칸의 2 에 하나를 더했습니다.

맨 아래 D 행의 마지막 칸도 3 입니다. 끝 원소 D 와 B 가 달라서 위 칸의 3 과 왼쪽 칸의 2 가운데 큰 3 을 가져왔습니다. 이 오른쪽 아래 칸이 두 나열 전체의 답입니다.

표에서 답을 되짚기

표는 길이만 알려 줍니다. 어떤 원소들이 답인지는 오른쪽 아래 칸에서 출발해 거꾸로 따라가며 모읍니다.

한 칸 옮길 때마다 규칙은 둘입니다. 그 칸의 행 원소와 열 원소가 같으면 그 원소를 모은 뒤 왼쪽 위 칸으로 갑니다. 다르면 위 칸과 왼쪽 칸 가운데 값이 큰 쪽으로 갑니다.

아래 그림은 이 예에서 지나는 칸을 차례로 이은 것입니다. 칸마다 행 이름, 열 이름, 값을 적었습니다.

flowchart TD
    S["D 행 · 두 번째 B 열 · 3"]
    B2["두 번째 B 행 · 두 번째 B 열 · 3 · B 모음"]
    C["C 행 · C 열 · 2 · C 모음"]
    B1D["첫 B 행 · D 열 · 1"]
    B1["첫 B 행 · 첫 B 열 · 1 · B 모음"]
    E["A 행 · 빈 열 · 0 · 멈춤"]
    S -->|"D 와 B 가 다름 · 위 칸 3 이 큼 → 위로"| B2
    B2 -->|"같음 → 왼쪽 위로"| C
    C -->|"같음 → 왼쪽 위로"| B1D
    B1D -->|"B 와 D 가 다름 · 왼쪽 1 이 위 0 보다 큼 → 왼쪽으로"| B1
    B1 -->|"같음 → 왼쪽 위로"| E

D 행에서 출발해 위로 한 칸 오르면 B 와 C 를 차례로 모읍니다. 첫 B 행 D 열에서는 원소가 달라 왼쪽으로 한 칸 옮깁니다. 첫 B 열에서 마지막 B 를 모으면 빈 열에 닿아 멈춥니다.

모은 순서는 B, C, B 입니다. 거꾸로 따라가며 모았으니 끝에 순서를 뒤집습니다. 이번 예는 뒤집어도 BCB 입니다.

위 칸과 왼쪽 칸의 값이 같을 때는 어느 쪽으로 가도 됩니다. 고르는 쪽에 따라 길이가 같은 다른 답이 나올 수 있습니다. 「문제를 세우기」에서 본 「답이 여럿일 수 있다」가 이렇게 드러납니다.

파이썬으로 옮긴 코드

표를 채우는 함수와 되짚는 함수 둘로 나눕니다. 먼저 표를 채우는 함수입니다. 표는 2차원 배열로 두고 행과 열을 하나씩 더 잡아 빈 접두사의 행과 열을 만듭니다.

def lcs_table(x, y):
    n, m = len(x), len(y)
    L = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if x[i - 1] == y[j - 1]:
                L[i][j] = L[i - 1][j - 1] + 1
            else:
                L[i][j] = max(L[i - 1][j], L[i][j - 1])
    return L

파이썬 리스트는 0 번부터 셉니다. 그래서 i 번째 원소는 x[i - 1] 로 꺼냅니다. 반복문 두 겹이 위에서 아래로, 왼쪽에서 오른쪽으로 표를 채웁니다.

되짚는 함수는 오른쪽 아래 칸에서 출발해 되짚기의 두 규칙을 되풀이합니다. 위 칸과 왼쪽 칸의 값이 같을 때는 위 칸으로 갑니다.

def lcs_trace(x, y, L):
    i, j = len(x), len(y)
    out = []
    while i > 0 and j > 0:
        if x[i - 1] == y[j - 1]:
            out.append(x[i - 1])
            i, j = i - 1, j - 1
        elif L[i - 1][j] >= L[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return out[::-1]

두 함수를 ABCBD 와 BDCB 에 돌려 봅니다. 표의 값과 되짚은 답이 손으로 채운 것과 같습니다.

x, y = "ABCBD", "BDCB"
L = lcs_table(x, y)
L[5][4]            # 3
L[3][3]            # 2 · ABC 와 BDC
lcs_trace(x, y, L) # ['B', 'C', 'B']

원소를 비교할 때 == 만 쓰므로 글자 대신 줄 목록을 넣어도 그대로 돕니다. diff 가 이 성질을 씁니다.

걸리는 시간과 메모리

두 나열의 길이를 n 과 m 이라고 하면 표는 n+1 행 m+1 열입니다. 칸 하나는 이웃 세 칸만 보고 채우므로 칸마다 드는 일이 일정합니다.

이런 늘어남은 빅오 표기법으로 적습니다. 빅오 표기법은 입력이 커질 때 비용이 어떤 모양으로 따라 커지는지를 적는 약속입니다. 표를 채우는 시간은 O(nm) 이고 표가 차지하는 메모리도 O(nm) 입니다.

되짚기는 한 칸 옮길 때마다 행이나 열이 하나 줄어듭니다. 그래서 많아야 n+m 번 옮기면 끝납니다. 표를 채우는 시간에 견주면 작습니다.

두 파일이 각각 1만 줄이면 칸이 1억 개입니다. 각각 10만 줄이면 100억 개가 됩니다. 이만한 표는 메모리에 올리기 어렵습니다. 시간보다 메모리가 먼저 모자랍니다.

메모리를 줄이는 법

길이만 필요하면 표 전체를 들고 있을 까닭이 없습니다. 한 행을 채울 때 바로 위 행만 보기 때문입니다. 두 행만 번갈아 쓰면 됩니다.

한 행의 칸 수는 열에 놓은 나열의 길이만큼입니다. 그래서 짧은 나열을 열 쪽에 놓으면 메모리가 짧은 쪽 길이만큼으로 줄어듭니다.

답이 되는 나열까지 필요하면 두 행만으로는 모자랍니다. 되짚기에 표 전체가 쓰이기 때문입니다.

이때는 문제를 반으로 나눠 가며 푸는 허슈버그 알고리즘을 씁니다. 시간은 O(nm) 그대로 두고 메모리만 두 나열 길이에 비례하는 만큼으로 줄입니다. 문제를 작게 쪼개 각각 푼 뒤 합치는 이런 방식을 분할 정복이라고 합니다.

diff 에서 쓰이는 모습

diff 는 두 파일에서 무엇이 바뀌었는지 보여 주는 도구입니다. 파일의 줄 하나를 원소 하나로 보고 두 파일의 최장 공통 부분 수열을 구합니다.

답에 든 줄은 양쪽에 같은 순서로 남은 줄이라 안 바뀐 줄로 봅니다. 옛 파일에만 있는 줄은 지운 줄입니다. 새 파일에만 있는 줄은 넣은 줄입니다.

옛 파일이 a, b, c, d 네 줄이고 새 파일이 a, c, d, e 네 줄이라고 해 봅니다. 최장 공통 부분 수열은 a, c, d 세 줄입니다. 남는 b 는 지운 줄, e 는 넣은 줄이 됩니다.

 a
-b
 c
 d
+e

앞의 기호 없는 줄이 안 바뀐 줄, - 가 붙은 줄이 지운 줄, + 가 붙은 줄이 넣은 줄입니다. 이렇게 바뀐 줄이 모인 덩어리를 헝크라고 부릅니다.

안 바뀐 줄을 가장 많이 남기면 지우고 넣는 줄이 가장 적어집니다. 그래서 사람이 읽기에 짧은 차이가 나옵니다. 버전 관리 시스템이 두 판을 비교하거나 세 갈래 병합이 두 쪽의 고친 곳을 찾을 때 이 차이를 씁니다.

diff 도구는 이 표를 그대로 채우지 않는 경우가 많습니다. 두 파일이 거의 같을 때는 바뀐 줄 수에 따라 일이 줄어드는 마이어스 diff 알고리즘 같은 방법이 더 빨리 끝납니다. 그 방법이 구하는 것도 같은 최장 공통 부분 수열입니다.

편집 거리와의 관계

편집 거리는 한 나열을 다른 나열로 바꾸는 데 필요한 가장 적은 편집 횟수입니다. 편집으로 무엇을 허락하느냐에 따라 값이 달라집니다.

원소 넣기와 지우기만 허락하면 편집 거리는 최장 공통 부분 수열 길이로 바로 구해집니다. 두 나열 길이를 더한 값에서 최장 공통 부분 수열 길이의 두 배를 뺍니다. 공통 부분 수열에 안 든 원소는 한쪽에서 지우거나 다른 쪽에 넣어야 하기 때문입니다.

diff 소절의 예에 대 봅니다. 4 더하기 4 에서 3 의 두 배인 6 을 빼면 2 입니다. b 를 지우고 e 를 넣는 두 번의 편집과 맞습니다.

원소를 다른 원소로 바꾸는 편집까지 허락하면 레벤슈타인 거리가 됩니다. 식은 달라지지만 두 접두사로 표를 채우는 뼈대는 같습니다.

쓸 때와 안 쓸 때

두 나열을 비교하는 방법은 여럿입니다. 아래 표를 위에서부터 물어 처음 맞는 줄의 방법을 고릅니다.

맨 위 줄에 해당하는 일은 파일 비교만이 아닙니다. 유전자 염기 서열처럼 긴 글자 나열 둘이 얼마나 닮았는지 볼 때도 같은 문제가 나옵니다. 사이에 끼어든 원소를 건너뛰고 공통된 뼈대를 찾는 일이기 때문입니다.

순서가 뜻을 갖지 않는 데이터에는 맞지 않습니다. 두 사용자의 관심사 목록처럼 순서가 우연인 나열은 교집합으로 충분합니다.

관련 항목

최장 공통 부분 수열이 속하는 상위 분류

알고리즘 · 동적 계획법 · 문자열 알고리즘 · 조합 최적화

최장 공통 부분 수열 문제를 이루는 기본 개념

수열 · 부분 수열 · 문자열 · 접두사 · 점화식

동적 계획법 풀이가 기대는 성질과 기법

최적 부분 구조 · 중복 부분 문제 · 메모이제이션 · 재귀 · 2차원 배열

이름이 닮아 헷갈리는 이웃 문제

최장 공통 부분 문자열 · 부분 문자열 · 최장 증가 부분 수열 · 부분 문자열 매칭 · 최장 공통 접두사

두 나열의 차이를 재는 척도

편집 거리 · 레벤슈타인 거리 · 해밍 거리 · 서열 정렬

최장 공통 부분 수열을 더 빠르거나 가볍게 푸는 알고리즘

허슈버그 알고리즘 · 마이어스 diff 알고리즘 · 헌트-시맨스키 알고리즘 · 분할 정복

최장 공통 부분 수열로 파일 차이를 다루는 도구

diff · diff3 · 패치 · 헝크 · 세 갈래 병합 · 버전 관리 시스템

드는 비용을 적는 표기

빅오 표기법 · 시간 복잡도 · 공간 복잡도 · 지수 시간