[백준 12015] LIS O(n log n) 알고리즘

문제 링크 : https://www.acmicpc.net/problem/12015

 

LIS는 최장 증가 부분 수열을 의미한다. 주어진 수열에서 숫자를 몇개 빼서 가장 긴 증가 수열을 만드는 것이 규칙이다.

 

[0, 1, 2, 0, 5, 4]에 대해서 LIS를 찾는다고 하면, [0, 1, 2, 5] 또는 [0, 1, 2, 4]가 답이다.

 

부분 수열이 인덱스 i에서 끝날 때 LIS 수열의 길이를 lis[i]라고 할 때, 여기에 dp를 적용하면 O(N^2) 해법을 쉽게 떠올릴 수 있다.

def dp(arr):
    N = len(arr)
    lis = [1] * N
    for i in range(N): # 0부터 i까지 구간에서 부분수열의 최대 길이를 구한다.
        for k in range(i):
            if arr[i] > arr[k]: 
                # [...3] 수열 뒤에 [... 8] 가 온다면, 3뒤에 8을 붙여서 길이를 늘릴 수 있다.
                # 위 예시에서 3의 인덱스가 k이고 8의 인덱스가 i인 상황이다.
                lis[i] = max(lis[i], lis[k] + 1)
    
    return max(dp)

 

여기서 한 단계 나아가 lis[i]를 찾아내는 방법을 O(log n)으로 단축할 수 있다.

bound라는 배열을 새로 만들어서, 자기자신 x보다 작은 수의 갯수를 count라고 할 때, bound[count] = x 로 표시하면 된다.

예시로 보자.

 

Q) [1, 5, 2, 6, 3, 7] 에서 LIS 수열의 길이를 구하라.

탐색 index	bound	설명
0	[1]	index 0 이하에서 1보다 작은 수는  0개이다. b[0] = 1로 표현된다.
1	[1, 5]	index 1 이하에서 5보다 작은수는 1개이다. b[1] = 5 로 표현된다. b[0]=1 이므로 1보다 작은수는 여전히 0개이다.
2	[1, 2]	index 2 이하에서 2보다 작은 수는 1개이다. b[1] = 2 로 표현된다.
3	[1, 2, 6]	index 3 이하에서 6보다 작은 수는 2개이다. b[2] = 6으로 표현된다.
4	[1, 2, 3]	index 4 이하에서 3보다 작은 수는 2개이다. b[2] = 3으로 표현된다.
5	[1, 2, 3, 7]	index 5 이하에서 7보다 작은 수는 3개이다. b[3] = 7로 표현된다.

 

배열 bound의 마지막 요소는 반드시 배열안에 존재하는 것이 보장되어있으므로,

(bound의 마지막 index + 1), 즉 len(bound)가 부분수열의 길이가 된다.

 

사실 bound를 업데이트 하기 위해 O(n)의 선형 탐색을 하면 여전히 LIS 길이를 찾는 알고리즘은 O(n^2)의 시간복잡도를 가진다.

bound가 정렬되어있음을 활용해서 이진 탐색을 적용해야 전체 알고리즘의 길이를 O(n log n)으로 만들 수 있다.

 

위 로직을 구현해보면 아래와 같다.

from bisect import bisect_right  # 이진탐색 라이브러리

def boundary(arr):
    N = int(arr)
    bound = [arr[0]]

    for i, num in enumerate(arr):
        if num > bound[-1]:
            bound.append(num)
        elif num < bound[-1]:
            # num보다 큰 수 중 가장 작은 수와 교체
            bi = bisect_right(bound, num)

            # bound 속의 수가 유일하도록 예외처리
            if bi - 1 >= 0 and bound[bi - 1] == num:
                continue
            else:
                bound[bi] = num
    	# print(f'arr[{i}] {num} | {bound}') # 출력보시면 이해가 쉬워요
    return len(bound)