백준(12015) - 가장 긴 증가하는 부분 수열2 Python

백준(12015) - 가장 긴 증가하는 부분 수열2

문제풀이: 이분 탐색, 파이썬

해결방법

예시)

# 입력 #
6
10 20 10 30 20 50

# 출력결과 #
4

• 이 문제 시리즈는 LIS를 구하는 방법이다

LIS (Longest Increasing Subsequence )

최장 증가수열 : 어떤 수열에서 특정 부분을 지워서 만들어낼 수 있는 증가 부분 수열 중 가장 긴 수열

• LIS를 구현하는 방법은 이진 탐색과 동적 계획법이 있지만 동적 계획법은 시간복잡도가 O(n^2) 이 된다.
• 따라서 이진 탐색방법으로 기억해두고 풀어야 한다. O(NlogN)

import bisect
import sys
input = sys.stdin.readline

x = int(input())
data = list(map(int, input().split()))

dp = []
dp.append(data[0])

for i in range(x):
    if data[i] > dp[-1]:
        dp.append(data[i])
    else:
        index = bisect.bisect_left(dp, data[i])
        dp[index] = data[i]
print(len(dp))