1ilsang

Developer who will be a Legend

최장 공통 부분수열(LCS) 알고리즘 알아보기

2019-11-13 1ilsangData-Structure & Algorithm

최장 공통 부분수열(LCS)는 두 문자열의 가장 긴 공동 부분 문자열을 찾는 알고리즘이다.

말로는 조금 애매하니 문자열로 표시하면 아래와 같다.

String a = "abcdeeabeesefeed";
String b = "abceacdfedd";

LCS = "abceafed";

문자열 a와 b를 비교해보면 abceafed가 가장 긴 공통 부분수열이 됨을 알 수 있다.

접근 방법은 dp 테이블을 채우면서 두 문자열이 같다면 왼쪽 대각선 값에 1을 더해주고(왼쪽 대각선인 이유는 지금 비교하는 문자열을 각자 뺀 곳이 왼쪽 대각선이기 때문) 아니라면 위쪽과 왼쪽 중에서 더 큰 값을 자신으로 하면 된다.(지금까지의 최대 개수)

int go(String a, String b) {
	int aLen = a.length();
	int bLen = b.length();
	int[][] memo = new int[aLen + 1][bLen + 1];
	
	for(int i = 1; i <= aLen; i++) {
		for(int j = 1; j <= bLen; j++) {
			if(a.charAt(i - 1) == b.charAt(j - 1)) memo[i][j] = 1 + memo[i - 1][j - 1];
			else memo[i][j] = Math.max(memo[i - 1][j], memo[i][j - 1]);
		}
	}

	return memo[aLen][bLen];
}

dp table image

그렇다면 위의 예에서 가장 긴 부분 수열인 ABD를 출력해보자. DP 테이블을 그대로 역순하면 된다. 제일 마지막 i, j 에서 값이 같다면 대각선 왼쪽으로 이동하고 아니라면 위와 왼쪽 중 더 큰 값으로 이동하면 된다.

	...

	int i = aLen;
	int j = bLen;

	Stack<Character> stack = new Stack<>();

	while(i > 0 && j > 0) {
		if(a.charAt(i - 1) == b.charAt(j - 1)) {
			stack.push(a.charAt(i - 1));
			i--;
			j--;
			continue;
		}
		if(memo[i][j - 1] > memo[i - 1][j]) j--;
		else i--;
	}

	String answer = "";
	while(!stack.isEmpty()) {
		answer += stack.pop();
	}
	
	return answer;

코드를 보면서 테이블이 어떻게 채워지는지 확인하면 쉽게 풀 수 있는 문제다. 역시 디피는 알고나면 쉽지만 점화식이나 방식을 떠올리기가 어려운것 같다.

그럼 이만!