LCS 2
백준 9252
GOLD IV
문제 내용
문제 링크
해결 방안
LCS(Longest Common Subsequence, 최장 공통 부분 수열)는 임의의 두 수열에 대하여, 두 수열 모두의 부분수열이 될 수 있는 수열들 중 가장 긴 수열을 의미힌다. 이 문제에서는 문자열의 각 알파벳들을 수열의 요소들로 간주하고, 주어진 두 문자열의 부분수열 중 가장 긴 문자열과 그 길이를 찾는 것이다.
본 코드는 다음 사이트의 풀이를 바탕으로 작성되었다. 다양한 풀이 방식과 시간 복잡도에 대해 적혀있으니 한 번 씩 읽는 것을 권장한다.
우선 두 문자열을 각각 a과 b, 각각의 인덱스를 i와 j로 정의한다. 우선 i와 j에 대해 이중 반복문을 통해 a와 b의 알파벳들을 비교해야 한다. 만약 a[i]와 b[j]가 같다면, 부분 수열의 길이를 늘리고 i와 j를 모두 1씩 증가시킨다. 반대로 a[i]와 b[j]가 다르다면 이전의 값을 가져오는데, 이전까지 찾은 부분수열 중 가장 길이가 긴 경우를 가져온다. 이 과정을 반복하면 결과적으로는, a의 길이가 0~i일 때와 b의 길이가 0~j일 때의 모든 결과들을 확인하게 된다. a와 b의 길이에 따른 각 결과를 저장해야 하므로, 메모이제이션을 이용한 바텀 업 방식을 사용하였다.
또한, 이 문제에서는 해당 문자열을 출력하는 것까지 요구하므로, 메모이제이션을 통해 얻은 결과를 역순으로 되짚어 가며 해당 결과를 출력해야 한다. 부분 수열의 가장 긴 길이에서 시작하여 길이가 증가했던 지점을 찾으면, a[i]와 b[j]가 같은 부분을 찾을 수 있다. 저장된 부분 수열의 길이가 작아질 때까지 i와 j를 감소시키고, (i-1)과 (j-1)이 같은 지점을 찾을 때까지 반복한다. 두 알파벳이 같으면 해당 알파벳을 저장하고, i와 j를 모두 1씩 감소시킨다. 결과적으로 길이가 0이 되면, 부분 수열의 길이가 긴 시점부터 작아지는 시점으로 저장했기 때문에 가장 긴 부분 수열이 역순으로 저장된 것을 알 수 있다. 때문에, LIFO 방식으로 늦게 들어온 알파벳부터 출력하면, 찾고자 했던 가장 긴 부분 수열이 출력된다.
부분 수열(subsequence)이란?
부분 수열(subsequence)은 주어진 수열의 일부 항을 원래 순서대로 나열하여 얻을 수 있는 수열이다. 다시 말해, 임의의 수열 p에 대해 수열의 순서가 바뀌지 않는 선에서, 그 수열의 일부 요소들로 구성된 수열을 p의 부분수열이라고 한다는 것이다. 특정 집합에서 그 집합 내 요소의 순서가 변하지 않은 위상의 부분집합으로 볼 수 있다. 여기서 순서라고 함은 자연수 i < j에 대해 수열에 A_i와 A_j가 포함된다고 한다면, A_i가 A_j보다 앞에 있어야 한다는 의미이다.
풀이 코드
#include <iostream>
#include <vector>
#include <string>
using namespace std;
// 부분 수열의 길이 메모이제이션
int lcs[1001][1001];
int main() {
// 문자 a와 b를 입력
string a, b;
cin >> a >> b;
// a의 길이와 b의 길이를 저장
int aLen = a.length();
int bLen = b.length();
// 각 자리를 0으로 초기화
for(int i = 0; i <= aLen; i++) {
for(int j = 0; j <= bLen; j++)
lcs[i][j] = 0;
}
// a의 i번째 글자와 b의 j번째 글자 비교
for(int i = 1; i <= aLen; i++) {
for(int j = 1; j <= bLen; j++) {
// 현재 글자가 같은 경우, (이전의 부분 수열의 길이 + 1) 저장
if(a[i - 1] == b[j - 1])
lcs[i][j] = lcs[i - 1][j - 1] + 1;
// 현재 글자가 다를 경우, 이전의 부분 수열의 최대 길이 저장
else
lcs[i][j] = max(lcs[i][j - 1], lcs[i - 1][j]);
}
}
// 가장 마지막 위치 저장
int i = aLen;
int j = bLen;
// LIFO 방식으로 출력하기 위한 스택
vector<char> answer;
// lcs 길이가 없을 때까지 역행
while(lcs[i][j] != 0) {
// 현재 위치가 부분 수열이 증가하는 위치면 같은 글자 저장
if(a[i - 1] == b[j - 1]) {
answer.push_back(a[i - 1]);
i--, j--;
}
// 글자가 다를 경우, 부분 수열이 더 긴 방향으로 이동
else {
if(lcs[i - 1][j] > lcs[i][j - 1])
i--;
else
j--;
}
}
// 부분 수열의 최대 길이 출력
cout << answer.size() << '\n';
// 역순으로 저장된 부분 수열 거꾸로 출력
while(!answer.empty()) {
cout << answer.back();
answer.pop_back();
}
cout << endl;
return 0;
}