백준 3745번 오름세 [LIS] :: 마이구미

이번 글은 백준 알고리즘 문제 3745번 "오름세"를 다뤄본다.

문제의 접근은 LIS(최장 증가 부분 수열) 알고리즘 문제이다.

LIS O(nlogn) - http://mygumi.tistory.com/303

본인은 LIS 알고리즘을 다룬 글이 있다. (관련 글)

관련 글은 시간 복잡도 O(n^2)으로 문제를 해결했다.

오름세 문제는 O(n^2)으로는 문제를 해결할 수 없다.

시간초과를 초래하니 LIS의 또 다른 접근 방식으로 문제를 해결한다.

이번에 다룰 LIS의 시간복잡도는 O(nlogn)을 가진다.

이분 탐색 또는 이진 탐색이라고 불리는 알고리즘을 이용하는 방식이다. (관련 글)

전체적인 의사코드로 표현하면 아래와 같다.

// nums - 주어진 수열
for each num in nums
     if(list.size()==0)
         add num to list // 리스트에 num 추가
     else if(num > last element in list) // num이 리스트의 마지막 값보다 클 경우
         add num to list // 리스트에 num 추가
     else 
         replace the element in the list which is the smallest but bigger than num
         // 리스트에 있는 값 중 num 보다 크면서 가장 작은 값을 num으로 대체

결과적으로 위와 같이 처리된다면, 아래와 같은 흐름을 볼 수 있다.

아래 그림과 함께 구현된 코드를 보면 이해가 쉽게 갈 것이다.

for(int num : array) {

    if (list.size() == 0 || num > list.get(list.size() - 1)) {
        list.add(num);
    } else {

        int i = 0;
        int j = list.size() - 1;

        while (i < j) {

            int mid = (i + j) / 2;

            if (list.get(mid) < num) {
                i = mid + 1;
            } else {
                j = mid;
            }

        }

        list.set(j, num);

    }

}

결과적으로 LIS의 길이를 구할 수 있다.

하지만 리스트에 있는 값들은 정확한 LIS가 아니다.

길이만을 고려한 방식이다.

그렇기에 LIS에 해당하는 리스트는 뽑아낼 수 없다.

머리를 굴려봤지만 떠오르지 않았다.

혹시나 알고 있다면 알려주면 감사하겠다.

문제에 대한 전체 소스는 아래 Github URL을 참고하길 바란다.

참고 URL

http://www.programcreek.com/2014/04/leetcode-longest-increasing-subsequence-java/

백준 알고리즘 문제 3754번 오름세 전체 소스

https://github.com/hotehrud/acmicpc/blob/master/algorithm/lis/3745.java