파이썬 bisect

import bisect

bisect는 이진탐색 알고리즘을 구현한 모듈

bisect.bisect 함수는 정렬된 리스트에 값을 삽입할 때 정렬을 유지할 수 있는 인덱스를 리턴

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

dp 문제로 분류되어있지만 bisect으로 풀어봤다

bisect_left(a, x)

• 정렬된 순서를 유지하면서 리스트a에 데이터x를 삽입할 가장 왼쪽 인덱스를 찾는다

예를들어 주어진 인풋이 이렇게 있을때 "10 20 10 30 20 50"
리스트[0], 리스트[1] 번까지는 순서대로 삽입될것이고 (dp = [10,20])
리스트[2]번을 만났을때는 이전위치의 값보다 작기때문에 리스트[2]번을 삽입할 인덱스를 찾으면 된다

idx = bisect.bisect_left(dp, arr[i])

이런경우 idx 는 0이 된다 (현재 dp[0]번이 10임)

bisect를 이용한 풀이

import sys
import bisect

n = int(input())

seq = list(map(int, sys.stdin.readline().split()))
dp = [seq[0]]

for i in range(1, n):
    if seq[i] > dp[-1]:
        dp.append(seq[i])
    else:
        idx = bisect.bisect_left(dp, seq[i])
        dp[idx] = seq[i]

print(len(dp))