LIS - Binary search를 이용한 O(NlogN) 풀이

항상 DP를 이용한 O(N^2) 풀이만 쓰다가, Binary search를 활용한 O(NlogN)을 공부했다.

생각보다 너무 쉬웠다.

 

https://www.youtube.com/watch?v=TocJOW6vx_I&t=208s

 

기본 아이디어는 배열에 LIS를 만들어가는데에서 시작한다.

주어지는 수 배열인 nums에서 숫자 n을 하나씩 따와서, LIS에 넣을 때 어디에 들어갈 지 체크한다. 

 

만약 맨 끝에 들어갈 수 있다면 그대로 넣어서 LIS가 1 더 증가하는 것이고,

만약 맨 끝에 들어가지 못한다면, 이진 탐색으로 n <= elem 인 elem을 찾은 뒤 n으로 바꿔 끼워넣는다.

(왜? elem은 n보다 크기 때문에, 더 작은 n으로 바꿔 끼워 넣어도 LIS가 유지되고,

추후 더 긴 LIS를 찾는데 도움되기 때문에 무조건 이득이다.)

 

아래 블로그도 비슷한 논리로 설명함.

https://jason9319.tistory.com/113

 

Py

from bisect import bisect_left

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        LIS = []
        for n in nums:
            idx = bisect_left(LIS, n)
            if idx == len(LIS):
                LIS.append(n)
            else:
                LIS[idx] = n
        print(LIS)
        return len(LIS)

C++

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> LIS;
        for (int n : nums){
            auto it = lower_bound(LIS.begin(), LIS.end(), n);
            
            if(it == LIS.end())
                LIS.push_back(n);
            else
                LIS[it-LIS.begin()] = n;
        }
        return LIS.size();
    }
};

 

시각화 잘 해놓은 블로그

https://4legs-study.tistory.com/106