최장 공통 부분 수열(LCS)

파일의 두 버전을 비교할 때, 바뀌지 않은 줄들은 두 버전의 공통 부분 수열입니다. 그중 가장 긴 것을 찾으면 무엇이 추가되고 무엇이 삭제되었는지 정확히 알 수 있습니다. 같은 아이디어로 DNA 가닥을 정렬하고 맞춤법 수정을 제안하며, 이 문제는 컴퓨터 과학에서 가장 우아한 표 중 하나로 풀립니다.

위쪽에 한 단어, 왼쪽에 다른 단어가 있고 칸마다 숫자가 적힌 표, 그리고 오른쪽 아래 모서리에서 위로 올라가는 주황색 칸들의 경로
위쪽에 한 단어, 왼쪽에 다른 단어가 있고 칸마다 숫자가 적힌 표, 그리고 오른쪽 아래 모서리에서 위로 올라가는 주황색 칸들의 경로

문제

단어의 부분 수열은 글자 일부를 원래 순서대로 남긴 것입니다. ACE는 ABCDE의 부분 수열이지만 EA는 아닙니다. 두 단어의 공통 부분 수열은 두 단어 모두의 부분 수열이며, 문제는 그중 가장 긴 것을 찾는 것입니다. 길이가 n인 단어에는 2ⁿ개의 부분 수열이 있으므로, 글자가 몇 개만 넘어가도 모두 시도해 보는 것은 가망이 없습니다.

표

len[i][j]를 한 단어의 처음 i글자와 다른 단어의 처음 j글자의 최장 공통 부분 수열 길이라고 합시다. 빈 단어는 공통된 것이 없으므로 첫 행과 첫 열은 0입니다. i번째 글자와 j번째 글자가 같으면 len[i][j] = len[i − 1][j − 1] + 1입니다. 그 일치가 앞에 있던 결과를 늘려 줍니다. 그렇지 않으면 len[i][j]는 len[i − 1][j]와 len[i][j − 1] 중 큰 값입니다. 두 글자 중 하나를 버리고 더 나은 결과를 남기는 것입니다.

예제

ABCBDAB와 BDCABA를 비교해 봅시다. 두 번째 단어의 첫 글자 B는 2행의 B와 일치하고, 셋째 열의 C는 3행과 일치하는 식으로 이어지며, 일치할 때마다 왼쪽 위 칸에 1을 더합니다. 오른쪽 아래 칸은 결국 4가 됩니다. 거기서 거꾸로 읽으면 BCBA가 나오지만, BCAB와 BDAB도 길이가 같습니다. 최장 공통 부분 수열은 하나뿐이 아닐 수 있습니다.

답을 거꾸로 읽기

오른쪽 아래 칸에서 시작하세요. 그 행과 열의 글자가 일치하면 그 글자는 답에 속합니다. 적어 두고 대각선으로 왼쪽 위로 한 칸 이동합니다. 그렇지 않으면 위나 왼쪽 이웃 중 값이 더 큰 칸으로 이동합니다. 칸의 값이 거기서 왔기 때문입니다. 첫 행이나 첫 열에 닿으면 멈춥니다. 적어 둔 글자를 거꾸로 하면 부분 수열이 됩니다.

역사와 활용

표를 쓰는 방법은 1970년 무렵 여러 사람이 각자 독립적으로 발견했습니다. 그중에는 1974년 논문에서 밀접하게 관련된 편집 거리 문제를 푼 로버트 와그너와 마이클 피셔도 있습니다. 1975년 댄 허슈버그는 훨씬 적은 메모리로 부분 수열을 찾는 방법을 보였고, 1976년 제임스 헌트와 더글러스 매킬로이는 줄들의 최장 공통 부분 수열을 바탕으로 Unix diff 프로그램을 만들었습니다. 생물학자들은 같은 아이디어에 점수를 더해 DNA와 단백질 서열을 정렬합니다.

피터 애덤스가 Faces of Open Source를 위해 촬영한 더글러스 매클로이. 1976년 그와 제임스 헌트는 줄의 최장 공통 부분 수열을 바탕으로 유닉스 diff 프로그램을 만들었다.
피터 애덤스가 Faces of Open Source를 위해 촬영한 더글러스 매클로이. 1976년 그와 제임스 헌트는 줄의 최장 공통 부분 수열을 바탕으로 유닉스 diff 프로그램을 만들었다.

직접 살펴보기

앱을 열고 단계를 누르세요. 비교 중인 두 글자가 머리글에서 강조됩니다. 일치하면 왼쪽 위의 파란 칸을, 일치하지 않으면 위와 왼쪽의 두 파란 칸을 읽습니다. 표가 다 채워지면 주황색 경로가 모서리에서 거꾸로 올라가고, 답의 글자들이 표 아래에 나타납니다.

자주 묻는 질문

LCS 알고리즘에는 시간과 메모리가 얼마나 필요한가요?

길이가 m과 n인 단어라면 O(m·n) 시간이 걸립니다. 답을 거꾸로 읽으려면 전체 표가 필요하므로 메모리도 O(m·n)이 듭니다. 댄 허슈버그는 1975년에 부분 수열 자체를 O(min(m, n)) 메모리만으로 찾는 방법을 보였습니다.

diff는 최장 공통 부분 수열을 어떻게 쓰나요?

파일의 각 줄을 하나의 기호로 보고, 두 파일의 줄들의 최장 공통 부분 수열을 찾습니다. 그 부분 수열에 든 줄은 바뀌지 않은 것이고, 옛 파일의 나머지 줄은 삭제된 것, 새 파일의 나머지 줄은 추가된 것입니다.

단어가 셋 이상이면 어떻게 되나요?

단어 하나마다 표의 차원이 하나씩 늘어나므로, 길이가 n인 단어 세 개에는 n³개의 칸이 필요합니다. 단어 수가 임의라면 이 문제는 NP-난해입니다.

LCS는 편집 거리와 어떤 관계가 있나요?

삽입과 삭제만 허용하면, 두 단어의 편집 거리는 두 단어 길이의 합에서 최장 공통 부분 수열 길이의 두 배를 뺀 값입니다. 바꾸기까지 허용하면 레벤슈타인 거리가 되며, 이것도 아주 비슷한 표로 계산합니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

최장 공통 부분 수열 체험하기