[Java]최장 공통 부분 수열(LCS, Longest Common Subsequence)

*최장 공통 부분 수열(LCS, Longest Common Subsequence)

->최장 공통 부분 수열이란, 주어진 두 수열이 주어졌을 때 두 수열 모두의 부분 수열이 되는 수열 중 가장 긴 것을 말한다.

->LCS를 구하는 문제는 역시 백준 Gold5 9251 LCS 문제를 기반으로 알고리즘을 설명하도록 하겠다.

※ 문제 주소 : https://www.acmicpc.net/problem/9251

9251번: LCS

->해당 테스트 케이스를 바탕으로 LCS를 이해하면 다음과 같다. 아래 그림을 참고하자.

두 수열의 부분 수열 중 공통 되는 부분 수열의 길이가 가장 긴 것.

 

*동적 계획법을 활용한 풀이

->Knapsack Problem, LIS와 마찬가지로 해당 블로그에 포스팅한 '동적 계획법 접근 방식'을 바탕으로 문제를 해결하겠다.

※ 참고 : https://sskl660.tistory.com/87

[Java]동적 계획법(Dynamic Programming)

 

1. 문제를 특정한 부분 문제로 생각해보고, 해당 문제를 저장할 dp 테이블을 정의해본다.

(1) 각 문자열이 비교되는 위치에서 가질 수 있는 LCS의 최대 값은 무엇일까?

->LCS 문제 풀이의 기본적인 접근은 위 질문으로부터 시작된다. 주어진 테스트 케이스를 예로 들면, 다음과 같은 느낌을 갖는 다는 것을 이해해보자.

 

(2) 해당 위치에서 가질 수 있는 LCS의 최대 값을 효과적으로 저장하기 위해, 2차원 배열을 활용하여 값을 저장한다.

->각 문자열이 비교되는 위치에서 가질 수 있는 LCS의 최대 값을 저장한다는 말이 잘 이해되지 않을 것이다. 우선 결론적으로 LCS 문제 해결은 아래 2차원 배열 형태의 dp 테이블을 활용하게 될 것이다. 아래 그림을 참고한다면 조금 더 이해하기 좋을 것이다.

 

(3) 우선 값을 채워보자

->우선, 첫 번째 문자열에 대하여 두 번째 문자열의 문자를 하나씩 비교하며 테이블을 갱신해보자. 그렇다면 두 번째 문자열의 첫 번째 문자인 'C'와 첫 번째 문자열을 비교하게 될 것이다.

 우선 C를 A와 비교한다면 두 문자가 일치하지 않기 때문에, LCS의 값은 1이 된다는 것을 알 수 있다.

 두 번째로 C를 C와 비교한다면 두 문자는 일치하므로, 해당 위치에서 가질 수 있는 LCS의 값은 1이 된다는 것을 알 수 있다.

 세 번째로 C와 A를 비교하면 두 문자는 일치하지 않는다. 그렇다면 해당 위치에 0을 채워야 할까? dp 테이블의 정의를 다시 살펴보자. 해당 위치의 의미는 두번째 문자열의 첫 문자인 'C'가 첫 번째 문자열의 첫 번째 문자와 두 번째 문자의 비교를 끝내고 세 번째 문자인 'A'와 비교하는 위치이다. 또한, 그 위치에 지금까지 C가 해당 위치에서 가질 수 있는 최대 LCS의 값을 저장해야 한다고 하였다. 따라서, 이전 문자에서 비교했던 최대 값인 1을 그대로 해당 위치에 가져와야함을 알 수 있다.

 마찬가지 방식으로 나머지 테이블도 채울 수 있다.

 여기서 주의해야 할 점은 첫 번째 문자열과 두 번째 문자열 모두 상호적으로 해당 위치의 의미는 각 문자열이 비교되는 위치에서 가질 수 있는 LCS의 최대 값을 의미한다는 것이다. 우선 나머지 테이블도 채워보도록 하자.

