[백준] 12015번 - 가장 긴 증가하는 부분 수열 2 (파이썬)

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

# 가장 긴 증가하는 부분 수열 2
import sys
import bisect
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))

result = []
result.append(arr[0])

for i in range(1, N):
    if arr[i] > result[-1]:
        result.append(arr[i])
    else:
        index = bisect.bisect_left(result, arr[i])
        result[index] = arr[i]

print(len(result))

 

이진탐색, bisect

1. 전체 리스트를 돌면서

    - result의 마지막 원소보다 크면 append를 해준다

    - 작으면 bisect_left를 이용하여 해당 인덱스의 값을 바꿔준다

2. result배열의 길이를 출력

 

[11053] 가장 긴 증가하는 부분 수열 : https://2hs-rti.tistory.com/37

[백준] 11053번 - 가장 긴 증가하는 부분 수열 (파이썬)

DP로 풀 수 있던 1번과는 다르게 데이터의 범위가 늘어나서 시간초과, 이진탐색으로 풀어야한다

 

파이썬에서는 이진탐색에 용이한 bisect를 제공한다.

bisect_left(리스트, 값) = 리스트에 해당 값이 들어갈 알맞은 위치들 중에서 가장 왼쪽 인덱스를 반환

단, 리스트는 정렬되어 있어야 한다.