LCS - 최장 공통 부분 수열이란?
LCS(Longest Common Subsequence)란 두 수열이나 문자열에서 공통되는 가장 긴 부분수열 혹인 부분문자열이다.
Subsequence이므로 연속적일 필요는 없다.
아래와 같이 두 개의 문자열이 있다고 하자.
문자열1 : "ACAYKP"
문자열2 : "CAPCAK"
여기서 LCS는 "ACAK"가 된다.
이제 이것을 알고리즘으로 구현해보고자 한다.
문제 접근
일반적인 LCS는 Dynamic Programming으로 해결할 수 있다.
먼저 문자열1("ACAYKP")를 x축에, 문자열2("CAPCAK")를 y축에 둔 후 비교를 진행한다.
| i\j | A | C | A | Y | P | K |
|---|---|---|---|---|---|---|
| C |
"A"와 "C" 비교 -> LCS=""
| i\j | A | C | A | Y | P | K |
|---|---|---|---|---|---|---|
| C | 0 |
"AC"와 "C" 비교 -> LCS="C"
| i\j | A | C | A | Y | P | K |
|---|---|---|---|---|---|---|
| C | 0 | 1 |
"ACA"와 'C' 비교 -> LCS="C"
| i\j | A | C | A | Y | P | K |
|---|---|---|---|---|---|---|
| C | 0 | 1 | 1 |
"ACAY"와 "C" 비교 -> LCS="C"
| i\j | A | C | A | Y | P | K |
|---|---|---|---|---|---|---|
| C | 0 | 1 | 1 | 1 |
"ACAYP"와 "C" 비교 -> LCS="C"
| i\j | A | C | A | Y | P | K |
|---|---|---|---|---|---|---|
| C | 0 | 1 | 1 | 1 | 1 |
"ACAYPK"와 "C" 비교 -> LCS="C"
| i\j | A | C | A | Y | P | K |
|---|---|---|---|---|---|---|
| C | 0 | 1 | 1 | 1 | 1 | 1 |
아직 규칙 파악이 잘 안되므로 한 줄만 더 진행해보자.
| i\j | A | C | A | Y | P | K |
|---|---|---|---|---|---|---|
| C | 0 | 1 | 1 | 1 | 1 | 1 |
| A |
"A"와 "CA" 비교 -> LCS="A"
| i\j | A | C | A | Y | P | K |
|---|---|---|---|---|---|---|
| C | 0 | 1 | 1 | 1 | 1 | 1 |
| A | 1 |
"AC"와 "CA" 비교 -> LCS="A" or "C"
| i\j | A | C | A | Y | P | K |
|---|---|---|---|---|---|---|
| C | 0 | 1 | 1 | 1 | 1 | 1 |
| A | 1 | 1 |
"ACA"와 "CA" 비교 -> LCS="CA"
| i\j | A | C | A | Y | P | K |
|---|---|---|---|---|---|---|
| C | 0 | 1 | 1 | 1 | 1 | 1 |
| A | 1 | 1 | 2 |
"ACAY"와 "CA" 비교 -> LCS="CA"
| i\j | A | C | A | Y | P | K |
|---|---|---|---|---|---|---|
| C | 0 | 1 | 1 | 1 | 1 | 1 |
| A | 1 | 1 | 2 | 2 |
"ACAYP"와 "CA" 비교 -> LCS="CA"
| i\j | A | C | A | Y | P | K |
|---|---|---|---|---|---|---|
| C | 0 | 1 | 1 | 1 | 1 | 1 |
| A | 1 | 1 | 2 | 2 | 2 |
"ACAYPK"와 "CA" 비교 -> LCS="CA"
| i\j | A | C | A | Y | P | K |
|---|---|---|---|---|---|---|
| C | 0 | 1 | 1 | 1 | 1 | 1 |
| A | 1 | 1 | 2 | 2 | 2 | 2 |
"A"와 "CA" 비교 -> LCS="A"
두줄을 비교해봤는데 여기서 문자열1[j]와 문자열2[i]가 같을때와 다를때로 나눠서 생각해보자.
문자열1[j] != 문자열2[i] ) 위쪽의 값이나 왼쪽의 값 중 큰 값이 들어간다.
왜냐하면? 어차피 현재 비교하는 문자가 서로 다르므로 값을 증가시킬 수 없다. 따라서 직전의 값 중 가장 큰 값이 들어가야 하는데 직전의 값은 왼쪽, 위쪽 2가지가 있으므로 비교하여 가장 큰 값을 넣는 것이다.
문자열1[j] == 문자열2[i] ) 왼쪽 위 대각선의 값에 1을 더한 값이 들어간다.
현재 비교하는 문자가 같은 경우 값을 증가시킬 수 있다. i와 j를 1씩 증가시키기 전(현재 문자열1 & 문자열2 보다 길이가 1씩 작을 때)의 값 + 1을 해야하므로 (왼쪽 위 대각선의 값 + 1) 이 된다.
따라서 우리는 다음과 같이 정리할 수 있다.
for (int i = 0; i < str2.size(); i++) {
for (int j = 0; j < str1.size(); j++) {
if (str1[j] == str1[i])
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}하지만 여기서 문제가 하나 발생한다.
만약 첫번째 줄의 첫번째 문자를 비교할 때 바로 일치하게 될 경우
dp[0][0] = dp[-1][-1] + 1을 수행하게 되고 이것은 segmentation fault가 발생한다.
따라서 우리는 두 문자열 앞에 의미 없는 값("0")을 두고 dp테이블에도 값을 0으로 설정해주어야 segmentation fault를 방지할 수 있다.
이렇게 점화식을 따라 DP테이블을 채우면 LCS는 DP테이블의 가장 오른쪽 밑의 값이 된다.
최종 코드
#include <iostream>
#include <vector>
using namespace std;
string s1, s2;
vector<vector<int>> dp;
int main() {
cin >> s1 >> s2;
s1 = "0" + s1;
s2 = "0" + s2;
dp.resize(s2.size(), vector<int>(s1.size()));
for (int i = 0; i < s2.size(); i++) {
for (int j = 0; j < s1.size(); j++) {
if (i == 0 || j == 0)
dp[i][j] = 0;
else if (s1[j] == s2[i])
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
cout << dp[s2.size()-1][s1.size()-1] << endl;
return 0;
}결과
