본문 바로가기

카테고리 없음

[백준 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)

 

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

어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다.

namu.wiki

 

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

 

 

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