꼬부기의 공대이야기

LCS - BOJ 9251번 본문

Algorithm

LCS - BOJ 9251번

전설의꼬부기 2018. 4. 4. 10:52

안녕하세요! 꼬부기입니다.

이번 문제는 BOJ 9251번 - LCS 입니다.


1. 개요


LCS는 Longest Common Subsequence의 약자로, 해석하면 최장 공통 부분 문자열입니다.

연속적인 부분 문자열인 substring과는 달리 subsequence는 연속적이지 않은 부분 문자열입니다.

익숙한 숫자로 생각을 해보면 다음과 같은 집합이 있다고 가정하겠습니다.


S = {4, 7, 3, 1, 2, 9, 5}


이때, substring은 {4, 7, 3, 1}, {3, 1, 2, 9} 또는 {7, 3, 1, 2, 9, 5}와 같이 연속적인 부분집합입니다.

반면에 subsequence는 {4, 1, 9}, {1, 5}와 같이 흔히 우리가 알고 있던 부분집합과 같은 개념이라고 접근하면 이해하기 편합니다.



2. 문제 풀어보기


DP를 이용해서 해결할 수 있는 문제이다.

문자열 2개는 각각 str1, str2로 표기하겠습니다.


이중 포문을 돌면서 같은 문자를 발견했을 경우, str1과 str2의 바로 이전문자에서 구한 최대 문자열 값 + 1을 하면 된다.

다른 문자를 발견했을 경우에는 str1의 바로 전의 문자에 대한 최대값, str2의 바로 전 문자에 대한 최대값 중 큰 값을 가져온다.


이것을 점화식으로 적으면 다음과 같습니다.

str1을 도는 인덱스가 i, str2를 도는 인덱스가 j라고 했을 때,


if( str1[i] == str2[i] )

    dp[i][j] = dp[i-1][j-1] + 1;

else

    dp[i][j] = max( dp[i-1][j], dp[i][j-1] );


이 식을 기반으로 DP 테이블을 채우면 다음 내용을 알 수 있습니다.

'행은 이전 행의 값을 기반으로 계산된다.'



3. 소스코드


첫번째 코드는 다음과 같습니다.

#include<iostream>
#include<string>
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;

int dp[1001][1001];

int main(void)
{
	string s1,s2;
	cin>>s1>>s2;

	for(int i=1;i<=s1.size();i++){
		for(int j=1;j<=s2.size();j++){
			if(s1[i-1] == s2[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[s1.size()][s2.size()] << endl;

	return 0;
}

이렇게 풀게 되면 dp 테이블인 2차원 배열 [1001][1001]이나 잡아먹게 됩니다.


하지만 이 문제에서 필요한 것은 바로 직전의 dp값만 필요하기 때문에 [2][1001]로 다음과 같이 해결할 수 있습니다.


#include<iostream>
#include<string>
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;

int dp[2][1001];

int main(void)
{
	string s1,s2;
	cin>>s1>>s2;

	for(int i=1;i<=s1.size();i++){
		int idx1 = i&1;
		int idx2 = (i+1)&1;
		for(int j=1;j<=s2.size();j++){
			if(s1[i-1] == s2[j-1]){
				dp[idx1][j] = dp[idx2][j-1]+1;
			}
			else{
				dp[idx1][j] = max(dp[idx2][j],dp[idx1][j-1]);
			}
		}
	}
	cout << dp[s1.size()&1][s2.size()] << endl;

	return 0;
}

지금까지 꼬부기였습니다!

0 Comments
댓글쓰기 폼