LCS
문제: LCS (백준 9251번)
구조 분석
처음 LCS를 들어봤다면 매우 생소한 문제일 것이다. LCS가 무엇인지부터 알아봐야 한다.
1. LCS(Longest Common Substring, 최대 공통 부분 문자열)
-연속하는 공통 부분 찾기
-ACAYKP
-CAPCAK
결과: CA
2. LCS(Longest Common Subsequence, 최장 공통 부분 수열)
-공통 부분 찾기
-ACAYKP
-CAPCAK
결과: ACAK
우선 위의 LCS 개념을 알고 있어야 문제를 풀 수 있다.
위의 두가지 문제 모두 점화식을 이용하여 구성할 수 있다. 그리고 점화식을 이용한다는 것은 dynamic programming을 적용할 수 있다는 것이며 dp table을 이용하여 문제를 풀 수 있다.
풀이 방법
우선 두가지 LCS 문제에 대해 풀이 방법을 정리해봤다.
"Longest Common Substring 길이 구하기" 풀이법
0. dp table을 생성한다. 이떄, 2개의 문자열을 비교하기 위해 2차원 배열을 생성한다.
1. str1, str2를 한글자씩 비교한다.
2. 두 문자가 다르다면 dp[i][j] = 0
3. 두 문자가 같다면 dp[i][j] = dp[i-1][j-1] + 1
4. 위 과정을 반복한다.
5. (테이블의 최댓값) = (LCS의 길이)
Longest Common Substring은 연속되는 공통 문자열을 찾는 과정이므로 위와 같은 알고리즘을 따른다.
"Longest Common Subsequence 길이 구하기" 풀이법
0. dp table을 생성한다. 이때 2개의 문자열을 비교하기 위해 2차원 배열을 생성한다.
1. str1, str2를 한글자씩 비교한다.
2. 두 문자가 다르다면 dp[i][j] = MAX(dp[i-1][j], dp[i][j-1])
3. 두 문자가 같다면 dp[i][j] = dp[i-1][j-1] + 1
4. 위 과정을 반복
5. (테이블의 마지막값) = (LCS의 길이)
Longest Common Subsequence는 연속되는 것을 찾는 것이 아니기 때문에 이전의 LCS는 계속해서 유지한다. 따라서 두 문자가 다른 경우 MAX(dp[i-1][j], dp[i][j-1])를 저장하게 되는 것이다.
코드
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string>
#define MAX(a,b) (((a)>(b))?a:b)
using namespace std;
int dp[1001][1001] = {0,};
int main() {
string str1;
string str2;
cin >> str1 >> str2;
int len1 = str1.length();
int len2 = str2.length();
for (int i=1; i<=len1; i++) {
for (int j=1; j<=len2; j++) {
if (str1[i-1] == str2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
}
else {
dp[i][j] = MAX(dp[i-1][j], dp[i][j-1]);
}
}
}
cout << dp[len1][len2] << "\n";
return 0;
}
정리
우선 LCS의 개념을 모르면 풀 수 없는 문제이다. 또한 이전까지의 기본형태의 dynamic programming과 달리 2차원 배열을 이용한 문제이므로 이러한 유형에도 익숙해져야한다. 마지막으로 점화식 논리로 풀 수 있는 문제는 dynamic programming이 적용된다는 것을 알아두자.
댓글남기기