이번 글에서는 LCS(Longest Common Subsequence, 최장 공통 부분 수열) 문제를 해결하는 공간 최적화 기법을 살펴보겠습니다. 예를 들어 두 문자열이 "BHHUBC"와 "HYUYBZC"라면, 공통 부분 수열의 길이는 4가 됩니다.
일반적인 동적 계획법(Dynamic Programming) 접근 방식도 존재하지만, 이 방식은 많은 메모리를 필요로 합니다. 첫 번째 문자열의 길이가 m, 두 번째 문자열의 길이가 n일 때, m × n 크기의 테이블 전체를 저장해야 하기 때문입니다.
하지만 기존 방식을 자세히 관찰해 보면 흥미로운 사실을 발견할 수 있습니다. 각 반복 단계에서 실제로 필요한 데이터는 바로 이전 행뿐이라는 점입니다. 즉, 전체 행을 유지할 필요가 없으므로 크기가 2n인 테이블만 있으면 충분합니다. 이를 활용하면 보조 공간을 O(n)까지 줄일 수 있습니다.
알고리즘
lcs_problem(X, Y) −
begin m := length of X n := length of Y define table of size L[2, n+1] index is to point 0th or 1st row of the table L. for i in range 1 to m, do index := index AND 1 for j in range 0 to n, do if i = 0 or j = 0, then L[index, j] := 0 else if X[i - 1] = Y[j - 1], then L[index, j] := L[1 – index, j - 1] + 1 else L[index, j] := max of L[1 – index, j] and L[index, j-1] end if done done return L[index, n] end
핵심 아이디어
- 2개의 행만 번갈아 사용하여 마치 롤링 배열(rolling array)처럼 동작합니다.
index = i & 1연산으로 현재 행과 이전 행을 교차적으로 가리킵니다.- 두 문자가 일치하면 대각선 방향 값(이전 행, 이전 열)에 1을 더하고, 일치하지 않으면 위쪽 값과 왼쪽 값 중 큰 것을 선택합니다.
C++ 구현 예제
#include <iostream>
using namespace std;
int lcsOptimized(string &X, string &Y) {
int m = X.length(), n = Y.length();
int L[2][n + 1];
bool index;
for (int i = 0; i <= m; i++) {
index = i & 1;
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0)
L[index][j] = 0;
else if (X[i-1] == Y[j-1])
L[index][j] = L[1 - index][j - 1] + 1;
else
L[index][j] = max(L[1 - index][j], L[index][j - 1]);
}
}
return L[index][n];
}
int main() {
string X = "BHHUBC";
string Y = "HYUYBZC";
cout << "Length of LCS is :" << lcsOptimized(X, Y);
}실행 결과
Length of LCS is :4
정리
이 최적화 기법은 시간 복잡도를 그대로 O(m × n)으로 유지하면서, 공간 복잡도를 O(m × n)에서 O(n)으로 크게 줄여줍니다. 문자열이 매우 길어져 전체 DP 테이블을 메모리에 담기 어려운 상황에서 특히 유용한 접근 방식입니다. 다만 역추적(backtracking)을 통해 실제 부분 수열을 구해야 하는 경우에는 전체 테이블이 필요하므로, 이 기법은 LCS의 길이만 구할 때 적합하다는 점을 기억해 두시기 바랍니다.