악곱 == 악성곱슬

이분 탐색

---

해당 문제는 앞서 공부한 LIS를 구현하는 문제인데, 입력의 범위가 100만, 값의 범위가 100만인 문제였다. 따라서 기존 DP를 활용하는 O(N^2)으로는 해결할 수 없는 문제이다. 따라서 O(NlogN) 이하의 알고리즘이 필요한 상황이고 이분탐색을 활용할 수 있다.

이분탐색은 문제에서 어떻게 적용해야 해결할 수 있을지 생각해내는게 제일 어렵다. 이분탐색을 수행할 수 있는 조건은 “정렬”이 되어있어야 한다. 따라서 기존 주어진 배열을 뭐 어떻게 짤라봐도 불가능하다. 그래서 순차적으로 앞에서부터 보면서 새로운 배열에 값을 “정렬”된 상태로 대입하면 된다.

bisect_left 메서드를 통해 정렬된 배열에 어디 위치에 해당 값이 들어가야 하는지 인덱스를 찾은 후 값을 대입하면 된다. 이렇게 구현할 경우 반환되는 배열이 정확히 LIS를 찾을 수는 없지만 LIS의 크기는 찾을 수 있다. 자세한 알고리즘은 LIS 포스트에 작성했다.

구현

---

import sys
from bisect import bisect_left

def solution(n):
    result = [0]
    for s in seq:
        idx = bisect_left(result, s)
        if idx == len(result):
            result.append(s)
        else:
            result[idx] = s
    return len(result) - 1

if __name__ == "__main__":
    N = int(sys.stdin.readline().rstrip())
    seq = [i for i in map(int, sys.stdin.readline().rstrip().split())]
    print(solution(N))