->자, 그럼 이번에는 두 번째 문자열의 두 번째 문자열인 'A'에 대하여 첫 번째 문자열의 모든 문자열을 비교해보도록 하자.

 우선 처음부터 A와 A를 비교하므로 문자가 일치한다. 그렇다면 당연히 해당 위치에 적어도 1이라는 값을 가지게 될 것임을 알 수 있다. 그렇다고 무작정 규칙을 생각하지 않으면서 그 값을 넣으면 안된다는 것을 지금까지 여러 다이나믹 프로그래밍 문제를 풀면서 경험적으로 알게 되었다.

 그렇다면 이전 문자열의 비교에서 사용된 것 처럼, 이전에 구했던 최대 값을 전이 시키면 되지 않을까? 하지만 0이라는 값을 전이 시키면 해당 위치에는 0이라는 값이 들어갈 것이다. 아직은 정보가 부족하다. 우선 테이블을 채우는 과정을 계속 진행해보자.

 우선 두 번째 문자열의 첫 번째 문자인 'C'를 첫 번째 문자열과 비교하며 채워나갔던 것처럼, A와 C는 문자가 서로 일치하지 않으므로 그 값을 전이시켜 두 번째 열을 채웠다.

 그렇다면 세번째 열에서도 1을 채워야 하는가? 일단 첫 번째 경우와 다른점은 세 번째 위치에서 A와 A로 문자열이 서로 일치한다는 것이다. 그렇지만, 두 번째 문자열에 현재 위치까지 보유한 A라는 문자는 단 하나 뿐이고, 무턱대고 해당 위치를 + 1해버린다면 두 번째 문자열의 2번째 위치까지 A라는 문자가 두 개라는 것을 의미하게 된다. 

 또 다른 정보는, 우선 직관적으로 해당 위치에서 각 문자열의 "CA"라는 부분이 공통적을 도출된다는 것을 알 수 있다. 따라서 해당 위치는 최소 2의 값을 가져야 함도 알 수 있다.

 자, 여기서 규칙성을 파악해보자. 테이블의 행을 i, 열을 j라고 한다면 해당 위치의 위(i - 1), 왼쪽(j - 1), 왼쪽 위 대각선 (i - 1, j - 1)방향의 정보를 참고할 수 있고 결론적으로 해당 정보들을 바탕으로 현재 위치의 값들을 갱신하게 된다. 그렇다면 각 위치의 정보가 의미하는 바를 분석해보자.

 

(4) 윗 행(i - 1)의 값이 의미하는 정보

->해당 위치의 바로 윗 행이 의미하는 정보는 두 번째 문자열의 'C'가 해당 위치에서 첫 번째 문자열의 'A'까지 비교하면서 얻은 최대 LCS의 값을 의미한다.

(5) 왼쪽 열(j - 1)의 값이 의미하는 정보

->해당 위치의 바로 왼쪽 열이 의미하는 정보는 첫 번째 문자열의 두 번째 문자인 'C'가 해당 위치에서 두 번째 문자열의 'A'까지 비교하면서 얻은 최대 LCS의 값을 의미한다.

(6) 윗 행(i - 1), 왼쪽 열(j - 1)의 값이 의미하는 정보

->해당 위치의 윗 행, 왼쪽 열이 의미하는 정보는 현재 문자에 대하여 각 이전 문자열의 이전 문자가 해당 위치에서 가질 수 있는 최대 LCS의 값을 의미한다.

(7) 4, 5, 6에서 얻은 정보를 종합해보자.

->우선 우리는 앞서 테이블을 채우는 과정에서 경험적으로 해당 위치의 문자가 같거나, 다르다면 처리를 다르게 해주어야 될 것 같다는 사실을 유추해볼 수 있었다. 이제 그 정보와 앞서 얻은 정보를 결합해 볼 차례이다.

 

※ 해당 위치의 문자가 일치하는 경우.

 앞서 언급한 바와 같이, 해당 문자의 대각선에 위치한 값의 의미는 각 이전 문자열의 이전 문자가 해당 위치에서 가질 수 있는 최대 LCS의 값이라고 하였다. 즉, 현재 문자가 일치한다면 각 문자가 추가되는 위치에서 LCS의 값을 증가시킬 가능성이 존재한다는 것을 의미한다. 따라서 해당 값에 + 1을 하여 해당 테이블을 갱신할 수 있다.

 

※ 해당 위치의 문자가 일치하지 않는 경우.

