문제 이해 단계
https://www.acmicpc.net/problem/9252
9252번: LCS 2
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
LCS는 두 수열이 주어졌을 때, 두 수열의 공통이 되는 부분 수열 중 가장 긴 것을 찾는 문제이다.
가장 긴 수열의 길이를 출력하고, 둘째 줄에 LCS를 출력한다.
LCS가 여러 가지일 경우엔 아무거나 출력하고,
LCS의 길이가 0인 경우에는 둘째 줄은 출력하지 않는다.
문제 접근 단계
LCS 길이 구하기
[C++] 백준 9251 - LCS
문제 이해 단계 문제 LCS(Longest Common Subsequence, 최장 공통부분 수열) 문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는
howudong.tistory.com
해당 문제와 완벽히 같은 문제이다.
다른 점은 해당 링크의 문제는 LCS의 길이만 구하면 되는 것이고,
해당 문제에서는 LCS의 길이와 함께 LCS가 무엇인지까지 구해야 한다.
일단 LCS의 길이를 구하는 방법은 기존 LCS 문제를 푸는 방법과 동일하다.
이는 예전에 2가지 방법으로 자세히 서술했기 때문에 위 링크를 참조하길 바란다.
결론적으로 점화식은 이렇게 나온다.
첫 번째 문자열을 A, 두 번째 문자열을 B라고 가정하자.
if(A [i] == B [j]) dp [i][j] = dp [i-1][j-1] + 1
else dp [i][j] = MAX(dp [i-1][j], dp [i][j-1])
길이는 예전처럼 쉽게 구할 수 있다.
문제는 LCS 문자가 무엇인가를 얻는 방법이다.
알 수 있는 정보, 가지고 있는 정보 파악
이를 구하기 위해 우리가 알 수 있는 정보를 파악해 보자.
일단 단순하게 우리는 LCS의 길이를 구하는 점화식을 알고 있다.
그리고 문자열 A, B의 각 인덱스가 무슨 문자인지도 알고 있다.
그렇다면 LCS 길이를 구할 때
얻을 수 있는 정보는 무엇이 있을까?
최초로 최대 길이가 될 때의
문자열 A와 문자열 B의 각 인덱스를 얻을 수 있다.
예를 들어, 최대 길이가 4라고 가정해 보자.
최초로 최대 길이가 4가 될 때의
문자열 A의 인덱스와 B의 인덱스 값을 저장해 둔다면,
최대 길이일 때의 마지막 인덱스 값들을 알 수 있다.
이 인덱스 값은 최대 길이 LCS의 마지막 문자가 될 것이다.
이 인덱스와 점화식을 이용해서 LCS를 모두 구할 수 있다.
역추적을 하는 것이다.
역추적
예제 입력으로 있는
ACAYKP
CAPCAK
를 예시로 보겠다.
LCS의 길이를 구하는 과정에서
각각의 dp [0~5][0~5]까지는 값이 다 구해져 있는 상황이다.
출력에서 ACAK가 답이기 때문에
마지막으로 얻어지는 인덱스는 A에서는 4, B에서는 5이다.
이를 각각 i, j로 봐서 dp [i][j]로 보겠다.
여기서 생각해 보는 것이다. dp [4][5]는 어떻게 만들어졌는가?
A [4] == B [5]이기 때문에 두 문자열이 같으므로, 4번째 문자는 K가 된다.
dp [4][5] = dp [3][4] + 1
dp [3][4] = 3이 나오는데, dp [3][4]도 어디서 온 건지 보자
dp [3][4] = MAX(dp [2][4],
dp [3][3])여기서 dp [2][4]와 dp [3][3]은
LCS의 길이를 구하는 과정에서 미리 구해져 있다고 가정했다.
즉, dp [2][4]가 더 크기 때문에 dp [3][4] = dp [2][4]가 된다.
dp [2][4] = 3이고, A [2] == B [4] == A로 같기 때문에 3번째 문자열은 A가 된다.
그다음은 dp [1][3]... 이런 식으로 쭉 쭉 구하다가
dp [i][j] = 0 이 될 때까지 구한다.
이런 식으로 마지막 인덱스를 통해 역추적을 해가면서
올라가면 LCS를 구할 수 있다.
다른 블로그에는 표를 그려서 설명하던데, 나는 그런 방식이 더 이해가 안 갔다.
그래서 그냥 시뮬레이션 돌려보는 방식으로 설명했다.
표 방식이 편한 사람들은 다른 블로그를 참고하셨으면 좋겠다.
이제 문제 구현 단계에서 코드로 구현하겠다.
문제 구현 단계
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int dp[1001][1001];
string A,B;
// LCS 문자열 역추적하여 출력
void print(int x, int y){
if(dp[x][y] == 0) return;
// 두 인덱스의 문자열이 같을 경우
if(A[x-1] == B[y-1]){
print(x-1,y-1);
cout << A[x-1];
}
// 다를 경우
else{
// x - 1 과 y - 1 중 더 긴 것을 재귀함수로 호출
if(dp[x-1][y] > dp[x][y-1]) print(x-1,y);
else print(x,y-1);
}
}
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
cin >> A >> B;
int ans = 0;
int a,b;
// dp 배열 넣기 및 길이 구하기
for(int i = 0; i < A.length(); i++){
for(int j = 0; j < B.length(); j++){
dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1]);
if(A[i] == B[j]){
dp[i+1][j+1]= max(dp[i+1][j+1],dp[i][j]+1);
}
// 최대 길이가 갱신될 때마다 인덱스 a와 b 초기화
if(ans < dp[i+1][j+1]){
ans = dp[i+1][j+1];
a = i+1;
b = j+1;
}
}
}
// 같은게 없으면 0
if(ans == 0) {
cout << "0";
return 0;
}
cout << ans << "\n";
print(a,b);
}print가 역추적을 통해 뒤에서부터 문자를 하나하나씩 출력하는 함수이다.
여기서는 점화식이 좀 다르게 되어있다.
그렇게 된 이유는 dp 배열은 인덱스가 1부터 시작하는데,
문자열은 인덱스가 0부터 시작하다 보니 좀 꼬였다.
시행착오
LCS 길이를 구하는 점화식까지는 구했는데, 역추적을 하는 방법을 몰라서 애를 먹었다.
어찌어찌하긴 했는데 시간초과가 뜨고 해서, 결국엔 인터넷을 참고했다.
점화식을 역추적하는 것은 처음 해봐서 신박하기도 했고
꼭 필요한 지식인 것 같아서 풀어두길 잘 한 문제 같다.
생활비..