BOJ#11053 가장 긴 증가하는 부분 수열 (LIS)

BOJ#11053 가장 긴 증가하는 부분 수열(LIS)

* 문제

https://www.acmicpc.net/problem/11053

* 풀이

유명한 문제인 Longest Increasing Subsequence (LIS)입니다.

O(N^2) 방법과 O(N logN) 방법으로 풀어보았습니다.

기존에 워낙 설명이 잘 되어있어서 따로 포스팅 하지는 않겠습니다만,

제가 공부할 때 참고했던 사이트 남겨드립니다.

1. LIS 이해 및 O(N^2) 풀이

https://www.youtube.com/watch?v=CE2b_-XfVDk

위 동영상을 보시고 아래 저의 코드를 보시면 되겠습니다.

* 나의 코드

// O(N^2) for (int i = 1; i < N; i++) { for (int j = 0; j < i; j++) { if (A[j] < A[i]) { if (dp[i] <= dp[j]) { dp[i] = dp[j] + 1; length = dp[i] > length ? dp[i] : length; } } } }

2. O(N logN) 풀이

https://youtu.be/S9oUiVYEq7E

,

http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/

http://codedoc.tistory.com/414

http://greatzzo.tistory.com/23

☞ 2017.2.17 추가

예를 들어 {5, 6, 7, 1, 2}라는 수열의 LIS를 구하고자 할 때,

O (NlogN) 해법이란

1. 빈 수열을 하나 만들고

   {}

2. 문제의 주어진 수열에서 숫자를 하나씩 뽑아 추가해나가며

   {5, 6, 7, 1, 2}

3. 각 길이를 갖는 부분_증가 수열들 중에 가장 마지막 수의 최소값을 추적해 나간다.

---

아래 소스에서 A 배열이 {5, 6, 7, 1, 2}이라면,

tailTable은 {1, 2, 7}이 될 것입니다.

이것의 의미는 아래와 같습니다.

- 길이가 1인 부분 증가 수열들 중에 마지막 수의 최소는 1이다.

  {1}, {2}, {5}, {6}, {7}

- 길이가 2인 부분 증가 수열들 중에 마지막 수의 최소는 2이다.

  {1, 2}, {5, 6}, {6, 7}

- 길이가 3인 부분 증가 수열들 중에 마지막 수의 최소는 7이다.

  {5, 6, 7}

※ 정의 : tailTable[i] = 길이가 i인 부분_증가 수열들 중에 마지막 수의 최소값

---

☞ 2017.3.15 추가

{3, 1, 5, 2, 7, 4, 9}

현재 길이가 3인 증가 부분 수열에서

길이가 4인 증가 부분 수열을 구하고자 할 때

중요한 것은 현재 수열의 마지막 값입니다.

앞에 어떤 숫자들이 있는지는 중요하지 않습니다. 왜냐하면 마지막 값만 알고 있으면 그 다음 숫자를 정할 수 있기 때문입니다.

길이가 3인 수열들은

{3, 5, 7}, {1, 2, 7}, {1, 2, 4}, {3, 5, 9} 등이 있지만

마지막 숫자가 4인 경우가 가장 유리합니다. 왜냐하면 4가 가장 작기 때문에 뒤에 숫자들을 많이 덧붙일 수 있는 가능성이 더 높기 때문입니다.

따라서 nlogn 방법에서는 수열에서 숫자를 한개씩 꺼내면서 아래와 같은 방식으로 마지막 숫자들을 모으는 것입니다.

- 마지막 숫자보다 큰 숫자는 추가하고

- 그 외의 경우에는 교체 (각 길이의 증가 부분 수열의 마지막 수가 작을 수록 뒤에 숫자를 덧붙일 수 있는 가능성이 높기 때문에)

☞ 2017.2.15 수정

나의 코드

-> Arrays.binarySearch를 이용한 소스

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

/*
 * BOJ#11053 가장 긴 증가하는 부분 수열
 * https://www.acmicpc.net/problem/11053
 * O(N log N)
 */

public class Main {

    public static void main(String[] args) throws IOException {

        int N; // array length
        int[] A;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        A = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {

            A[i] = Integer.parseInt(st.nextToken());
        }

        // O(N log N)
        System.out.println(LISLength(A, N));

    }

    static int LISLength(int[] A, int size) {

        int[] tailTable = new int[size];
        int lisLength = 0; // always points empty slot

        // 초기값
        tailTable[0] = A[0];
        lisLength = 1;

        for (int i = 1; i < size; i++) {

            // 후보값이 LIS의 처음 값보다 작은지?
            if (A[i] < tailTable[0]) {

                tailTable[0] = A[i];
            }
            // 후보값이 LIS의 마지막 값 보다 큰지?
            else if (A[i] > tailTable[lisLength - 1]) {

                tailTable[lisLength] = A[i];
                lisLength++;
            } else {

                // CeilIndex를 찾고 replace한다.

                int idx1 = Arrays.binarySearch(tailTable, 0, lisLength, A[i]);

                idx1 = idx1 < 0 ? -idx1 - 1 : idx1;

                tailTable[idx1] = A[i];

            }
        }

        return lisLength;
    }
}

---

* 나의 코드

https://github.com/stack07142/BOJ/tree/master/BOJ%2311053_LongestIncreaseSubsequence