•
문제
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
문자열 **"ABDEG"** 와 **"ABECG"** 가 있다고 생각해보자.
이 때, 마지막 G에서의 값을 어떻게 구하는지 생각해보자.
'G'라는 문자가 두 문자열에 모두 공통적으로 들어있기 때문에,
"ABDE"와 "ABEC" 까지의 최장 공통 부분수열 + 1의 값을 해주면 될 것이다.
그렇다면 이제 마지막 G를 빼고 **"ABDE"와 "ABEC"**를 보고 한번 구해보자.
G와 똑같이 구하려고 보니, G와 달리 가장 마지막 문자가 'E'와 'C'로 서로 다르게 된다.
당연한 소리지만 서로 다른 문자이기 때문에 G처럼 이전의 최장 공통 부분수열 + 1로는 계산이
되지 않는다. 이 때는 'E'를 LCS에 포함시켰을 때의 값과, 'C'를 LCS에 포함시켰을 때의 값을
비교해서 더 큰 값을 선택해 주면 된다.
'E'를 선택한 경우 LCS는 "ABE", 'C'를 선택한 경우 LCS는 "AB"가 된다.
C++
복사
풀이
•
기본 알고리즘
1. 두개의 문자열을 한자리씩 비교한다.
2. if s1[i] == s2[j] 비교하는 위치의 문자가 같다면 -> 이전까지의 LCS + 1
3. if s1[i] != s2[j] 비교하는 위치의 문자가 다르다면 ->
max(이전까지의 LCS에 s1을 추가하는 경우, 이전까지의 LCS에 s2를 추가하는 경우)
Python
복사
•
Main 함수
int dp[1001][1001] = { 0 }; // i, j 까지의 문자열의 LCS 저장
int main() {
string s1, s2;
cin >> s1 >> s2;
int s1_len = s1.size();
int s2_len = s2.size();
for (int i = 1; i <= s1_len; i++) {
for (int j = 1; j <= s2_len; j++) {
// 문자가 같은 경우엔 이전까지의 LCS + 1
if (s1[i-1] == s2[j-1]) dp[i][j] = dp[i - 1][j - 1] + 1;
// 문자가 다른 경우엔 max(s1[i] 추가, s2[j] 추가)
else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
cout << dp[s1_len][s2_len];
return 0;
}
C++
복사
