최장 증가 수열(LIS, Longest Increasing Subsequence) 알고리즘

최장 증가 수열

• 어떠한 수열에서 오름차순으로 증가하는 가장 긴 부분 수열을 의미한다.
• 이 때, 부분 수열의 각 수는 서로 연속할 필요는 없다.
• 아래 수열에서 최장 증가 수열을 찾으면 아래와 같다.

• {10, 20, 30, 50} 는 전체 수열 중 오름차순으로 증가하는 가장 긴 부분 수열이다.

 

문제의 풀이 방법

1. Dynamic Programming(동적 계획법)
2. 이진 탐색

 

Dynamic Programming(동적 계획법)

x : 수열 A의 크기
arr : 수열 A를 이루고 있는 A(i)를 담은 배열
dp : arr[i]를 마지막 원소로 가질 때 가장 긴 증가하는 부분 수열의 길이

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

• 이 풀이법의 시간 복잡도는 O(N^2)

-> 이 경우 난이도가 올라가면 시간초과가 뜬다.

이진 탐색

• dp[i]를 구하기 위해 dp[0] ~ dp[i - 1] 의 최댓값을 알고 있다면 반복하지 않아도 되지 않을까?

-> 이때 python의 bisect를 사용!

import bisect

x = int(input())
arr = list(map(int, input().split())
dp = arr[0]
for i in range(x) :
	if arr[i] > dp[-1] :
    	dp.append(arr[i])
    else :
    	idx = bisect.bisect_left(dp, arr[i])
       dp[idx] = arr[i]
print(len(dp))

• 이 풀이법의 시간 복잡도는 O(NlogN))