LIS (Longest Increasing Subsequence) 완전 정복: O(N log N) 해법

1. 문제 정의

주어진 수열에서 가장 긴 증가하는 부분 수열의 길이를 구하는 문제다. 예: [10, 9, 2, 5, 3, 7, 101, 18] $\rightarrow$ [2, 3, 7, 18] (길이 4)

---

2. 접근 방법

1) Dynamic Programming ($O(N^2)$)

\(DP[i] = 1 + \max(\{DP[j] \mid j < i, A[j] < A[i]\} \cup \{0\})\) 직관적이지만 $N$이 커지면 느리다.

2) Binary Search 활용 ($O(N \log N)$)

“가능한 한 작은 값으로 증가 수열을 만들어야 더 길게 이을 수 있다”는 그리디한 아이디어를 사용한다.

tails 배열을 유지한다:

tails[i] = 길이가 i+1인 증가 부분 수열 중 가장 마지막 원소가 작은 값

새로운 원소가 들어올 때, tails 배열에서 이분 탐색(Lower Bound)을 수행하여 적절한 위치를 갱신하거나 길이를 늘린다.

import bisect

def find_lis_length(nums):
    tails = []
    for x in nums:
        idx = bisect.bisect_left(tails, x)
        if idx < len(tails):
            tails[idx] = x
        else:
            tails.append(x)
    return len(tails)

이 방식은 Patience Sorting과도 관련이 깊다.

```