최장 공통 부분 수열

Article on other languages:

• Longest_common_subsequence_problem
• Plus_longue_sous-séquence_commune
• Najdłuższy_wspólny_podciąg
• Наибольшая_общая_подпоследовательность
• 最长公共子序列

	del.icio.us
	Digg
	Furl
	Reddit
	Rojo
	Add to OnlyWire

최장 공통 부분수열 문제는 주어진 여러 개의 수열 모두의 부분수열이 되는 수열들 중에 가장 긴 것을 찾는 문제다. 컴퓨터 과학에서 고전으로 통하는 문제이며, diff 유틸리티의 근간이 되며, 생물정보학에서도 많이 응용되고 있다.

이 문제는 연속되어 있는 공통 문자열을 찾는 최장 공통 부분문자열(longest common substring) 문제와 혼동해서는 안 된다.

복잡도

이 문제는 임의의 수의 수열의 경우 NP-난해의 복잡도를 갖는다^[1]. 그러나 주어진 수열의 개수가 일정할 때 이 문제는 동적 계획법에의해 다항시간 안에 풀린다. 각각의 길이가 인 N개의 수열이 주어졌다고 하자. 무식하게 해를 찾는 방법은, 모든 각 수열의 모든 가능한 부분수열을 전부 하나씩 구해 비교해 보는 것이며, 이 때의 경우의 수는 다음과 같다.

.

반면, 동적 계획법을 이용하면 경우의 수는 아래의 복잡도로 줄어든다.

복잡도를 더 낮출 수 있는 방법도 있으며^[2], 이 방법의 복잡도는 최장 공통 수열의 길이, 수열을 이루는 알파벳의 크기 등에 좌우된다.

두 개의 수열에 대한 해

두 수열 and 이 주어졌을 때, 주어진 두 수열의 최장 공통 부분수열(longest common subsequence)은 다음과 같이 표현된다.

여기서 + 는 더하기가 아니라 수열의 끝에 붙인다는 의미를 갖으며, max 는 둘 중에 긴 것을 택하는 함수이다.

이 문제는 최적 부분구조(optimal substructure) 성질을 갖기 때문에, 이 문제는 동적 계획법으로 풀 수 있다. 자세한 것은 이것^[3]을 보라.

위 재귀적인 식을 설명해 보면 이렇다. 두 수열의 마지막 문자가 같다면, 이 문자는 최장 공통 부분열에 들어간다. 왜냐하면, j < n인 j, n에 대해 x_m을 y_j에 맞추어서 공통 부분열을 만들어서는 절대로 더 긴 공통 부분열을 만들 수 없기 때문이다. 이 둘이 갖지 않다면, x_m와 y_n 둘 중에 어느 것을 지우고 만들어지는 것이 더 긴지를 비교하여 긴 것을 선택한다. 만약 모든 최장 공통 부분열을 구하고자 한다면, 두 경우의 길이가 같은 경우에는 마지막 max함수 대신에 둘 모두를 포함하는 집합을 결과로 내주는 함수로 바꾸어야 할 것이다.

참조

1. ↑ David Maier (1978). The Complexity of Some Problems on Subsequences and Supersequences. J. ACM 25 (2): 322–336. DOI:10.1145/322063.322075.
2. ↑ L. Bergroth and H. Hakonen and T. Raita (2000). A Survey of Longest Common Subsequence Algorithms. SPIRE 00: 39–48. DOI:10.1109/SPIRE.2000.878178. ISBN 0-7695-0746-8.
3. ↑ 토머스 H. 코르먼, 카를리스 E. 레이서슨, 로널드 라이베스트, 그리고 클리포드 스타인. "15.4", Introduction to Algorithms, second edition, MIT 프레스와 McGraw-Hill, 350-355. ISBN 0-262-53196-8.