[알고리즘] LCS(Longest Common Subsequence)

시작부터 웬 다이나믹 프로그래밍...(동공지진)

뭔가 처음엔 제일 자신있는걸 하고싶었다.

내가 이 과제 했을때 얼마나 고생을 했던지......

그래서 방학때 날잡아서 LCS 관련 문제를 전부 풀어봤었다 하하

자 먼저, 우리 Longest Common Subsequence에 대한 문제를 풀어보기 전에

- 다이나믹 프로그래밍 이란?

 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법

수업 들을 당시에 교수님께서는 

'크기가 N-1인것을 어떻게 푸는지 알려주면 크기가 N인것도 풀어줄게'

라는게 동적계획법, 다이나믹 프로그래밍이라고 하셨다.

뭐, LCS는 다이나믹 프로그래밍중에서도 아주...아주 기초중의 기초

일단 본격적으로 Longest Common Subsequence를 보기 전에,

Longest Common Substring 부터 알아보도록 하쟈

1. Longest Common Substring (최장 길이 공통 부분 문자열)

최장 길이 공통 부분 문자열은 말 그대로, 두 문자열 사이에 공통되는 문자열의 최대길이가 얼마냐?

를 묻는 문제이다.

>예를들어,

String A = "abcdabcd";
String B = "efcdagh";

라고 하면, A와 B의 Longest Common Substring은 "cda", 길이가 3인 문자열이 된다.

점화식은, A의 길이 = N, B의 길이 M이라 할때 N*M의 2차원배열 arr에서

와 같은 식으로 2차원 배열을 채워주면 된다.

그리고 우리가 구하고 싶은 LongestCommonSubstring은 arr에 저장된 값 들 중에 가장 큰 값이 된다.

위에서 예를 들었던, "abcdabcd"와 "efbcdgh"로 실행시켜보면

이런식으로 나타난다. 그러므로 정답은 배열의 값들중의 최댓값, 3이 된다.

혹시 코드는....구현이 너무 쉬워서..... 필요없을거 같지만....

코드는....

#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;

int max_num(int a, int b){
	if(a>=b) return a;
	else return b;
}
int main(){
	string A, B;
	cin>>A>>B;

	int **arr = new int*[A.length()+1]();
	for(int i=0;i<=A.length();i++){
		arr[i] = new int[B.length()+1]();
	}
	int result = 0;
	for(int i=1;i<=A.length();i++){
		for(int j=1;j<=B.length();j++){
			if(A[i-1]==B[j-1]){
				arr[i][j] = arr[i-1][j-1]+1;
				result = max_num(arr[i][j], result);
			}
			else{
				arr[i][j] = 0;
			}
		}
	}
		for(int i=0;i<=A.length();i++){
		for(int j=0;j<=B.length();j++){
			cout<<arr[i][j]<<" ";
		}
		cout<<endl;
	}
	printf("%d\n", result);
}

2. Longest Common Subsequence(최장 공통 부분열)

Substring이 연속되는 부분문자열이였다면, Subsequence는 연속되지 않는다. 순서만 보면 된다.

Helloworld 에서 hello, world, llowo 등은 연속되므로 Substring이라고 할 수 있다.

그러나, elol, llwd, oord 등은 연속되지 않지만, Helloworld내에서 순서대로 배열되어있으므로 Subsequence라 할 수 있다.

다시 말해, Substring은 Subsequence이지만 Subsequence는 Substring이 아니다...!!!!

예를들면, "ACAYKP"라는 문자열과 "CAPCAK"라는 문자열이 있다. 이 두 문자열의 LCS는 "ACAK"가 된다.

LCS같은 경우는 문자열이 길어지면 눈으로는 찾기가 힘든데 컴퓨터는 기똥차게 찾아준다><

LCS의 점화식은, A의 길이를 N, B의 길이를 M이라 할때 N X M 2차원 배열 arr에 대하여

Longest Common Substring과 똑같지만, A[i-1]과 B[j-1]이 다를 경우가 약간 다르다. 

왼쪽, 혹은 위의 값 중에 큰 값이 arr[i][j]의 값이 된다.

LCS 같은 경우는 테이블을 다 채운 후에 arr[N-1][M-1]의 값이 답이 된다.

위에서 예로 들었던 "ACAYKP", "CAPCAK"에 대해서 LCS를 찾아보면

답은 4가 나온다.

근데 그렇다면, 만약 LCS의 길이가 얼마냐? 를 묻는 문제가 아니라 LCS가 무엇인지 출력하라는 문제가 나온다면???

테이블을 자세히 관찰해보면 저 답을 찾을 수 있다.

arr[N-1][M-1]부터 타고 올라가는데, 그 값이 대각선 위에서 왔는지, 왼쪽에서 왔는지, 위에서 왔는지만 체크해주면 된다.

타고 올라가면서 값이 대각선 위에서 왔다면 그 자리가 바로 빨간 동그라미 친 자리 즉, LCS의 부분이 된다.

그러므로, CAPCAK에서 빨간 동그라미 쳐진 부분이 (맨 앞 0 빼고) 2, 4, 5, 6번째이므로

LCS는 ACAK가 된다.

ACAYKP에 대해서도 마찬가지로 구할 수 있다.

이 값은 arr을 채우는 과정에서, 이 값이 왼쪽, 위, 가운데 위 중에 어디서 왔느냐를 체크해준 후 타고 올라가면 된다!

코드로 나타내면

#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;

