발상 & 풀이
문제 자체에 대한 점화식과 발상은 LCS 참고.
구조가 이전 문제와 같기 때문에 쉽게 풀릴 거라 생각하지만 생각보다 역추적이 까다롭다.
이전 문제들과 다르게 이전 결과를 간접적으로만 가져와 연산하기 때문에 실제 인덱스를 바로 알 수 없기 때문이다.
이게 무슨 말이냐면, LIS 문제에서는 어떤 인덱스 에 대한 연산을 할 때, LIS 내의 이전 인덱스 후보들을 직접 비교하고 선택하기 때문에 의 이전 LIS 항목이 되는 요소의 인덱스를 바로 알 수 있었다.
LIS의 점화식 자체에도 이전 인덱스가 로 포함되어 있다.
1 3 2 1 6 7이라는 예제에서 LIS에 해당하는 1 2 6 7의 각 요소는 모두 자신 이전 요소의 인덱스를 탐색 과정에서 바로 알 수 있다.
그에 반해, LCS 문제는 현재 인덱스 , 가 일치한 후보를 직접 탐색하지 않는다.
LCS 점화식을 보면 현재 인덱스 , 이전에 일치하는 인덱스를 별도로 특정하지 않는다.
간접적으로 , 이전의 모든 영역의 최적값만 저장할 뿐이다.
이 ‘이전의 모든 영역’에 이전에 일치한 인덱스가 들어있다고만 알고 있을 뿐 그 인덱스를 정확히 알 수 없다.
따라서 이 인덱스를 정확하게 알아내기 위한 로직 자체를 새로 개발해야 한다.
우선 로직이 해야하는 일을 정확하게 정의하면 아래와 같다.
모든
dp[i][j]의 위치에서 이전에 문자열이 일치한 위치 , 를 추가로 기록한다.
LCS 알고리즘은 현재 두 인덱스의 문자의 일치 여부에 따라
- 일치 할 경우 :
dp[i - 1][j - 1] + 1 - 일치하지 않을 경우 :
max(dp[i - 1][j], dp[i][j - 1])중에 선택하게 된다. 상기의 이전 상태들 (dp[i - 1][j - 1],dp[i - 1][j],dp[i][j - 1]) 에서 일치 여부를 검사해 일치한 경우, 그 일치한 인덱스를 저장하고 일치하지 않는 경우에는 이전에 저장된 일치한 인덱스를 그대로 복사하면 된다.
역추적
이제 역추적을 위한 장치는 마련되었다. 우리는 어떤 위치에서든 그 위치 이전에 문자가 일치한 가장 최근 인덱스를 알 수 있다. LCS의 길이가 저장되어있는 가장 마지막 인덱스를 기준으로 재귀 탐색을 시작하며 역순으로 문자들을 출력하면 LCS를 출력할 수 있다. 한가지 주의해야할 점은 우리는 항상 그 인덱스의 이전에 일치한 문자만 출력하기 때문에 만약 마지막 인덱스 쌍이 LCS에 포함된 경우, 그 문자는 재귀 탐색에서 출력되지 않는다. 이 경우만 별도로 처리해주면 된다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
struct node {
int c = 0, p1 = -1, p2 = -1;
};
string s1, s2;
void printlcs(int i, int j, vector<vector<node>>& dp) {
if (i == -1 && j == -1) { // 더 이상 이전 LCS가 없는 경우
return;
}
printlcs(dp[i][j].p1, dp[i][j].p2, dp);
cout << s1[i - 1];
}
int main() {
cin >> s1 >> s2; int n1 = s1.size(), n2 = s2.size(); vector<vector<node>> dp(n1 + 1, vector<node>(n2 + 1));
for (int i = 1; i <= n1; i++) {
for (int j = 1; j <= n2; j++) {
if (s1[i - 1] == s2[j - 1]) {
dp[i][j].c = dp[i - 1][j - 1].c + 1;
// 이전 인덱스의 문자가 일치한 경우, 그 인덱스 저장. 일치하지 않은 경우 이전 인덱스 계승
dp[i][j].p1 = i - 2 >= 0 && j - 2 >= 0 && s1[i - 2] == s2[j - 2] ? i - 1 : dp[i - 1][j - 1].p1;
dp[i][j].p2 = i - 2 >= 0 && j - 2 >= 0 && s1[i - 2] == s2[j - 2] ? j - 1 : dp[i - 1][j - 1].p2;
}
else {
if (dp[i - 1][j].c > dp[i][j - 1].c) {
dp[i][j].c = dp[i - 1][j].c;
dp[i][j].p1 = i - 2 >= 0 && s1[i - 2] == s2[j - 1] ? i - 1 : dp[i - 1][j].p1;
dp[i][j].p2 = i - 2 >= 0 && s1[i - 2] == s2[j - 1] ? j : dp[i - 1][j].p2;
}
else {
dp[i][j].c = dp[i][j - 1].c;
// 이전 인덱스의 문자가 일치한 경우, 그 인덱스 저장. 일치하지 않은 경우 이전 인덱스 계승
dp[i][j].p1 = j - 2 >= 0 && s1[i - 1] == s2[j - 2] ? i : dp[i][j - 1].p1;
dp[i][j].p2 = j - 2 >= 0 && s1[i - 1] == s2[j - 2] ? j - 1 : dp[i][j - 1].p2;
}
}
}
}
cout << dp[n1][n2].c << "\n";
printlcs(dp[n1][n2].p1, dp[n1][n2].p2, dp);
if (s1[n1 - 1] == s2[n2 - 1]) { // 마지막 인덱스의 문자가 서로 일치하는 경우 검사
cout << s1[n1 - 1];
}
return 0;
}