백준 9251번: LCS(C++)

www.acmicpc.net/problem/9251

9251번: LCS

코드

#include <iostream>
using namespace std;

string a, b, temp;
int dp[1001][1001] = {0, };

void init(){
	cin >> a >> b;
	if(a.length() > b.length()){
		temp = a;
		a = b;
		b = temp;
	}
}

int max(int a, int b){
	return a > b ? a : b;
}

void solve(){
	for(int i=1; i<=a.length(); i++){
		for(int j=1; j<=b.length(); j++){
			if(a[i-1] == b[j-1]) dp[i][j] = max(dp[i][j-1], dp[i-1][j-1]+1);
			else dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
		}
	}
	cout << dp[a.length()][b.length()];
}


int main(){
	init();
	solve();
}

 

문제 풀이

최장 공통 부분 수열(LCS)문제입니다.

예를들어 A = "ACAYKP" , B = "CAPCAK" 라면 두 문자열의 LCS부분은

ACAYKP

CAPCAK

공통 부분 : ACAK 로 길이는 4가 되므로 정답은 4 입니다.

그렇다면 길이는 어떻게 하면 구할 수 있을까요? 그림을 통해 설명 해 보도록 하겠습니다.

문자열 A = ACAYKP

문자열 B = CAPCAK 입니다.

우선 기본적으로 int DP[ A.length() + 1 ][ B.length() + 1] 크기의 배열을 생성해줍니다.

이 배열에 LCS 길이가 저장 됩니다.

그리고, 각 문자열과 공집합, 즉 아무것도 없는 빈 문자열과 비교해서 LCS 길이를 저장해줍니다.

당연히 빈 문자열은 아무것도 없기 때문에 공통된 부분도 없기 때문에 0으로 초기화가 됩니다.

 

---

1. 문자열 A의 부분 수열 {A} 와 문자열 B의 부분 수열들과 비교.

 

문자열 A의 부분 수열 {A} 와 문자열 B의 부분 수열들과 비교하면 위의 빨간색으로 칠한 부분을 알 수 있습니다. 한 번 해볼까요?

1-1 {A} 와 {C} 의 LCS

{A}와 {C}는 공통 부분이 없습니다. 

그렇기 때문에,

{A}와 {C}에서 문자열 C를 포함하지 않는 부분수열의 LCS (여기서는 Ø이 됩니다.) -> 0

{C}와 {A}에서 문자열 A를 포함하지 않는 부분수열의 LCS (여기서는 Ø이 됩니다.) -> 0

이 둘 중 가장 큰수가 {A} 와 {C} 의 LCS가 됩니다.

점화식으로 나타내어 볼까요?

위 배열의 행의 Index Number를 I, 열의 Index Number를 J라고 해 봅시다.

if (A[I] != B[J]) 
   DP[I][J] = max( DP[I][J-1] , DP[I-1][J])

{A}와 {C}에서 문자열 C를 포함하지 않는 부분수열의 LCS (여기서는 Ø이 됩니다.)

위의 그림에서는 이 색입니다.

{C}와 {A}에서 문자열 A를 포함하지 않는 부분수열의 LCS (여기서는 Ø이 됩니다.) 

위의 그림에서는 이 색입니다.

두 부분 모두 0이므로 DP[i][j] 또한 0이 되겠습니다.

 

그럼 이번에는 두 문자열이 동일한 경우를 봐 보겠습니다. 마침 A[1] 과 B[2]가 동일하네요.

(편의상 설명할때는 A[0], B[0] 을 Ø 으로 가정하고 하겠습니다.)

 

1-2 {A} 와 {AC} 의 LCS

 

여기서는 공통 부분이 있습니다. {A}죠.

{A}와 {CA}에서 문자 A를 포함하지 않는 부분수열의 LCS({C}) 

{A}에서 문자 A를 포함하지 않는 수열 과 {CA}에서 문자 A를 포함하지 않는 수열간의 LCS + 1

(두 문자열 모두 A가 없다가, 생겼을때 공통부분이 된 것이므로 없었던 때의 + 1)

이 둘 중 가장 큰수가 DP[i][j] 의 값이 됩니다.

점화식으로 나타내어 볼까요?

위 배열의 행의 Index Number를 I, 열의 Index Number를 J라고 해 봅시다.

if (A[I] == B[J]) 
   DP[I][J] = max( DP[I-1][J-1] + 1 , DP[I][J-1])

{A}와 {CA}에서 문자 A를 포함하지 않는 부분수열의 LCS({C})

위의 그림에서는 이 색입니다.  0이죠.

{A}에서 문자 A를 포함하지 않는 수열 과 {CA}에서 문자 A를 포함하지 않는 수열간의 LCS + 1

위의 그림에서는 이 색입니다.  0 + 1 돼서 1입니다.

0과 1중 1이 더 크므로 DP[i][j]는 1이 됩니다.

 

자 이렇게해서 문자열이 같은경우 다른경우를 다 봤습니다 그럼 이 점화식을 이용해서 차례대로 배열을 채워나가면 되는데요. 한 줄씩 채워나가보겠습니다.

 

 

이렇게 하면 결국 최종적으로 배열의 끝에 있는 것이 LCS 길이가 됩니다.