[Baekjoon] 12015. 가장 긴 증가하는 부분 수열 2

문제 설명

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입력 1

6
10 20 10 30 20 50

예제 출력 1

4

문제 풀이

# 이분탐색

풀이 과정

• 이 포스팅을 참고하세요.

정리하자면, 이분탐색을 활용하여 LIS를 찾는 방법은 다음과 같습니다.

LIS의 길이를 나타낼 벡터 ans를 정의합니다. 이 때 중요한 것은 ans의 원소가 실제 LIS의 원소는 아니라는 것입니다. 즉, LIS의 길이와 동일하지만 원소는 다릅니다.

첫번째 원소부터 마지막 원소까지 n개의 원소에 대해 for문을 돌면서, 이 원소가 ans 배열의 어디에 들어갈 지를 이분 탐색으로 찾는 것입니다. 이 때 다음의 두 가지에 의해 탐색합니다.

• xs[i] > ans[-1]: ans.append(xs[i])
• ans[k] <= xs[i] < ans[k+1]: ans[k] = xs[i]

이 때 ans 배열의 i번째 원소는 현재까지 만들수 있는 i개의 원소를 가진 IS(증가수열)들 중 i번째 원소가 가장 작은 수열의 i번째 원소입니다.

이로써 뒤에 나올 수들에 대해 계속해서 LIS만큼의 길이를 ans가 유지할 수 있는 것입니다.

전체 코드

import sys
input = sys.stdin.readline
    
N = int(input())
xs = list(map(int,input().split()))
ans = [0] # 나올 수 없는 제일 작은 값으로 초기화

for i in range(N):
    lo,hi = 0,len(ans)-1
    while lo <= hi:
        mid = (lo+hi) // 2
        if ans[mid] < xs[i]:
            lo = mid+1
        else:
            hi = mid-1
    if lo >= len(ans):  ans.append(xs[i])
    else:  ans[lo] = xs[i]
print(len(ans)-1)