최장 공통 서열(Longest Common Subsequence, LCS) 문제는 두 문자열이 주어졌을 때, 두 문자열 모두에서 공통으로 나타나는 가장 긴 부분 서열을 찾는 문제입니다. 이 문제를 해결하는 방법을 단계별로 설명하겠습니다.
1) 재귀적 관계 파악하기
먼저, 두 문자열 (X)와 (Y)의 LCS를 찾기 위해 재귀적 관계를 정의합니다. 각 문자열의 마지막 문자가 일치하는지 여부에 따라 다음과 같은 경우로 나눌 수 있습니다:
경우 1: (X)와 (Y)의 마지막 문자가 일치하는 경우
- 이 경우, (X)와 (Y)의 마지막 문자를 LCS에 추가하고, 나머지 부분 문자열에 대한 LCS를 구합니다.
- 예: (X = "ABC"), (Y = "BDC")일 때, 마지막 문자 'C'가 일치합니다. 따라서, LCS("ABC", "BDC") = LCS("AB", "BD") + 'C'.
경우 2: (X)와 (Y)의 마지막 문자가 일치하지 않는 경우
- 이 경우, 두 가지 가능성을 고려해야 합니다. 하나는 (X)의 마지막 문자를 제외한 경우, 다른 하나는 (Y)의 마지막 문자를 제외한 경우입니다.
- 예: (X = "ABC"), (Y = "BDA")일 때, 마지막 문자가 일치하지 않습니다. 따라서, LCS("ABC", "BDA") = max(LCS("AB", "BDA"), LCS("ABC", "BD")).
2) 재귀적으로 정의하기
위의 재귀적 관계를 사용하여 LCS를 다음과 같이 정의할 수 있습니다:
[
LCS(X[1..m], Y[1..n]) =
\begin{cases}
0 & \text{if } m = 0 \text{ or } n = 0 \
LCS(X[1..m-1], Y[1..n-1]) + 1 & \text{if } X[m] = Y[n] \
\max(LCS(X[1..m-1], Y[1..n]), LCS(X[1..m], Y[1..n-1])) & \text{if } X[m] \neq Y[n]
\end{cases}
]
3) 중복 부분 문제
재귀적으로 정의된 LCS는 많은 중복 계산을 포함합니다. 예를 들어, LCS("ABC", "BDC")를 계산할 때, LCS("AB", "BD")를 여러 번 계산할 수 있습니다. 이러한 중복 계산을 피하기 위해 동적 계획법(Dynamic Programming)을 사용합니다.
4) 최적해의 재구성
동적 계획법을 사용하여 최적해를 재구성하는 방법은 다음과 같습니다.
DP 테이블 채우기:
두 문자열 (X)와 (Y)의 길이를 각각 (m)과 (n)이라고 할 때, 크기 ((m+1) \times (n+1))의 DP 테이블 (dp)를 만듭니다. 여기서 (dp[i][j])는 (X[1..i])와 (Y[1..j])의 LCS 길이를 저장합니다.int LCS(string X, string Y) { int m = X.size(); int n = Y.size(); vector<vector<int>> dp(m+1, n+1); for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i == 0 || j == 0) dp[i][j] = 0; else if (X[i-1] == Y[j-1]) dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]); } } return dp[m][n]; }최적해 재구성:
DP 테이블을 채운 후, (dp[m][n])에는 LCS의 길이가 저장됩니다. 이제 실제 LCS 문자열을 재구성하려면 (dp) 테이블을 역추적합니다.string LCS(string X, string Y) { int m = X.size(); int n = Y.size(); vector<vector<int>> dp(m+1, n+1); for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i == 0 || j == 0) dp[i][j] = 0; else if (X[i-1] == Y[j-1]) dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]); } } // 역추적 int index = dp[m][n]; string lcs(index, ' '); int i = m, j = n; while (i > 0 && j > 0) { if (X[i-1] == Y[j-1]) { lcs[index-1] = X[i-1]; i--; j--; index--; } else if (dp[i-1][j] > dp[i][j-1]) i--; else j--; } return lcs; }
이와 같이, 재귀적 관계를 파악하고, 이를 바탕으로 재귀적으로 정의하며, 중복 부분 문제를 동적 계획법을 통해 해결하고, 최적해를 재구성하는 과정을 통해 LCS 문제를 효율적으로 해결할 수 있습니다.