최장 증가 부분 수열(LIS) 알고리즘

LIS(Longest increasing Subsequence)란, 가장 긴 증가하는 부분 수열이다.

 

예를 들어,

[6, 2, 5, 1, 7, 4, 8, 3] 이라는 배열이 있을 경우, LIS는 [2, 5, 7, 8]이 된다.

증가하는 부분 수열 중 가장 긴 것이기 때문.

 

 

LIS를 풀기 위한 가장 일반적인 방법은 DP를 이용하는 것이다.

dp = [1]*n
for i in range(n): 
	for j in range(i): #첫번째 요소부터 i번째까지 위와 비교
    	if arr[i] > arr[j]: #뒤에 있는 요소(arr[i])가 크면
        	dp[i] = max(dp[i], dp[k]+1)
        	

위 알고리즘의 시간복잡도는 O(n^2)을 갖게 됩니다.

 

시간복잡도를 개선하기 위해서는 이분탐색을 활용합니다.

주어진 배열의 인덱스를 하나씩 살펴보면서 그 숫자가 들어갈 위치를 이분탐색으로 탐색해서 넣습니다.

이분탐색은 일반적으로 시간복잡도가 O(log n)으로 알려져있으므로,

이분탐색을 활용한 LIS의 길이 구하기의 시간복잡도는 O(nlog n)으로 개선시킬 수 있습니다.

memorization = [0]
arr = [0] + 원래 배열

for case in cases:
	if memoization[-1] < case:
    	memoization.append(case)
    else:
    	left = 0
        right = len(memoization)
        
        while left<right:
        	mid = (left+right)//2
            
            if memoization[mid] < case:
            	left = mid + 1
            else:
            	right = mid
     	memoization[right] = case

[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를 이루는 요소와 무관하다는 것이다.