최단 공통 초수열(SCS) 완벽 정리: 개념부터 동적 계획법 구현까지

최단 공통 초수열(Shortest Common Supersequence, SCS)은 주어진 두 시퀀스의 모든 요소를 포함하는 가장 짧은 시퀀스를 의미합니다. 다시 말해, 두 문자열이 모두 이 초수열의 부분 수열(subsequence)이 되도록 만드는 문자열이라고 할 수 있습니다.

두 문자열 사이에 공통 문자가 전혀 없다면, 단순히 두 문자열을 이어 붙이는 것만으로 초수열을 얻을 수 있습니다. 하지만 공통 문자가 존재하는 경우에는 공통 부분을 한 번만 사용하도록 두 문자열을 교차 병합해야 하며, 이때 초수열의 길이는 두 문자열 길이의 합에서 최장 공통 부분 수열(LCS)의 길이를 뺀 값이 됩니다.

입력 및 출력

입력:
두 문자열 "ABCDEF"와 "XYDEF"
출력:
최단 공통 초수열의 길이
여기서 초수열은 "ABCXYDEF"이며, 따라서 길이는 8입니다.

알고리즘

동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해를 구할 수 있습니다. 테이블의 각 칸에는 문자열의 앞부분 일부에 대한 최단 초수열 길이가 저장되며, 두 문자가 같으면 대각선 값에 1을 더하고, 다르면 위쪽 또는 왼쪽 값 중 작은 값에 1을 더합니다.

superSeq(str1, str2)

입력: 두 문자열 str1과 str2

출력: 최단 공통 초수열의 길이

Begin
   m := str1의 길이
   n := str2의 길이
   (m+1) x (n+1) 크기의 테이블 seqTab 정의

   for i := 0 to m, do
      for j := 0 to n, do
         if i = 0, then
           seqTab[i, j] := j  // str1이 빈 문자열이면 초수열 길이는 j
         else if j = 0, then
           seqTab[i, j] := i  // str2가 빈 문자열이면 초수열 길이는 i
         else if str1[i-1] = str2[j-1], then
           seqTab[i, j] := 1 + seqTab[i-1, j-1]
         else
           seqTab[i, j] := 1 + min(seqTab[i-1, j], seqTab[i, j-1])
      done
   done
   return seqTab[m, n]
End

구현 예제 (C++)

#include<iostream>
using namespace std;

int min(int a, int b) {
   return (a<b)?a:b;
}

int superSeq(string str1, string str2) {
   int m = str1.size();
   int n = str2.size();

   int supSeqTable[m+1][n+1];

   for (int i = 0; i <= m; i++) {
      for (int j = 0; j <= n; j++) {
         if (!i)
           supSeqTable[i][j] = j;  // str1이 비어 있으면 초수열 길이는 j
         else if (!j)
           supSeqTable[i][j] = i;  // str2가 비어 있으면 초수열 길이는 i
         else if (str1[i-1] == str2[j-1])
           supSeqTable[i][j] = 1 + supSeqTable[i-1][j-1];
         else
           supSeqTable[i][j] = 1 + min(supSeqTable[i-1][j], supSeqTable[i][j-1]);
      }
   }
   return supSeqTable[m][n];
}

int main() {
   string first = "ABCDEF";
   string second = "XYDEF";
   cout << "Length of the shortest supersequence is " << superSeq(first, second);
}

실행 결과

Length of the shortest supersequence is 8

이 알고리즘의 시간 복잡도는 O(m×n)으로, 두 문자열의 길이 곱에 비례합니다. 최장 공통 부분 수열(LCS) 문제와 밀접한 관련이 있어, 면접이나 코딩 테스트에서 자주 등장하는 대표적인 동적 계획법 응용 문제 중 하나입니다.