최장 공통 부분 수열
위키백과 ― 우리 모두의 백과사전.
최장 공통 부분수열 문제는 주어진 여러 개의 수열 모두의 부분수열이 되는 수열들 중에 가장 긴 것을 찾는 문제다. 컴퓨터 과학에서 고전으로 통하는 문제이며, diff 유틸리티의 근간이 되며, 생물정보학에서도 많이 응용되고 있다.
이 문제는 연속되어 있는 공통 문자열을 찾는 최장 공통 부분문자열(longest common substring) 문제와 혼동해서는 안 된다.
[편집] 복잡도
이 문제는 임의의 수의 수열의 경우 NP-난해의 복잡도를 갖는다[1]. 그러나 주어진 수열의 갯수가 일정할 때 이 문제는 동적 계획법에의해 다항시간 안에 풀린다. 각각의 길이가
인 N개의 수열이 주어졌다고 하자. 무식하게 해를 찾는 방법은, 모든 각 수열의 모든 가능한 부분수열을 전부 하나씩 구해 비교해 보는 것이며, 이 때의 경우의 수는 다음과 같다.
.
반면, 동적 계획법을 이용하면 경우의 수는 아래의 복잡도로 줄어든다.
복잡도를 더 낮출 수 있는 방법도 있으며[2], 이 방법의 복잡도는 최장 공통 수열의 길이, 수열을 이루는 알파벳의 크기 등에 좌우된다.
[편집] 두 개의 수열에 대한 해
두 수열
and
이 주어졌을 때, 주어진 두 수열의 최장 공통 부분수열(longest common subsequence)은 다음과 같이 표현된다.
여기서 + 는 더하기가 아니라 수열의 끝에 붙인다는 의미를 갖으며, max 는 둘 중에 긴 것을 택하는 함수이다.
이 문제는 최적 부분구조(optimal substructure) 성질을 갖기 때문에, 이 문제는 동적 계획법으로 풀 수 있다. 자세한 것은 이것[3]을 보라.
위 재귀적인 식을 설명해 보면 이렇다. 두 수열의 마지막 문자가 같다면, 이 문자는 최장 공통 부분열에 들어간다. 왜냐하면, j < n인 j, n에 대해 xm을 yj에 맞추어서 공통 부분열을 만들어서는 절대로 더 긴 공통 부분열을 만들 수 없기 때문이다. 이 둘이 갖지 않다면, xm와 yn 둘 중에 어느 것을 지우고 만들어지는 것이 더 긴지를 비교하여 긴 것을 선택한다. 만약 모든 최장 공통 부분열을 구하고자 한다면, 두 경우의 길이가 같은 경우에는 마지막 max함수 대신에 둘 모두를 포함하는 집합을 결과로 내주는 함수로 바꾸어야 할 것이다.
[편집] 참조
- ↑ David Maier (1978). "The Complexity of Some Problems on Subsequences and Supersequences". J. ACM 25: 322–336. DOI:10.1145/322063.322075.
- ↑ 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.
- ↑ 틀:Cite book



