[백준] 12015 – 가장 긴

by

문제

#12015: 최장 증가 서브 시퀀스 2(acmicpc.net)

12015: 최장 증가 서브 시퀀스 2

'추천 관련글,

첫 번째 라인은 시퀀스 A의 크기 N(1 ≤ N ≤ 1,000,000)을 제공합니다.
두 번째 줄에는 시퀀스 A를 구성하는 Ai가 포함됩니다.
(1 ≤ Ai ≤ 1,000,000)

www.acmicpc.net

시간적 복잡성

시퀀스가 최대 1,000,000이므로 11053(가장 길게 증가하는 하위 시퀀스)을 풀 때 사용한 것과 동일한 코드를 사용하면 시간 복잡도가 $O(N^2)$이고 시간 초과가 발생합니다.

이 경우 DP 대신 시간 복잡도가 $O(N\log N) $인 이분 검색을 사용해야 합니다.

분할 검색

먼저 가장 작은 수인 0이 첫 번째 수와 비교될 수 ​​있도록 미리 정해져 있다.

입력을 받는 경우에는 두 가지 경우가 있습니다.

– 이전에 입력한 값보다 큰 숫자를 입력한 경우:

입력한 값을 dp에 더합니다.

– 이전에 입력한 값보다 작거나 같은 숫자가 나오는 경우:

dp를 오름차순으로 생각하고 이진 검색으로 입력값을 넣을 수 있는 위치를 찾습니다.

기존 값을 찾은 위치에 붙여넣기 하지 않고 입력한 값으로 변경합니다.

Python에는 두 부분으로 검색을 수행하는 bisect라는 라이브러리가 있어 매우 간결한 코드를 작성할 수 있습니다.


https://dragon-h.2

위 과정에 대한 좋은 글이 있어 이미지로 남깁니다.

from sys import stdin
from bisect import bisect_left
input = lambda : stdin.readline().strip()

N = int(input())
A = list(map(int, input().split()))
dp = (0)

for i in A :
    if dp(-1) < i :
        dp.append(i)
    else :
        dp(bisect_left(dp, i)) = i

print(len(dp) - 1)