LCS - 🥇 Gold 5
LCS는 Longest Common Subsequence로, 최장 공통 부분 수열이다. 어떠한 문자열이 주어졌을 때, 해당 문자를 이루고 있는 문자들로 부분 수열을 만들 수 있다.
ex) abc
a,b,c,ab,ac,bc,abc
두 문자열이 주어졌을 때, 각 문자열의 부분 수열들 중에 동일한 부분 수열의 최장 길이를 구하는 문제가 LCS다.
처음에 문제를 접하였을때는 두 문자열에 대해서 순회하면서 비교하면 가능할 것이라 생각하였지만, 이 방식으로 풀지 못하는 case가 너무나도 많았고, 잘못된 접근법이었다.
이 문제는 2차원 배열 DP를 이용하면 쉽고 간단하게 풀이가 가능했다. 각 문자열을 길이가 0일때부터 비교하며, 해당 자리까지 순서가 일치하며 공통되는 문자의 개수를 저장하는 것이다.
test case로 주어진 경우를 살펴보겠다.
우선 각 문자열을 NULL과 비교하는 경우에는 공통된 문자가 0개이므로 전부 0으로 처리해준다.
그리고 문자열을 순회하며 각 문자열까지에 대해 다음을 반복한다.
문자가 서로 같다면
- 해당 지점의
[ i - 1 ][ j - 1 ]지점의 값에서+1을 저장
문자가 서로 같지 않다면- 해당 지점에서
[ i ][ j - 1 ],[ i - 1 ][ j ]중에서의 최댓값을 저장
이를 반복하면 문자열의 길이에 해당하는 가장 마지막 지점에 적혀있는 숫자가 LCS의 길이가 된다.
해당 점화식을 바탕으로 코드를 작성하면 아래와 같다.
풀이 코드
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
string s1, s2;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// 입력값 입력받음
cin >> s1 >> s2;
// 2차원 배열 DP를 위한 vector 초기화
vector<vector<int>> LCS(s1.length() + 1, vector<int>(s2.length() + 1, 0));
// 문자열을 탐색하며 점화식을 반복
for (int i = 1; i <= s1.length(); i++) {
for (int j = 1; j <= s2.length(); j++) {
if (s1[i - 1] == s2[j - 1]) {
LCS[i][j] = LCS[i - 1][j - 1] + 1;
}
else {
LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1]);
}
}
}
// 결과 출력
cout << LCS[s1.length()][s2.length()] << "\n";
return 0;
}결과
festina lenta