LCS (Longest Common Subsequence) - 최장 공통 부분 수열 알고리즘
LCS 알고리즘은 두 문자열에서 공통된 부분 수열 중 가장 긴 부분 수열을 찾는 문제이다. 문자열 비교 문제에서 기본적으로 사용되는 알고리즘 중 하나로, 여러 응용 문제에서도 중요한 역할을 한다.
1. LCS란?
LCS는 두 문자열에서 순서를 유지하며, 연속적이지 않아도 되는 가장 긴 부분 수열을 의미한다.
예를 들어, 문자열 A = "ACAYKP"와 B = "CAPCAK"가 주어졌을 때, 공통 부분 수열 중 하나는 "ACAK"이며, 그 길이는 4다.
부분 수열이란 원래 문자열에서 순서를 유지하면서 일부 문자를 제거하여 만든 새로운 문자열이다.
2. 접근 방식 - DP 테이블 정의와 점화식
(1) DP 테이블 정의
두 문자열 A와 B의 길이를 각각 n, m이라 할 때, DP 테이블 dp[i][j]는 A의 처음 i번째 문자와 B의 처음 j번째 문자를 고려한 최장 공통 부분 수열의 길이를 의미한다. DP 테이블을 채워나가며 점진적으로 최장 공통 부분 수열을 찾아내려한다.
(2) 점화식
-
문자가 같을 때 (
A[i-1] == B[j-1]):
dp[i][j] = dp[i-1][j-1] + 1
현재 두 문자가 같다면, 이전까지의 LCS에 해당 문자를 추가한 형태이므로 길이가 1 증가 -
문자가 다를 때 (
A[i-1] != B[j-1]):
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
문자가 다르다면A의 마지막 문자를 포함하지 않거나B의 마지막 문자를 포함하지 않는 경우 중 최대 길이를 취한다.
(3) 초기화
dp[i][0]과 dp[0][j]는 0으로 초기화된다. 이는 길이가 0인 문자열과 비교할 때 공통 부분 수열의 길이가 0이기 때문이다.
3. 코드
A = "ABCBDAB", B = "BDCABC"일 때의 최장 공통 부분 수열의 길이는?
C++ 코드
#include <iostream>
using namespace std;
int dp[1001][1001];//전부 0으로 초기화된 상태
int main() {
string a = "ABCBDAB";
string b = "BDCABC";
int n = a.size();
int m = b.size();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[i - 1] == b[j - 1])
dp[i][j] = dp[i - 1][j - 1] + 1; // 문자가 같다면 길이 + 1
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); // 문자가 다르면 현재까지의 LCS 유지
}
}
cout << dp[n][m];
return 0;
}코드 설명
- 입력 문자열: 두 문자열
A와B의 길이를 기준으로dp테이블을 정의한다. - DP 테이블 초기화: 모든 값을 0으로 초기화한다.
- 문자 비교 및 값 갱신:
A[i-1] == B[j-1]일 때는 공통된 문자가 포함되어 길이가 1 증가하므로dp[i][j] = dp[i-1][j-1] + 1로 갱신- 그렇지 않으면,
dp[i][j] = max(dp[i-1][j], dp[i][j-1])로 갱신하여 최대 LCS 길이를 저장한다.
- 결과 반환: 최종적으로
dp[n][m]에 LCS의 길이가 저장되며, 이를 반환하면 끝이다.
예제 설명
| B | D | C | A | B | C | ||
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| A | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| B | 0 | 1 | 1 | 1 | 1 | 2 | 2 |
| C | 0 | 1 | 1 | 2 | 2 | 2 | 3 |
| B | 0 | 1 | 2 | 2 | 2 | 3 | 3 |
| D | 0 | 1 | 2 | 2 | 2 | 3 | 3 |
| A | 0 | 1 | 2 | 2 | 3 | 3 | 3 |
| B | 0 | 1 | 2 | 2 | 3 | 4 | 4 |
결과적으로, dp[7][6] = 4로 최장 공통 부분 수열의 길이는 4가 된다.
4. 시간 복잡도
알고리즘의 시간 복잡도는 O(n * m). 여기서 n과 m은 문자열 A와 B의 길이다. DP 테이블을 채우기 위해 n * m번의 비교 연산이 필요하기 때문이다.
5. LCS 문자열을 찾는 방법
길이를 구하는 DP 테이블을 이용해 역추적(backtracking)하는 방식으로 가능하다. 최장 공통 부분 수열의 길이를 구한 후, DP 테이블을 활용해 각 단계에서 공통 부분을 찾아 최종 LCS 문자열을 완성할 수 있다.
1. DP 테이블 생성 및 채우기:
우선, 두 문자열 A와 B에 대해 dp 테이블을 생성하고, 각 위치에 LCS의 길이를 저장해둔다.
2. 역추적 시작:
DP 테이블의 오른쪽 아래 끝(dp[n][m])에서 시작해, 두 문자열의 공통 부분을 역추적하며 찾는다.
3. 역추적 로직:
만약 A[i-1] == B[j-1]라면, 두 문자열의 현재 문자가 동일하다는 의미이므로 공통 부분에 포함된다. 이때, 해당 문자를 결과 문자열에 추가하고 i와 j를 각각 하나씩 감소시켜서 이전 위치로 이동한다.
만약 A[i-1] != B[j-1]라면, dp[i-1][j]와 dp[i][j-1] 중 더 큰 값으로 이동한다. 이는 두 문자열 중 한쪽의 문자를 제외하고 공통 부분 수열을 찾는 방식이다.
4. 결과 문자열 완성:
역추적이 끝나면, 찾은 공통 부분은 역순이므로 이를 뒤집어 최종 LCS 문자열을 완성한다.
// LCS 문자열 찾기 (역추적)
string lcs = "";
int i = n, j = m;
while (i > 0 && j > 0) {
if (A[i - 1] == B[j - 1]) {
lcs += A[i - 1];
i--; j--;
} else if (dp[i - 1][j] > dp[i][j - 1]) {
i--;
} else {
j--;
}
}
// 결과를 역순으로 뒤집어 반환
reverse(lcs.begin(), lcs.end());