[알고리즘] 최장 공통 부분 수열 LCS - DP & 이진탐색 LIS (Java)

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

LCS(Longest Common Subsequence)는 LCS는 주로 최장 공통 부분수열(Longest Common Subsequence)을 나타내지만 최장 공통 문자열(Longest Common Substring)을 말하기도 한다.

최장 공통 문자열(Longest Common Substring)은 반드시 부분 문자열이 연결된 형태여야한다. banana, vbankn
최장 공통 부분수열(Longest Common Subsequence)은 떨어져있어도 상관없다. bdanvv, vbkkanm

이번에 다룰 LCS 알고리즘은 최장 공통 부분수열(Longest Common Subsequence)이다. 이는 주어진 여러 개의 수열 모두의 부분수열이 되는 수열들 중에 가장 긴 것을 찾는 문제다.(종종 단 두 개중 하나가 되기도 한다.) 컴퓨터 과학에서 고전으로 통하는 문제이며, diff 유틸리티의 근간이 되며, 생물정보학에서도 많이 응용되고 있다.

1-1. LCS 길이 찾는 방법 (DP)

ACAYKP 와 CAPCAK의 LCS를 찾아보면 ACAK가 LCS가 된다. 따라서 LCS길이는 4이다. 이를 구하는 방법으로는 이중 포문을 사용하여 각 원소들을 하나씩 직접 비교해주면서 dp값을 갱신해주면된다.

dp는 2차원 배열로 수열 n1과 n2의 LCS길이를 저장해준다.

dp[수열 n1의 i번째][수열 n2의 j번째] = 수열 n1(0~i)와 수열 n2(0~j)의 LCS 길이

설계

i : str1의 문자열 i번째 문자, j : str2의 문자열 j번째 문자

if(i==j) str1(0~i-1)과 str2(0~j-1)의 LCS + 1을 해준다.
1. (ACAYKP, CAPCAK)
  1. i=3, j=2 일 때, (AC 의 LCS : dp[2][1] =1 ) + 1 = 2)
if(i!=j) str1(0~i-1)과 str2(0~j)의 dp[i-1][j], str1(0~i)와 str2(0~j)의 dp[i][j-1] 중 최댓값을 받아온다.
1. (ACAYKP, CAPCAK)
  1. i=3, j=3 일 때, (AC CAP의 LCS : dp[2][3] =1 ) vs (ACA CA dp[3][2] =2 ) → 2

2차원 배열 dp를 표로 나타내면 다음과 같다.

	A	C	A	Y	K	P
0	0	0	0	0	0	0
C	0	1	1	1	1	1
A	1	1	2	2	2	2
P	1	1	2	2	2	3
C	1	2	2	2	2	3
A	1	2	3	3	3	3
K	1	2	3	3	4	4

풀이코드

백준 9251번 LCS

import java.io.*;

public class Main {
	static int[][] dp;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str1 = br.readLine();
		String str2 = br.readLine();
		System.out.println(LCS(str1, str2));
	}
	
	static int LCS(String str1, String str2) {
		int n1 = str1.length();
		int n2 = str2.length();
		
		dp = new int[n1+1][n2+1];
		for(int i=1; i<n1+1; i++) {
			for(int j=1; j<n2+1; j++) {
				if(str1.charAt(i-1) == str2.charAt(j-1)) {
					dp[i][j] = dp[i-1][j-1]+1;
				}else {
					dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
				}
			}
		}
		return dp[n1][n2];
	}
}

1-2. LCS 문자열 찾는 방법 (DP)

위에서 사용한 dp 2차원 배열 표를 보면 쉽게 풀어낼 수 있다. 위의 색칠된 숫자를 자세히보면 dp값이 변하는 부분임을 알 수 있다. 그 부분이 LCS를 찾아내는 부분이므로 저 위치들만 골라서 탐색을 해주면 된다.

설계

dp값이 줄어드는 절벽 구간에 도달했다면 해당 부분에 속하는 문자를 저장한다. n → 0 하향식으로 값을 저장해주므로 후입선출을 해주는 Stack자료구조를 사용하여 데이터를 저장한다.

dp[i][j] == dp[i-1][j] 이면
1. i → i-1 , j → j 로 이동
dp[i][j] == dp[i][j-1] 이면
1. i → i , j → j-1 로 이동
1,2에 해당하지않으면 해당 부분은 절벽 구간으로 LCS의 문자열이므로 stack에 저장한다.
1. stack.push(str.charAt(i-1));
2. i → i-1, j →j-1로 이동

