최장 공통 부분 수열

위키백과 ― 우리 모두의 백과사전.

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

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

[편집] 복잡도

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

\sum_{L=0}^{\min_{i=1}^{N}{n_i}} \prod_{k=1}^{N}{n_k \choose L}.

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

\Theta\left(N \prod_{k=1}^{N} n_k\right)

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

[편집] 두 개의 수열에 대한 해

두 수열 X_{1 \dots m} and Y_{1 \dots n}이 주어졌을 때, 주어진 두 수열의 최장 공통 부분수열(longest common subsequence)은 다음과 같이 표현된다.


\textrm{LCS}\left(X_{1 \dots i},Y_{1 \dots j}\right) =
\begin{cases}
  \emptyset                                                                                                                      & \mbox{ if } i = 0 \mbox{ or } j = 0 \\
  \textrm{LCS}\left(X_{1 \dots i-1},Y_{1 \dots j-1}\right) + x_{i}                                                                & \mbox{ if } x_i = y_j \\
  \max\left(\textrm{LCS}\left(X_{1 \dots i},Y_{1 \dots j-1}\right),\textrm{LCS}\left(X_{1 \dots i-1},Y_{1 \dots j}\right)\right) & \mbox{ otherwise} \\
\end{cases}

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

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

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

[편집] 참조

  1. David Maier (1978). "The Complexity of Some Problems on Subsequences and Supersequences". J. ACM 25: 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.
  3. 틀:Cite book