• LIS 최장증가수열 알고리즘 -2- :: 마이구미
    알고리즘 2018. 3. 18. 14:52
    반응형

    이전에 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


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


    LIS O(nlogn)


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

    4 ~ 5번의 경우에는 LIS 길이뿐만 아니라, 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


    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
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    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;
        }
    }
    cs


    반응형

    댓글

Designed by Tistory.