백준 12015 : 가장 긴 증가하는 부분수열 2 [파이썬]

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

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

1. 문제 설명

가장 긴 부분수열을 이진탐색으로 푸는 문제

DP를 사용해서 푼다면 시간복잡도(O(n^2)) 때문에 시간 초과가 나온다. 이분 탐색을 사용한다면 O(nlogn)의 시간복잡도로 풀 수 있다.

2. 코드설명

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
lis = [0]

for i in arr:
    if lis[-1]<i:
        lis.append(i)
    else:
        left = 0
        right = len(lis)

        while left < right:
            mid = (right+left)//2
            if lis[mid] < i:
                left = mid + 1
            else:
                right = mid
        lis[right] = i
print(len(lis)-1)

100, 50, 70, 90, 75, 87, 105, 78, 110, 60] 이 배열의 LIS를 구한다고 가정해보면,

LIS는 [50, 70, 75, 87, 105, 110] 로, 길이는 6이 된다.

아래와 같은 순서로 진행된다.

[0] 
[0, 100]
[0, 50]
[0, 50, 70]
[0, 50, 70, 90]
[0, 50, 70, 75]
[0, 50, 70, 75, 87]
[0, 50, 70, 75, 87, 105]
[0, 50, 70, 75, 78, 105]

[0, 50, 70, 75, 78, 105, 110]
[0, 50, 60, 75, 78, 105, 110]

0을 뺀 나머지의 길이를 구하면 LIS의 길이가 된다.

 

이분탐색으로 구한 LIS와 실제 LIS의 값들이 다른 것을 주의깊게 봐야한다.

수열상에서 뒤에 있던 원소가 먼저 들어온 원소보다 lower_bound로 탐색된 최적의 위치가 앞에 있을 수도 있기 때문이다.

따라서 배열에 들어있는 값들은 LIS를 이루는 요소와 무관하다는 것이다.