[알고리즘] LCS(최장 공통 부분 수열) & LIS(가장 긴 증가하는 부분 수열)

1. LCS란?

Longest Common Subsequence의 약자이며, 두 문자열을 비교할  때 공통적으로 나타나는 부분 순서들 중 가장 긴 것을 말한다.

예를 들어,  'ABCBDAB'와  'BDCABA'의 LCS를 구해보면

ABCBDAB

BDCABA

=> 'BCBA'가 나오게 된다.

 

그리고 LCS는 최적화를 해야 하는 문제이기 때문에, 동적계획법(DP)를 사용하여야 가장 효율적으로 구할 수 있다.

 

 

1-1. 접근 방법 & 예시

두 문자열 'GCABCD' 그리고 'ABDCED'가 주어졌을 때, LCS를 구하는 진행과정은 다음과 같다.

위 그림에서 확인할 수 있듯이, {GCA}, {GCAB}, {GCABC}, {GCABCD}와 {A}를 비교하면 공통 수열이 1임을 알 수 있다.

위 그림은 {ABDCED} 문자열의 'B'를 추가하여 비교한 것이다. 마찬가지로, 위의 문자열과 {AB}를 비교하기 때문에 {GCAB} 이후 길이가 2가 됨을 알 수 있다.

이어서 진행되는 과정들을 쭉 보면 다음과 같다.

이 그림을 토대로 점화식을 구해보면 다음과 같은 규칙들이 있음을 알 수 있다.

 

LCS 길이 진행 규칙(점화식)

1. 문자열의 비교가 같은 경우 : 부분 문자열 증가. 즉, 대각선 왼쪽 위까지의 진행상 길이 + 1

2. 문자열의 비교가 다른 경우 : 현재 진행상황의 왼쪽과 위쪽 값중 더 큰 값

 

코드로 나타내면 아래와 같다.

// 문자열s1, s2
int n = s1.length();
int m = s2.length();

int[][] dp = new int[n+1][m+1];

if(s1.charAt(i-1) == s2.charAt(j-1)) dp[i][j] = dp[i-1][j-1] + 1;
if(s1.charAt(i-1) != s2.charAt(j-1)) dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);

---

2. LIS란?

Longest Increasing Subsequence의 약자이며, 불연속 상관없이 가장 긴 증가하는 부분 수열을 구하는 알고리즘이다.

예들 들어, 수열 A = {10,20,10,30,20,50}이 있다고 하면, 해당 수열의 LIS는 {10,20,30,50}이다. 길이는 4

 

풀이 방법에 아래와 같이 두가지 방식이 있다.

1. DP(시간복잡도 O(N^2)) -> 간단하지만, N이 클수록 시간이 오래걸림

2. 이분탐색(시간복잡도 O(nlogn)) -> 복잡하지만, N이 클때 유리

 

이제 두 가지 풀이방법에 대해 알아보자.

---

2-1. DP를 이용한 풀이

DP를 이용한 풀이는 간단하다.

먼저, 1차원 배열 dp를 선언해준다.(선언 후 1로 초기화)

(여기서, dp[i] = 0~i의 증가하는 부분 수열 크기)

 

다음, 이중 포문을 설계하여 각 수를 비교해가면서 증가하는 부분 수열의 크기를 카운트해준다.

1. i : 0 ~ n-1

2. j : i+1 ~ n-1

 

마지막으로, dp배열중 가장 큰 값을 출력하면 된다.

// numArr는 입력된 수열을 순차적으로 담은 배열
for(int i = 0; i < N; i++) {
    for(int j = i+1; j < N; j++) {
        if(numArr[i] < numArr[j]) {
            dp[j] = Math.max(dp[j], dp[i] + 1);
        }
    }
}

int max = 0;
for(int d : dp) {
    max = Math.max(max, d);
}

 

하지만, 이런 이중for문은 N값이 10000이상이되면, 시간초과가 발생한다.(O(N^2))

효율성을 올리기 위해 이분탐색을 통한 최적화 작업을 거쳐 시간복잡도를 O(NlogN)로 줄여주는 방식에 대해 알아보자.

---

2-2. 이분탐색을 이용한 풀이(Lower Bound)

- LIS의 길이만 구할 때 사용(수열을 구하기 위해선 따로 역추적 과정 필요)

수열을 순회하면서, 현재 값을 신규 배열에 넣거나 치환하는 방식으로 구현되고,

현재 값의 Lower Bound가 없다면 삽입하고, 있다면 해당 값을 찾아서 치환한다.

 

예를 들어, {10,20,10,30,20,50}이라는 수열이 있다고 하자.

 

1. LIS배열에 수열의 첫 번쨰 원소를 넣는다(10)

10

2. LIS배열에 마지막 원소(10)가 현재 원소(20)보다 작다면 Lower Bound를 찾을 수 없으므로 그대로 값을 넣어준다.

10

20

3. 현재 원소(10)이 LIS배열의 마지막 원소(20)보다 작기 때문에, 이분 탐색을 통해 적합한 자리를 찾고 해당 값으로 치환한다.

10

20

4. 현재 원소(30)이 LIS배열의 마지막 원소(20)보다 크기 때문에, 그대로 값을 넣어준다.

10

20

30

5. 현재 원소(20)이 LIS배열의 마지막 원소(30)보다 작기 때문에, 이분 탐색을 통해 적합한 자리를 찾고 해당 값으로 치환한다.

10

20

30

6. 현재 원소(50)이 LIS배열의 마지막 원소(30)보다 크기 때문에, 그대로 값을 넣어준다.

10

20

30

50

 

코드는 아래와같다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception {
        int[] lis = new int[N]; // LIS 배열
        int[] arr = new int[N]; // 수열 배열

        //수열 저장
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        lis[0] = arr[0]; // 첫번째 원소 삽입
        int lisIdx = 0; // lis배열의 마지막 원소의 인덱스 값

        // 수열을 순회하면서 Lower Bound 값을 찾는다.
        for(int i = 1; i < N; i++) {
            // lis의 마지막 원소가 현재값 보다 작을때(Lower Bound 존재X => 그대로 삽입)
            if(lis[lisIdx] < arr[i]) {
                lisIdx++;
                lis[lisIdx] = arr[i];
            } else {
                // 마지막 원소가 현재값 보다 클 때(lis배열에서 arr[i]의 Lower Bound값에 해당하는 index를 찾아야함)
                int idx = lowerBound(0, lisIdx, arr[i]);
                lis[idx] = arr[i];
            }
        }

        System.out.println(lisIdx+1); // 마지막 인덱스 + 1 해야 총 길이가됨
	}
    
    public static int lowerBound(int Left, int Right, int n) {
    	int mid = 0;
        while(Left < Right) {
        	mid = (Left + Right) / 2;
            // arr[i]의 값이 lis배열의 중간 값보다 작거나 같으면, 오른쪽 인덱스(Right) 크기를 절반으로 줄인다.
            if(n <= lis[mid]) {
            	Right = mid;
            } else {
            	Left = mid + 1;
            }
        }

 

📗참고사이트

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

Longest Common Sub-sequence Algorithm(LCS, 최장 공통 부분수열)

[Algorithm] LIS 알고리즘 (최장증가수열 알고리즘)