문제
풀이
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
Longest Common Substring = 최장 공통 부분 문자열, Longest Common Subsequence = 최장 공통 부분 수열가 있는데, “ABDFE”와 “ABDEF”가 있을 때,
Longest Common Substring = “BD”, Longest Common Subsequence = “BDE”라고 한다. 이는 Substring은 연속되어 있는 공통된 문자열을 의미하고 Sequence는 연속하지 않은 부분수열 중 공통된
부분을 포함시킨다. (참조
LCS 알고리즘은 처음 접하는 것으로 알아두면 매우 좋을 것 같다. 두 개의 비교 문자열을 행과 열로 위치하여, 하나하나씩 비교해가며 같은 문자열이 나타났을 땐, 그 전까지 비교한 LCS에 공통 문자열을 +1하여 표를 채우고,
다른 문자열이 나타났을 땐, 비교하는 A와 B문자열을 각각 넣었을 때 LCS가 최대가 되는 것으로 표를 채운다. 이는 행과 열에서 채우려고 하는 칸에서 왼쪽과 위쪽이 될 것이며, 이 중 큰 것을 넣으면 된다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
int main(){
string st1, st2;
cin >> st1 >> st2;
int dp[1001][1001] = {0};
for(int i = 1; i<=st1.size(); i++){
for(int j = 1; j<=st2.size(); j++){
if(st1[i-1] == st2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
}
}
printf("%d\n", dp[st1.size()][st2.size()]);
}
