[백준 12015번] 가장 긴 증가하는 부분 수열 2 (Python3)

import sys
input = sys.stdin.readline

def binary(num):
  l = len(DP)
  start,end = 0,l-1
  while True:
    if end-start < 2:
      if DP[end]<num:
        return end
      return start
    mid = (end+start)//2
    if DP[mid] == num:
      return mid-1
    else:
      if DP[mid] > num:
        end = mid
      else:
        start = mid

N = int(input())

seq = list(map(int,input().split()))

DP = [0]

for i in range(N):
  num = seq[i]
  l = binary(num)+1
  if l > len(DP)-1:
    DP.append(num)
  else:
    if DP[l] > num:
      DP[l] = num

print(len(DP)-1)

 

가장 긴 증가하는 부분 수열 1과 같은 방식인 O(N^2)으로 제출하면 시간초과가 나게 된다. LIS라는 알고리즘을 사용해야하는 문제이다. 나무위키에서 LIS에 대해서 공부한 뒤 문제를 풀 수 있었다.

최장 증가 부분 수열 - 나무위키 (namu.wiki)

최장 증가 부분 수열 - 나무위키

 

이진탐색을 나는 while로 직접 구현하였다. 그런데 알고보니 bisect 라이브러리를 이용하면 훨씬 쉽게 이진탐색이 구현 가능하다고 한다. 이에 대해서도 알아보아야겠다.

 

 

오늘의 교훈) bisect에 대해서 알아보자