가장 긴 증가하는 부분 수열-2 O(N log N) 알고리즘

가장 긴 증가하는 부분 수열 문제다.

이 문제는 풀면서 고민을 많이 했던 문제이다. N의 범위가 1000000 미만인데, 이렇게 되면 O(N^2)알고리즘으로는 택도 없다. 

먼저 O(N^2)알고리즘을 연구해보자.

n = int(input())
a = list(map(int, input().split()))
dp = [1 for i in range(n+1)]
for i in range(n):
    for j in range(i):
    	if a[j] < a[i]:
            dp[i] = max(dp[i], dp[j]+1)
print(max(dp))

여기에서 시간을 잡아먹는 요인은 무엇일까?

바로 a[j] < a[i]인 부분을 판별하기 위해 반복문을 돌리는 것이다.

 

만약 a[j] < a[i]인 것을 어떤 형식으로 기록해 놓는다면 어떨까?

이 아이디어를 통해 LIS 알고리즘을 보완할 수 있다.

n = int(input())
a = list(map(int, input().split()))
INF = 10000000000
d = [INF for i in range(n+1)]
d[0] = 0
dp = [1 for i in range(n+1)]
for i in range(n):
    hi = n
    low = 0
    for j in range(100):
        mid = (hi+low) // 2
        if d[mid] < a[i]:
            low = mid
        else:
            hi = mid
	dp[i] = mid+1
    d[mid+1] = min(a[i], d[mid+1])
print(max(dp))

여기에서는 d라는 배열이 중요하다. 이는 현재까지 구한 dp중, dp[i] = x일 때 d[x] = (dp[i] = x를 만족하는 i 중 a[i]의 최소)를 저장해 놓은 배열이다. 이 배열은 오름차순으로 저장될 수 밖에 없고,따라서 이 배열은 a[j] < a[i]일 때의 최대의 길이를 이진 탐색으로 쉽게 찾을 수 있게 한다.

이렇게, 이진 탐색을 통해 a[j] < a[i]이면서 최대의 값을 찾을 수 있다.

보통 이진 탐색은 정렬이 된 배열에서

(어떤 조건이면서, 최대/최소의 값을 찾아라)하는 형식의 문제일 때 유용하다.

이를 구현하면 위의 코드와 같이 되는 것이다.

많이 알려져 있는 LIS 문제이기도 하지만 아무 것도 모르는 상태에서 아이디어를 얻기에는 매우 힘든 문제라고 느껴졌다.