풀이코드

백준 9252번 LCS2

import java.io.*;
import java.util.Stack;

public class Main {
	static int[][] dp;
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str1 = br.readLine();
		String str2 = br.readLine();
		LCS2(str1,str2);
		getLCSToString(str1, str1.length(), str2.length());
		System.out.println(sb.toString());
	}
	
	static void LCS2 (String str1, String str2) {
		int n1 = str1.length();
		int n2 = str2.length();
		
		dp = new int[n1+1][n2+1];
		int max =-1;
		for(int i=1; i<n1+1; i++) {
			for(int j=1; j<n2+1; j++) {
				if(str1.charAt(i-1) == str2.charAt(j-1)) {
					dp[i][j] = dp[i-1][j-1] +1;
				}else {
					dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
				}
			}
		}
		sb.append(dp[n1][n2] + "\n");
	}
	
	static void getLCSToString(String str, int i, int j) {
		Stack<Character> st = new Stack<>();
		while(i>0 && j>0) {
			if(i == 0 || j ==0)break;
			
			if(dp[i][j] == dp[i-1][j]) {
				i--;
			}else if(dp[i][j] == dp[i][j-1]) {
				j--;
			}else {
				st.push(str.charAt(i-1));
				i--;
				j--;
			}
		}
		while(!st.isEmpty()) {
			sb.append(st.pop());
		}
	}
}

2. LCS 길이 찾는 방법 (이진탐색 LIS)

위의 DP 풀이는 이중 포문을 사용한 풀이로 두 수열 길이가 n1, n2라고할 때 시간복잡도 O(n^2)을 갖게된다. 이는 문자열 길이가 100만 이상으로 주어지면 엄청난 시간이 걸릴 것이다.

이 두 수열 LCS 길이를 이중포문이 아닌 LIS를 통해 LCS를 구할 수 있는 방법이 있다. 이진탐색을 통한 LIS알고리즘은 시간복잡도 O(nlogn)을 가진다.

구상

백준 13711번 LCS4

두 수열 [1 3 2], [1 2 3] 의 LCS는 [1,2] or [1,3]이다.

이는 따지고보면 [1 2 3]은 index순대로 정렬이 되어있기 때문에 [1 3 2]의 가장 긴 증가하는 부분 수열(LIS)을 구하는 것과 다름없다.
그래서 하나의 배열을 기준([1 2 3])으로 정하고 다른 배열([1 3 2])을 이 기준이 되는 배열과 비교하여 index를 정리하면 된다.

따라서 하나의 배열을 기준 index로 정하고 다른 배열을 기준 index를 통해 다시 원소를 재배열한 다음 해당 배열의 LIS를 구하면 결국은 두 배열의 LCS를 찾는 것과 똑같다.

총 3가지의 자료구조를 사용하여 풀이를 한다.

standard : 첫 번째로 주어진 배열로 비교의 기준 index가 되는 배열 standard {1, 2, 3}
arr : 두 번째로 주어진 배열의 값들의 위치 index를 저장한 배열 arr[num-1] = i
- 두 번째로 주어진 입력 배열 {1, 3, 2} → arr {0, 2, 1} // 1은 0번 인덱스, 2는 2번 인덱스, 3은 1번 인덱스
res : standard배열을 기준으로 arr 원소들의 상대적 위치를 저장하는 배열 res[i] = arr[standard[i]-1]+1

standard 배열

standard 배열이 가장 중요하다. 이 배열은 숫자가 아닌 하나의 기준이 된다는 것을 알아야한다.

standard(기준) : [1 4 6 7 5 2 3 8]
두 번째로 주어진 배열 : [1 2 3 6 7 8 4 5]
arr : [0 1 2 6 7 3 4 5]
res : [ 1 7 4 5 8 2 3 6 ]

res배열 구하는 시뮬레이션

res[0] = arr[standard[0]-1]+1 = arr[0]+1 = 1
res[1] = arr[standard[1]-1]+1 = arr[3]+1 = 7
res[2] = arr[standard[2]-1]+1 = arr[5]+1 = 4

...

res[7] = arr[standard[7]-1]+1 = arr[7]+1 = 6

만약 위의 과정이 헷갈린다면 기준이 되는 배열(standard)이 [a b c d e f g h]이고 두 번째로 주어진 배열은 [a d f g e b c h]이라고 하자.

