LIS (최장 증가 부분 수열)

1. LIS ?

최장 부분 공통 수열 (LIS)란, 주어진 수열 내에서 오름차순으로 증가하는 가장 긴 수열을 찾아내는 문제이다. 

쉽게 말해서, 증가하는 값이 가장 긴 수열을 찾아내는 문제로, 본인은 DP를 공부하다가 알게 된 개념이다.

 

2. 유형

대부분의 공통적인 유형으로, 꼬인 전선을 푸는 문제나, 교차되지 않는 한도 내에서 최대한 많이 연결하는 문제가 주로 포진되어 있는 것 같다.

아래의 블로그를 통해 공부해본 뒤에 대표적으로 2가지 문제를 풀어보았다.

참조한 블로그

알고리즘 - 최장 증가 부분 수열(LIS) 알고리즘

 

1. DP를 이용한 기본 LIS 유형

백준 - 2565번 전깃줄 https://www.acmicpc.net/problem/2565

 

2. 이분탐색을 이용한 LIS 유형

백준 - 2352번 반도체 설계 https://www.acmicpc.net/problem/2352

 

 

3. 원리

1. DP

for (int i = 0; i < n; i++){
	dp[k] = 1;
    for (int j = 0; j < i; j++){
        if(arr[j] < arr[i]){
            dp[i] = max(dp[i], dp[j] + 1);
        }
    }
}

 

기본 LIS의 코드 구조이다.

 

최적의 값을 기록할 dp배열을 저장해 나가는 식으로 계산한다. 해당 인덱스의 수보다 앞선 인덱스의 수가 더 작을 경우, 현재 인덱스에 해당하는 수를 기준으로 앞선 인덱스는 증가하는 수열이기 때문에 조건문을 만족하게 되고, 현재까지 계산한 값과 이전에 계산된 최적의 값에 현재 인덱스를 더한 값을 비교하여 더 큰 값으로 dp배열을 정해준다.

 

예를들어 2, 1, 7, 5, 9 가 있다고 가정하면,

dp[3]까지는 2이라는 값이 나오게 된다. (2, 7 또는 1, 5)

dp[4]의 경우 j가 3일 때, dp[4]에 해당하는 2와, dp[3]에 해당하는 2에 9를 추가한 3이랑 비교를 하게 되고, 3이 더 크므로, dp[4]는 3이 되게 된다.

 

여기까지가 내가 이해한, dp를 이용한 LIS의 기본 원리이다.

 

 

2. 이분 탐색

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


public static int binarySearch(int value, int[] arr, int listSize) {
        int start = 0;
        int end = listSize;
        int mid = 0;
        while (start <= end) { // 종료 조건: start > end
            mid = (start + end) / 2;

            if (value == arr[mid]) {
                return mid; // 값이 동일하면 해당 위치 반환
            } else if (value < arr[mid]) {
                end = mid - 1; // 왼쪽으로 범위 축소
            } else {
                start = mid + 1; // 오른쪽으로 범위 축소
            }
		}

	return start; // 값이 없으면 삽입 위치 반환
}

   
        while (i < N) {
            if (list[j] < arr[i]) {
                list[j+1] = arr[i];
                j+=1;
            } else {
                int index = binarySearch(arr[i],list,j);
                list[index] = arr[i];
            }
            i+=1;
        }

        System.out.println(j+1);
    }

 

기존 dp를 사용하는 방법은 시간 복잡도가 O(n^2)이기 때문에 매우 느린 것을 알 수 있다. 그래서, 오름차순에 맞추어 자리를 지정해 주는 빠른 방법으로 시간 복잡도가 O(nlogn)인 이분 탐색을 적용하면 더욱 빠르다고 한다.

해당 코드에서는 == 까지 구현해 주었지만, LIS는 찾는 값과, 같은 값이 존재할 수 없는 구조이기 때문에 (오름차순의 특성 상 중복 되지 않아야 하기 때문) 리턴 값은 end로 하고, start의 +1은 제외 시켜주는 방식이 더욱 맞는 방식이다.

 

원리는, arr배열은 원본 배열이고, list는 우리가 만들어 줄 배열로 원본 배열을 순회하면서 리스트 내의 값보다 더 큰 값이 올 경우 리스트 맨 뒤에 붙여주고, 그렇지 않은 경우는 이분탐색을 통하여 자리를 지정해준 뒤 해당 값을 갱신해주는 방식이다. 이렇게 하면, 기존 오름차순을 list배열에 만들어 줄 수 있어 더욱 빠른 LIS가 완성된다.

 

LIS에서 중요한 키워드는 한 쪽은 정렬되어 있는 것, 순서대로 라는 키워드 인 것 같다. 두 문제 모두, 한 쪽의 N의 값을 정렬 시켜준 뒤, 다른 값에서 최장부분 공통수열을 찾기 때문이다.