LCS

LCS는 Longest Common Subsequence 라는 의미로 최장 공통 부분수열을 구하는 알고리즘이다. ACAYKP CAPCAK 일때 LCS를 하게 되면, 길이는 4가 나오고, ACAK라는 수열을 갖게된다 그냥 동작원리는 다른 블로그에도 잘 나와 있어서 간략하게 쓰려고 한다

	0	A	C	A	Y	K	P
0	0	0	0	0	0	0	0
C	0	0	0	0	0	0	0
A	0	1
P	0	1
C	0	1
A	0	1
K	0	1

일반적으로 위와 같은 상태에서 시작을 한다. 즉 길이가 1인 경우는 일치하는 문자가 나오면, 그뒤에 부분수열은 모두 1이 될것이다

그리고 0인 인덱스를 0으로 채워주는 이유는 나중에 LCS의 문자열을 뽑기 위해서 해주는 것이다.

만약에 LCS의 문자열을 뽑을 필요가 없다면 구지 0을 채우고 시작하는것이아니라 바로, 길이가 1인 경우에 체크를 해주고 시작하면 된다

​이때 동작하는 방식은

1. 문자가 동일한 경우
2. 문자가 동일하지 않은 경우이다

​1번의 경우는 dp[i][j]=max(dp[i-1][j-1]+1,dp[i][j])의 경우로 나타낼수 있고 2번의 경우는 dp[i][j]=max(dp[i-1][j],dp[i][j-1])의 경우로 나타낼수 있다

그래서 위의 경우를 채워보면

	0	A	C	A	Y	K	P
0	0	0	0	0	0	0	0
C	0	0	0	0	0	0	0
A	0	1	1	2	2	2	2
P	0	1	1	2	2	2	3
C	0	1	2	2	2	2	3
A	0	1	2	3	3	3	3
K	0	1	2	3	3	4	4

이런식으로 채워질것이다

그 다음에 역추적을 할때는 끝의 지점에서 시작을 하면서 0을 만나는 순간까지 돌리는데,

LCS의 과정을 반대로 하면서 진행을 해주면 된다

1. 현재 값인 4와 같은 값을 가지는 왼쪽과 위쪽이 있는지를 체크한다. 있다면 그쪽으로 이동을 한다
2. 더이상 1번의 경우로 이동할수없을때, 대각선의 값+1이 현재값과 동일하다면 대각선으로 이동을 한다

2번을 좌표로 표현해보면 현재 위치가 (i,j)일때 대각선은 (i-1,j-1)일것이다

빨간색 지점들을 모으면 결국 정답이 되는 부분들을 이룰수 있을것이다. 그때의 값의 저장은 stack을 이용해도 좋고, vector를 이용해도 좋다

다음의 문제를 풀어볼 수 있다. BOJ LCS 2

by C++

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <iostream>
#include <string>
#include <math.h>
#include <set>
#include <list>
#include <climits>
#include <string.h>
#include <deque>
#include <functional>
#include <stack>
using namespace std;
typedef long long ll;
#define INF 1000000000
typedef pair<int, int> P;
typedef pair<pair<int, int>, pair<int, int>> PP;
typedef pair<int, pair<int, int>> PPP;
int gox[4] = { 0,1,-1,0 };
int goy[4] = { 1,0,0,-1 };
using namespace std;
string s1, s2;
int lcs[1005][1005];
int lcs2[1005][1005];
vector<int> v;
int main() {
	cin >> s1 >> s2;
	if (s1[0] == s2[0]) lcs[0][0] = 1;
	for (int i = 1; i < s1.size(); i++) {
		if (s2[0] == s1[i]) {
			lcs[i][0] = 1;
		}
		else lcs[i][0] = max(lcs[i][0], lcs[i - 1][0]);
	}
	for (int i = 1; i < s2.size(); i++) {
		if (s2[i] == s1[0]) lcs[0][i] = 1;
		else lcs[0][i] = max(lcs[0][i], lcs[0][i - 1]);
	}
	int Max = 0;
	for (int i = 1; i < s1.size(); i++) {
		for (int j = 1; j < s2.size(); j++) {
			if (s1[i] == s2[j]) lcs[i][j] = max(lcs[i - 1][j - 1] + 1, lcs[i][j]);
			else lcs[i][j] = max(lcs[i][j], max(lcs[i - 1][j], lcs[i][j - 1]));
		}
	}

	for (int i = 0; i < s1.size(); i++) {
		for (int j = 0; j < s2.size(); j++) {
			lcs2[i + 1][j + 1] = lcs[i][j]; // 0인 지점을 종료로 만들기 위해서 기존의 값을 x좌표로 한칸, y좌표로 한칸 이동했다
		}
	}
	int ex = s1.size(), ey = s2.size();
	while (lcs2[ex][ey] != 0) {  //LCS를 추적하는 부분
		if (lcs2[ex - 1][ey] == lcs2[ex][ey]) {
			ex--;
		}
		else if (lcs2[ex][ey - 1] == lcs2[ex][ey]) {
			ey--;
		}
		else if (lcs2[ex - 1][ey - 1] + 1 == lcs2[ex][ey]) {
			v.push_back(ex);
			ex--, ey--;
		}
	}
	reverse(v.begin(), v.end()); // 벡터로 했기 때문에 reverse를 해줬음
	printf("%d\n", lcs[s1.size() - 1][s2.size() - 1]);
	for (int i = 0; i < v.size(); i++) {
		printf("%c", s1[v[i] - 1]);
	}
	return 0;
}

관련 문제 : https://www.acmicpc.net/problem/5582

이 문제는 연속적인 공통 부분을 만들어야 하기때문에 저기 위에 있는 lcs의 점화식에서

문자가 다를때는 옆이나 위의 최대값을 이뤄줘야하는 점화식이 있었습니다. 그 점화식의 경우를 빼주면 됩니다 -> dp[i][j]=max(dp[i-1][j],dp[i][j-1]) (단 s1[i]!=s2[j])

출처: https://www.crocus.co.kr/787
좋은 공부가 되었습니다 감사합니다^^

궁금하신 사항이 있으시면 댓글을 달아주시면 감사하겠습니다^^
잘못 된점 이 있다면 댓글 남겨주시면 감사드리겠습니다