[Algorithm] LIS : 가장 긴 증가하는 부분 수열

LIS

LIS는 Longest Increasing Subsequence의 약자로, 주어진 배열의 부분 수열 중 각 원소가 이전 원소보다 커야 한다는 조건을 만족하는 가장 긴 부분 수열이다. 예시를 들자면 다음과 같다.

[10 20 10 30 20 50]

위와 같은 배열에서 LIS는 10 20 10 30 20 50 으로, 길이는 4이다.

 

다이나믹 프로그래밍 DP

LIS를 찾는 가장 간단한 방법은 DP를 이용하는 것이다. 주어진 수열을 저장할 배열 뿐 아니라, 각 원소가 포함된 가장 긴 부분 수열을 저장할 또다른 배열이 필요하다. 여기서는 주어진 수열을 저장하는 num, 가장 긴 부분 수열의 길이를 저장할 배열을 len이라고 하겠다.

 

for (int i = 1; i < N; i++) {
	for (int j = 0; j < i; j++) {
    	if(num[i] > num[j] && len[i] < len[j] + 1) {
        	len[i] = len[j] + 1;
        }
    }
}

위 코드를 보면 i번 이전까지를 확인하며 1. i번째 원소보다 작은지, 2. i번째 원소보다 작다면 len[i]값이 len[j] + 1보다 작은지 확인한다. 즉, 현재 원소보다 작은 원소 중 가장 긴 증가하는 부분 수열을 가진 것을 찾고, 그 길이에 1을 더해주는 것이다.

 

나는 이 방법으로 백준 11053번 : 가장 긴 증가하는 부분 수열(https://www.acmicpc.net/problem/11053)을 풀었는데, 다른 사람들의 풀이를 보니 상당히 다양한 방법이 존재했다.

 

이분 탐색으로 LIS 찾기

가장 많이 보인 유형은 이분 탐색으로 찾는 것이다. 주어진 수열 num과, LIS를 저장할 lis 배열이 필요하다. 이 방법은 O(NlogN)으로 LIS를 구하는 방법 중 시간 복잡도가 가장 작다.

int[] num; // 배열이 저장되어 있다
int[] lis = new int[N];
int idx = 0;

lis[0] = num[0];
for (int i = 1; i < N; i++) {
	if(lis[idx] == num[i]) continue;
    if(lis[idx] < num[i]) lis[++idx] = num[i];
    else {
    	int start = 0;
        int end = idx;
        
        while(start < end) {
        	int mid = (start + end) / 2;
            
            if(lid[mid] < num[i]) {
            	start = mid + 1;
            } else {
            	end = mid;
            }
        }
        lis[end] = num[i];
    }
}

// LIS의 길이는 idx와 같다.

복잡해보이지만 결국 여기서 이분 탐색의 목적은 현재 원소보다 큰 것 중 최솟값의 위치를 구하는 것이다. 위치를 찾았다면 현재 원소로 교체한다. 그래야 이후에 나올 숫자들과 비교하며 가장 긴 증가하는 부분 수열을 찾을 수 있기 때문이다.

 

이를 통해 항상 각 순서의 최솟값을 유지하며 다음번 원소와 비교할 수 있다. 당연히, 계속 업데이트되기 때문에 lis 배열에 저장된 값이 실제 LIS 배열과 같지 않을 수도 있다.

num : [50, 60, 70, 80, 10, 20, 30]
실제 LIS : [50, 60, 70, 80]
연산이 끝난 후 lis : [10, 20, 30, 80]