[BOJ] 12015 - 가장 긴 증가하는 부분 수열 2

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

12015번: 가장 긴 증가하는 부분 수열 2

import sys
from bisect import bisect_left
n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().rstrip().split()))

dp = [data[0]]
for i in range(1, n):
    if data[i] > dp[-1]:
        dp.append(data[i])

    else:
        idx = bisect_left(dp, data[i])
        dp[idx] = data[i] # 수열이 유지되는 위치의 원소와 교환

print(len(dp))

이 문제는 [BOJ] 18353 - 병사 배치하기 에서 처음 다룬 '가장 긴 증가하는 부분 수열(LIS)' 알고리즘의 시간 복잡도가 개선된 방법으로 풀 수 있다. 병사 배치하기 문제에서 사용한 방법은 이중 for 문을 이용하여 O(N^2)의 시간 복잡도를 가졌지만 이 방법은 이진 탐색을 이용하여 O(N log N)의 시간 복잡도를 가진다.

 

아이디어는 새로운 리스트에 가장 긴 증가하는 수열이 되도록 원소들을 담은 후 그 길이를 출력하는 것이다. 코드를 보면 현재 dp의 가장 큰 값보다 검사하는 원소가 크다면 삽입하고 그렇지 않다면 수열이 유지되는 위치의 원소와 교환한다. 이때 파이썬에서 이진 탐색을 통해 해당 원소가 들어갈 수 있는 가장 왼쪽 인덱스를 찾아주는 bisect_left() 메서드를 이용하여 교환할 인덱스를 찾을 수 있다.

 

다만 이 방법은 가장 긴 증가하는 부분 수열의 '길이'를 알 수 있지만 dp에 담긴 원소들이 가장 긴 증가하는 부분 수열을 구성하는 원소가 아니기 때문에 원소를 출력하는 문제에서는 사용할 수 없다.