int max_num(int a, int b){
	if(a>=b) return a;
	else return b;
}
enum{
	LEFT = -1,
	UP = 1,
	CROSS = 0
};
int main(){
	
	string A, B;
	cin>>A>>B;

	int **arr = new int*[A.length()+1]();
	int **s_arr = new int*[A.length()+1]();
	for(int i=0;i<=A.length();i++){
		arr[i] = new int[B.length()+1]();
		s_arr[i] = new int[B.length()+1]();
	}
	int result = 0;
	for(int i=1;i<=A.length();i++){
		for(int j=1;j<=B.length();j++){
			if(A[i-1]==B[j-1]){
				arr[i][j] = arr[i-1][j-1]+1;
				s_arr[i][j] = CROSS;
			}
			else{
				arr[i][j] = max_num(arr[i-1][j], arr[i][j-1]);
				if(arr[i][j]==arr[i-1][j]) s_arr[i][j] = LEFT;
				else s_arr[i][j] = UP;
			}
		}
	}
	int k = A.length();
	int l = B.length();
	string answer="";
	while(arr[k][l]!=0){
		switch(s_arr[k][l]){
		case UP:
			{
				l--;
				break;
			}
		case CROSS:
			{
				answer = A[k-1]+answer;
				k--; l--;
				break;
			}
		case LEFT:
			{
				k--;
				break;
			}
		}
	}
	for(int i=0;i<=A.length();i++){
		for(int j=0;j<=B.length();j++){
			cout<<arr[i][j]<<" ";
		}
		cout<<endl;
	}
	printf("%d\n", arr[A.length()][B.length()]);
	cout<<answer<<endl;

ㅎㅎㅎ.....

문자열이 세개인 경우도 마찬가지다

세 문자열의 i번째, j번째, k번째 값이 모두 같을때 대각선 위의 값에 +1을 해주는 식으로 테이블을 채워나가면 된다.

#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;

int max_num(int a, int b){
	if(a<=b) return a;
	else return b;
}
int main(){
	string A, B, C;
	cin>>A>>B>>C;

	int ***arr = new int**[A.length()+1]();
	for(int i=0;i<=A.length();i++){
		arr[i] = new int*[B.length()+1]();
		for(int j=0;j<=B.length();j++){
			arr[i][j] = new int[C.length()+1]();
		}
	}

	for(int i=1;i<=A.length();i++){
		for(int j=1;j<=B.length();j++){
			for(int k=1;k<=C.length();k++){
				if(A[i-1]==B[j-1] && B[j-1]==C[k-1]){
					arr[i][j][k] = arr[i-1][j-1][k-1]+1;
				}
				else{
					int max = max_num(arr[i-1][j][k], arr[i][j-1][k]);
					arr[i][j][k] = max_num(max, arr[i][j][k-1]);
				}
			}
		}
	}
	
	printf("%d\n", arr[A.length()][B.length()][C.length()]);
}

요런식으로 똑같이 채워주면 된다!!!

LCS는 사실 여러가지가 나올 수 있다.

예를들면, TTTAAA라는 문자열과

AATATT라는 문자열의 LCS는 "AAA"가 될수도 있고, "TTT"가 될 수도 있다.

만약 문제에서 LCS중 사전순으로 가장 빠른것을 찾으라 하면???

ㅎㅎ...

두가지 방법이 있을수 있다.

1. 백트랙킹

2. 스트링 테이블 만들기

두가지 다 시도해봤는데 ..... 아니 물론 이 외에 더 있을수 있지만

내가 생각나는건 요거 두가지 정도....

백트랙킹은 시도해봤지만...문자열이 조금만 길어져도 시간이 엄청나게 오래 걸리게 된다.

그래서 스트링으로 테이블을 만들어보았다...!!

스트링 테이블을 arr과 같은 크기로 만든다. s_arr이라고 하면,

이런식으로 테이블을 채워줄수있다...!!

Front 함수는 여기서 사전적으로 더 빠른것을 찾아주는 함수이다. 사실 스트링 비교도 < >으로 가능하기 때문에 Max와 같이 구현할 수 있다.

약간 문제가 다른 코드긴 하지만, 과제때 실제로 구현했던 코드는

	
for(int i=1;i<first_len;i++){
	for(int j=1;j<second_len;j++){
		if(first[i-1]==second[j-1]){
			max_gene[i][j]=max_gene[i-1][j-1]+1;
			max_string[i][j]=max_string[i-1][j-1]+first[i-1];
		}
		else{
			if(max_gene[i-1][j]>max_gene[i][j-1]){
				max_string[i][j]=max_string[i-1][j];
				max_gene[i][j] = max_gene[i-1][j];
			}
			else if(max_gene[i-1][j]<max_gene[i][j-1]){
				max_string[i][j]=max_string[i][j-1];
				max_gene[i][j]= max_gene[i][j-1];
			}
			else if(max_gene[i-1][j]==max_gene[i][j-1]){
				max_gene[i][j] = max_gene[i-1][j];
				if(max_string[i-1][j]==""){
					max_string[i][j]=max_string[i][j-1];
				}
				else if(max_string[i][j-1]==""){
					max_string[i][j]=max_string[i-1][j];
				}
				else{
					max_string[i][j]=max_string[i-1][j]<max_string[i][j-1]?max_string[i-1][j]:max_string[i][j-1];
				}
				
			}
		}
	}

와 같이 구현해주면 된다...^^

이 코드에서 max_gene은 LCS의 길이 값을 구해주는 것이고

max_string이 위에서 언급한 스트링 배열이다.

저렇게 계산 된 결과로 max_string[N-1][M-1] 을 출력해주면

그 값이 Longest Common Subsequence가 된다.

LCS를 할 줄 안다고 해서 다이나믹 프로그래밍을 잘하는건 아니다

확실하게 알고리즘을 하다보면 DP는 흥미있는 분야이다. 

재...재밌지만 너무 어려워ㅠㅠㅋㅋㅋㅋㅋ

다음번엔 더 많은 DP 문제 풀어보고 이해해봐야징