그러면 arr배열은 두 번째로 주어진 배열 그대로 [a d f g e b c h]이 된다.

위의 두 번째로 주어진 배열 [1 2 3 6 7 8 4 5]도 알파벳 순이라고 가정하고 standard를 [ a b c d e f g h]로 바꿔서 생각하면 res배열은 그대로 [a d f g e b c h]가 된다. 하나의 배열을 기준으로 삼고 그거에 따른 새로운 수열을 하나 만드는 것이다.

이렇게 res배열이 구해지면 위에서 말한바와 같이 해당 배열의 LIS의 길이를 구해주면 된다. 효율적인 탐색을 위해 이진탐색을 활용한 LIS알고리즘을 통해 구해줘야한다.

설계

처음으로 주어진 배열을 비교의 기준이 되는 배열(standard)로 지정한다.
그리고 두 번째로 주어진 배열 원소들이 저장된 Index를 arr배열에 저장한다.
standard 배열을 기준으로 arr원소들이 상대적으로 어디에 저장되어 있는 위치를 새로운 배열 res에 저장한다.
해당 res배열의 LIS를 이진탐색을 통해 구해준다.

풀이코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
	static int n;
	static int[] memo;
	public static void main(String[] args) throws IOException{
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		int[] standard = new int[n];
		int[] arr = new int[n];
		
		StringTokenizer st = new StringTokenizer(br.readLine());		
		for(int i=0; i<n; i++) {
			standard[i] = Integer.parseInt(st.nextToken());
		}
		
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			int num =  Integer.parseInt(st.nextToken());
			arr[num-1] = i;
		}
		
		int[] res = new int[n];
		for(int i=0; i<n ;i++) {
			res[i] = arr[standard[i]-1]+1;
		}
		
		// res의 LIS구하기 
		memo = new int[n+1];
		int answer = LIS(res);
		System.out.println(answer);
	}
	
	
	static int LIS(int[] arr) {
		int len=0;
		int idx=0;
		for(int i=0; i<n; i++) {
			if(arr[i] > memo[len]) {
				len +=1;
				memo[len] = arr[i];
			}else {
				idx = binarySearch(0, len, arr[i]);
				memo[idx] = arr[i];
			}
		}
		return len;
	}
	
	static int binarySearch(int left, int right, int key) {
		int mid =0;
		while(left<right) {
			mid = (left+right)/2;
			if(memo[mid] < key) {
				left = mid+1;
			}else {
				right = mid;
			}
		}
		return right;
	}
}

'Dot Algo∙ DS > 알고리즘 개념' 카테고리의 다른 글

[알고리즘] 최적화 문제 결정 문제로 바꿔풀기 - 파라메트릭 서치(Parametric Search) (0)	2021.10.22
[알고리즘] 탐욕스러운 그리디(Greedy) 알고리즘 정리 (Java) (1)	2021.10.19
[알고리즘] 가장 긴 증가하는 부분 수열 LIS - DP & 이진탐색 (Java) (2)	2021.08.09
[알고리즘] 최소 공통 조상 LCA 트리 - DP & 세그먼트 트리 (Java) (2)	2021.08.04
[자료구조] 세그먼트 트리 + Lazy Propagation (Java) (0)	2021.07.08

일	월	화	수	목	금	토
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30

그릿 속의 해빗

[알고리즘] 최장 공통 부분 수열 LCS - DP & 이진탐색 LIS (Java)

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

1-1. LCS 길이 찾는 방법 (DP)

설계

풀이코드

1-2. LCS 문자열 찾는 방법 (DP)

설계

풀이코드

2. LCS 길이 찾는 방법 (이진탐색 LIS)

구상

standard 배열

res배열 구하는 시뮬레이션

설계

풀이코드

'Dot Algo∙ DS > 알고리즘 개념' 카테고리의 다른 글

티스토리툴바

티스토리툴바

[알고리즘] 최장 공통 부분 수열 LCS - DP & 이진탐색 LIS (Java)

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

1-1. LCS 길이 찾는 방법 (DP)

설계

풀이코드

1-2. LCS 문자열 찾는 방법 (DP)

설계

풀이코드

2. LCS 길이 찾는 방법 (이진탐색 LIS)

구상

standard 배열

res배열 구하는 시뮬레이션

설계

풀이코드

'Dot Algo∙ DS > 알고리즘 개념' 카테고리의 다른 글

'Dot Algo∙ DS/알고리즘 개념' 관련글

티스토리툴바

티스토리툴바