->다음 테이블을 채워보자. 이번에는 A와 Y라는 문자가 일치하지 않기 때문에, 대각선 정보는 활용할 수 없다.

 일치하지 않기 때문에, 이제 남은 윗 행 정보와 왼쪽 열의 정보를 활용해야 한다는 사실을 알 수 있다. 그리고 그 정의 그대로, 각 첫 번째 문자열과 두 번째 문자열이 지금까지 조사한 최대 LIS의 값 중 더 큰 값을 갖는 것을 선택해야 한다는 것을 유추해볼 수 있다.

 따라서 이때는 좌측의 값이 더 크기 때문에, 좌측의 값을 해당 테이블에 갱신해주는 것이다.

 

2. 부분 문제의 관계를 생각하며 점화식을 도출한다.

->즉, 해당 위치의 문자가 일치하느냐의 여부에 따라서 다른 점화식을 적용하여 해당 위치의 값을 갱신해야 된다는 것을 이해할 수 있다. 따라서 다음과 같은 점화식을 도출할 수 있을 것이다.

3. 점화식을 바탕으로 dp 테이블을 갱신하면서 최종적으로 전체 문제를 해결한다.

->우선 해당 점화식을 진행하기 위해서는 서로 문자가 없는 상태에서 시작하는 경우도 고려(기저 조건)해야 하기 때문에 기존 배열에 패딩을 추가하여 0으로 초기화 해줘야 한다는 사실을 알 수 있다(문자가 없는 경우 비교를 수행해도 일치하는 문자는 없기 때문에 0).

 이렇게 각 테이블을 채우고 dp[B문자열의길이][A문자열의길이]가 의미하는 것은 B문자열의 K라는 문자가 A문자열의 P라는 문자까지 비교하며 얻은 최대 LCS의 값을 의미하게 된다. 따라서 해당 값을 출력하면 된다.

 

4. 구현

->위의 규칙을 그대로 코드로 옮기면 된다. 아래 코드를 참고하자.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class LCS {
	static char[] A, B;
	static int[][] dp;
	static int max = 0;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		// 각 문자열을 입력 받는다.
		String a = br.readLine();
		String b = br.readLine();
		// 각 문자열의 길이가 다르므로 따로 저장해둔다.
		int alength = a.length();
		int blength = b.length();
		// 각 문자열을 나눠서 저장할 char 배열.
		A = new char[alength + 1];
		B = new char[blength + 1];
		// 각 문자열을 char 배열에 문자 하나씩 옮겨 담는다.
		for(int i = 1; i <= alength; i++) {
			A[i] = a.charAt(i - 1);
		}
		for(int i = 1; i <= blength; i++) {
			B[i] = b.charAt(i - 1);
		}
		
		// 각 문자의 비교가 끝났을 때, 해당 위치에서 가질 수 있는 LCS의 값을 저장할 2차원 dp테이블을 정의한다.
		// 첫 행에서도 이전 문자를 참고할 수 있도록 패딩을 준다.
		dp = new int[blength + 1][alength + 1];
		
		// B의 모든 문자열을 A문자열과 비교
		for(int i = 1; i <= blength; i++) {
			for(int j = 1; j <= alength; j++) {
				// 만일 두 문자가 같은 경우
				if(B[i] == A[j]) {
					// 대각선의 값을 참고하여 LCS의 값을 + 1한다.
					dp[i][j] = dp[i - 1][j - 1] + 1;
				}
				// 두 문자가 다른 경우
				else {
					// 각 문자열의 이전 문자 중 최대 LCS값을 선택.
					dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
				}
			}
		}
		
		// 최종으로 탐색한 위치에 LCS의 최대 값이 저장되어 있을 것이다.
		System.out.println(dp[blength][alength]);
	}
}

->두 문자열의 각 문자를 비교하는 과정을 수반하기 때문에, O(N^2)의 시간복잡도를 갖게 된다.

 

※ 여기까지가 다이나믹 프로그래밍에서 가장 유명한 3가지 예제 였다(Knapsack, LIS, LCS). 이는 다이나믹 프로그래밍이 무엇인지 감을 잡기 좋은 예제들이고, 몇몇 문제에서는 이곳에서 배운 논리를 기반으로 문제를 출제하기도 하므로 기본적인 예제에 대한 이해는 반드시 해두도록 하자.