LIS 최장증가수열 알고리즘 -2- :: 마이구미

이전에 LIS 알고리즘을 다룬적이 있다.

다뤘던 글의 시간복잡도는 O(n^2) 이라면, 이번에는 O(nlogn) 을 다룬다.

또한, 응용된 LIS 추적도 살펴본다.

결론적으로 가장 긴 증가하는 부분 수열 시리즈(1 ~ 5) 등과 같은 문제들을 해결할 수 있다.

이 방식은 이분 탐색을 요구한다.

LIS O(n^2) - http://mygumi.tistory.com/69

이분 탐색 - http://mygumi.tistory.com/72

참고 링크 - http://www.crocus.co.kr/681

O(nlogn) 방식의 경우에는 이분 탐색을 활용한 방식이다.

구현에 대한 흐름은 다음과 같다.

• 배열 마지막 요소보다 새로운 수가 크다면, 배열에 넣는다.
• 그렇지 않다면, 그 수가 들어갈 자리에 넣는다. (이분 탐색을 통해 들어갈 자리를 찾는다)

말로도 간단하게 표현할 수 있듯이 코드도 간단하다.

dp[0] = array[0];
int idx = 0;
for (int i = 1; i < n; i++) {
    if (dp[idx] < array[i]) {
        dp[++idx] = array[i];
    } else {
        int ii = lower_bound(idx, array[i]);
        dp[ii] = array[i];
    }
}
// ans => idx + 1

그림으로 표현하면 다음과 같다.

이것만으로 가장 긴 증가하는 부분 수열 문제 중 1 ~ 3 을 해결할 수 있다.

4 ~ 5번의 경우에는 LIS 길이뿐만 아니라, LIS 자체를 요구한다.

즉, 추적을 통해 LIS 를 구해야한다.

추적의 경우에는 본인은 너무 깊게 생각해서 헤맸다.

하지만 일반적으로 추적은 대부분 인덱스를 활용한다.

여기서도 인덱스와 함께 실제 값을 통해 구할 수 있다.

추적 배열을 추가한 흐름의 그림과 코드는 다음과 같다.

dp[0] = array[0];
tracking[0] = new Pair(0, array[0]);
int idx = 0;
for (int i = 1; i < n; i++) {
    if (dp[idx] < array[i]) {
        dp[++idx] = array[i];

        tracking[i] = new Pair(idx, array[i]);
    } else {
        int ii = lower_bound(idx, array[i]);
        dp[ii] = array[i];

        tracking[i] = new Pair(ii, array[i]);
    }
}

추적이 필요한 LIS의 대표적인 문제의 링크는 다음과 같다.

전깃줄 -2 => https://www.acmicpc.net/problem/2568

가장 긴 증가하는 부분 수열 5 - https://www.acmicpc.net/problem/14003

다음은 "가장 긴 증가하는 부분 수열 5" 문제의 소스이다.

기타 소스들은 Github 을 참고하길바란다.

Github - https://github.com/hotehrud/acmicpc/tree/master/algorithm/lis

static int[] dp;
 
private void solve() {
    int n = sc.nextInt();
    dp = new int[n];
    int[] array = new int[n];
 
    Pair[] tracking = new Pair[n];
 
    for (int i = 0; i < n; i++) {
        array[i] = sc.nextInt();
    }
 
    dp[0] = array[0];
    tracking[0] = new Pair(0, array[0]);
    int idx = 0;
    for (int i = 1; i < n; i++) {
        if (dp[idx] < array[i]) {
            dp[++idx] = array[i];
 
            tracking[i] = new Pair(idx, array[i]);
        } else {
            int ii = lower_bound(idx, array[i]);
            dp[ii] = array[i];
 
            tracking[i] = new Pair(ii, array[i]);
        }
    }
 
    Stack<Integer> stack = new Stack<Integer>();
    int temp = idx;
    for (int i = n - 1; i >= 0; i--) {
        if (temp == tracking[i].idx) {
            stack.push(tracking[i].value);
            --temp;
        }
    }
    System.out.println(stack.size());
    while(!stack.isEmpty()) {
        System.out.print(stack.pop() + " ");
    }
}
 
static int lower_bound(int end, int n) {
    int start = 0;
 
    while (start < end) {
        int mid = (start + end) / 2;
        if (dp[mid] >= n) {
            end = mid;
        } else {
            start = mid + 1;
        }
    }
    return end;
}
 
static class Pair {
    int idx;
    int value;
 
    Pair(int idx, int value) {
        this.idx = idx;
        this.value = value;
    }
}