LCS - BOJ 9251번

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

이번 문제는 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;
}

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