[알고리즘] 최장 공통 부분수열(LCS, Longest Common Subsequence)

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

최장 공통 부분 수열은 두 개의 문자열이 주어졌을 때, 문자로 이루어진 부분 수열 중에서 가장 긴 문자열이 일치하는 수열을 말한다.

 

예를 들어 cdabe와 cdegt가 주어졌다면 이 두 문자열의 최장 공통 부분수열은

 

cdabe, cdegt 즉, 길이가 3인 부분수열 {c, d, e} 된다.

 

최장 공통 부분수열 과정

최장 증가 수열은 동적 계획법(DP, Dynamic Programming)을 이용해 풀 수 있다.

 

각각 n, m길이의 두 문자열 str1, str2가 주어졌을 때, n X m 크기의 2차원 배열을 만든다.

 

이 2차원 배열은 각 문자열, i번째, j번째 원소까지의 최장 공통 부분을 저장할 배열이다.

 

각 문자열의 부분문자열 하나씩 비교해 최장 공통 길이를 저장한다.

 

각 문자열의 부분문자열의 최장 공통 길이를 저장하는 2차원 배열을 dp[n][m]이라고 했을 때,

 

각 행과 열이 나타내는 글자 str1[i]와 str[j]가

같을 경우 dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + 1이 된다.

다를 경우 dp[i][j] = max(dp[i-1][j], dp[i][j-1])

 

저장하는 과정을 아래와 같다.

 

		c	d	a	b	e
	0	0	0	0	0	0
c	0	1	1	1	1	1
d	0
e	0
g	0
t	0

 

		c	d	a	b	e
	0	0	0	0	0	0
c	0	1	1	1	1	1
d	0	1	2	2	2	2
e	0
g	0
t	0

 

		c	d	a	b	e
	0	0	0	0	0	0
c	0	1	1	1	1	1
d	0	1	2	2	2	2
e	0	1	2	2	2	3
g	0
t	0

 

		c	d	a	b	e
	0	0	0	0	0	0
c	0	1	1	1	1	1
d	0	1	2	2	2	2
e	0	1	2	2	2	3
g	0	1	2	2	2	3
t	0

 

		c	d	a	b	e
	0	0	0	0	0	0
c	0	1	1	1	1	1
d	0	1	2	2	2	2
e	0	1	2	2	2	3
g	0	1	2	2	2	3
t	0	1	2	2	2	3

 

최장 공통 부분수열 구현

package algorithm;

import java.util.*;

public class LCS {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		
		for(int t = 1; t <= tc; t++) {
			String s1 = sc.next();
			String s2 = sc.next();
			String max;
			String min;
			int cnt = 0;
			
			if(s1.length() > s2.length()) {
				max = s1;
				min = s2;
			}
			else {
				max = s2;
				min = s1;
			}
			
			int[][] a = new int[min.length()][max.length()];
			
			if(max.charAt(0) == min.charAt(0)) a[0][0] = 1;
			else a[0][0] = 0;
			
			for(int i = 1; i < max.length(); i++) {
				if(max.charAt(i) == min.charAt(0)) {
					a[0][i] = a[0][i-1] + 1;
				}
				else {
					a[0][i] = a[0][i-1];
				}
			}
			
			for(int i = 1; i < min.length(); i++) {
				if(max.charAt(0) == min.charAt(i)) {
					a[i][0] = a[i-1][0] + 1;
				}
				else {
					a[i][0] = a[i-1][0];
				}
				for(int j = 1; j < max.length(); j++) {
					if(min.charAt(i) == max.charAt(j)){
						a[i][j] = Math.max(a[i-1][j], a[i][j-1]) + 1;
					}
					else {
						a[i][j] = Math.max(a[i-1][j], a[i][j-1]);
					}
					cnt = Math.max(a[i][j], cnt);
				}
			}
			System.out.println("#" + t + " " + cnt);
		}
	}
}