✏️ 문제
12015번: 가장 긴 증가하는 부분 수열 2
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)
www.acmicpc.net
✏️ 풀이
11053 가장 긴 증가하는 부분 수열 1과 뭐가 다를까?
다른 것은 단 하나. N의 조건 범위이다. 11053에서는 1<=N<=1000이었다. 보통 연산 수행 횟수가 약 1억번 (100,000,000)을 넘어가면 수행시간이 1초를 넘어간다고 한다. 따라서 O(N^2)정도면 거뜬하게 연산이 가능하다.
백준 11053: 가장 긴 증가하는 부분 수열 해설- python
✏️ 문제 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴
duckracoon.tistory.com
11053 에서는 시간복잡도가 O(N^2)이었다. 하지만 여기서는 O(N^2)의 시간 복잡도에서는 1초안에 연산을 수행하지 못할거다. 즉 O(NlogN) 정도의 알고리즘을 만들어야한다.
11053에서의 DP를 이용한 알고리즘에서는 현재위치 이전의 모든 수를 반복하며 훑어보게된다. 이런 과정을 없애려면 어떻게해야할까?
파이썬의 bisect 모듈을 이용해 이진탐색을 진행했다.
dp[]의 마지막 원소가 현재 진입하려는 원소보다 작으면 맨 뒤에 그냥 붙여주면 되고, 아니라면 이진탐색으로 해당 위치의 원소를 교체해준다.
from bisect import bisect_left, bisect_right
n=int(input())
A=list(map(int,input().split()))
dp=[0]
for x in A:
if dp[-1]<x:
dp.append(x)
else:
dp[bisect_left(dp,x)]=x
print(len(dp)-1)