https://www.acmicpc.net/problem/12015
12015번: 가장 긴 증가하는 부분 수열 2첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)www.acmicpc.net
예전에 풀어봤던 문제인데, 풀어야 하는 방식이 다르다
예전에는 모든 배열을 돌면서 n^2의 시간복잡도로 풀었는데, 여기서는 시간초과가 난다.
따라서 2분탐색을 통해서 시간복잡도를 nlogn으로 줄여야 한다.
먼져, 원 수열을 반복문에 넣어 기본적으로 부분 수열을 구해나가는데,
현재 보고있는 원소가
만일 현재 구한 부분수열의 마지막원소(젤큼) 보다 크다면, 그냥 부분수열에 append시켜주면 된다.
만일 작다면, (부분 수열 중 원소보다 큰 수 중 가장 작은 수) 에 원소를 넣는다.
이를 반복하면서 lis의 총 길이를 구하면 된다.
직접 이분탐색 구현 코드
n = int(input())a = list(map(int, input().split()))lis = [0]for i in a:
if lis[-1] < i: # 만일 lis의 마지막 숫자가 i보다 작을 경우 lis.append(i) # 추가
else: # 이분탐색해서 가장 잘 어울리는 위치에 넣기 start, end = 0, len(lis)
while start < end: mid = (start + end) // 2
if lis[mid] < i: start = mid + 1 else:
end = mid lis[start] = iprint(len(lis) - 1)bisect 모듈 이용 코드
from bisect import bisect_leftn = int(input())
a = list(map(int, input().split()))res = [0]for i in a: if res[-1] < i:
res.append(i) else: res[bisect_left(res, i)] = i
print(len(res)-1)