가장 긴 공통 부분 수열(LCS)을 구하는 C++ 프로그램

부분 수열(subsequence)은 주어진 문자열에서 원소들의 상대적인 순서를 그대로 유지한 채 일부 원소를 선택하여 만든 수열입니다. 예를 들어 문자열 "stuv"의 부분 수열로는 "stu", "tuv", "suv", "sv" 등이 있습니다.

길이가 n인 문자열에서 만들 수 있는 부분 수열의 개수는 공집합을 포함하여 최대 2ⁿ개입니다.

예제

문자열 "ABCDGH"와 "AEDFHR"의 가장 긴 공통 부분 수열(LCS)은 "ADH"이며, 그 길이는 3입니다.

C++ 구현 코드

아래 코드는 재귀 호출을 이용해 두 문자열의 LCS 길이를 구하는 기본적인 방식입니다. 두 문자열의 마지막 문자가 서로 같으면 해당 문자를 LCS에 포함하고(1을 더함) 두 문자열 모두 한 글자씩 줄여 재귀 호출합니다. 다르다면 한쪽 문자열만 줄인 두 경우 중 더 큰 값을 선택합니다.

#include <iostream>
#include <string.h>
using namespace std;
int max(int a, int b);
int lcs(char* X, char* Y, int m, int n){
   if (m == 0 || n == 0)
      return 0;
   if (X[m - 1] == Y[n - 1])
      return 1 + lcs(X, Y, m - 1, n - 1);
   else
      return max(lcs(X, Y, m, n - 1), lcs(X, Y, m - 1, n));
}
int max(int a, int b){
   return (a > b) ? a : b;
}
int main(){
   char X[] = "AGGTAB";
   char Y[] = "GXTXAYB";
   int m = strlen(X);
   int n = strlen(Y);
   printf("Length of LCS is %d\n", lcs(X, Y, m, n));
   return 0;
}

출력 결과

Length of LCS is 4

위 예제에서 "AGGTAB"과 "GXTXAYB"의 가장 긴 공통 부분 수열은 "GTAB"이므로 길이는 4가 됩니다.

참고: 시간 복잡도

위 재귀 방식은 최악의 경우 시간 복잡도가 O(2^m+n)으로 매우 비효율적입니다. 문자열이 길어지면 중복되는 하위 문제가 많아지기 때문에, 실제로는 메모이제이션이나 동적 계획법(DP)을 활용하면 O(m×n)의 시간 복잡도로 효율적으로 해결할 수 있습니다.