[Algorithm] LCS(Longest Common Subsequence)

 

LCS(Longest Common Subsequence)는 문자열 A,B가 있을 시, 가장 길이가 긴 공통 부분 문자열을 찾는 알고리즘입니다. 여기서 부분 문자열이라는 것은 연속된 문자열이 아닌 부분 문자열을 뜻합니다.

 

예로들어, 'HAYOUNG'과 'AONG'이라는 문자열이 있을 시, 공통된 부분문자열은, {A}, {A,O}, {A,N}, {A,G}, .. ,{A,O.N,G} 가 있죠. 그리고 여기서 가장 긴 부분 문자열은 'AONG'입니다.

 

LCS를 푸는 알고리즘은 Dynamic Programming을 이용하며 O(mn), (m = len(A), n = len(B)) 의 시간복잡도를 가지고 해결할 수 있습니다. 푸는 절차는 다음과 같습니다.

 

 

먼저, Dynamic Programming을 적용하기 위해 다음과 같은 정보를 저장합니다.

 

dp[i, j] = A[0, i]와 B[0, j]에 해당하는 부분문자열 중 가장 길이가 긴 공통 부분 문자열의 길이

 

그리고 알고리즘의 동작과정은 다음과 같습니다.

 

 

먼저, 계산의 편의를 위해 A문자열에 B문자열을 비교하는 것을 가정하고 시작합니다. 그리고 B의 첫번째 문자부터 계산하는 것이 아닌 문자 자체를 비교하지 않는 다는 것을 전제로 그 비교값을 0으로 초기화시킵니다.

 

다음 B의 문자열의 문자들을 하나씩 더해가며 만일 A와 일치하는 부분이 있다면 그 부분에 1을 더해주고 일치하지 않는 경우라면 그 전에 계산한 값들 중( i, j 라면 i-1, j or i, j-1) 가장 큰 값을 대입합니다. 즉, 왼쪽 혹은 위쪽 중 가장 큰 값을 대입하는 것이죠. 

 

 

최종적으로 위와 같은 표가 됩니다. 프로그램 상에서는 2차원 배열의 최종 상태가 되겠죠. 맨 오른쪽 아래값을 반환하면 LCS 문제의 정답을 구하는 것이 됩니다. 

 

위 알고리즘에서 적용된 규칙은 다음과 같습니다.

 

1. i == 0 or j == 0, dp[i][j] = 0

2. A[i] = B[j], dp[i-1][j-1] + 1

3. A[i] != B[j], Max(dp[i][j-1], dp[i-1][j])

 

아래의 코드는 LCS를 구현한 C++코드입니다.

 

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main(void)
{
	int len_a, len_b;
	string A, B;
	cin >> len_a >> len_b;
	cin >> A >> B;

	int dp[100][100];
	memset(dp, 0, sizeof(dp));

	for (int i = 1; i <= len_b; ++i) {
		for (int j = 1; j <= len_a; ++j) {
			if (B[i] == A[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
			else dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
		}
	}

	cout << dp[len_b][len_a] << endl;
}

출처: https://engkimbs.tistory.com/359?category=688855 [새로비]