[두번째 공부] 최장 증가 부분 수열

최장 증가 부분 수열은 LIS라고도 부른다. (LIS: Longest Increasing Subsequence)

 

어떤 임의의 수열이 주어졌을 때, 이 수열에서 몇 개의 수들을 제거하여 부분수열을 만들 수 있다. 이때 만들어진 부분수열 중 일부 혹은 전체가 오름차순으로 정렬된 수열을 '증가 부분 수열'이라 하며 이 중 가장 긴 수열을 최장 증가 부분 수열이라고 한다.

 

LIS의 길이 구하는 문제를 해결하기 위한 알고리즘으로 2가지가 존재한다.

 

1. 첫번째 알고리즘(시간복잡도 O(N^2))

새로운 배열 D를 정의하자. 

D[i]: A[i]를 마지막 값으로 가지는 가장 긴 증가부분수열의 길이

A[i]가 어떤 증가부분수열의 마지막 값이 되기 위해서는 A[i]가 추가되기 전 증가부분수열의 마지막 값이 A[i]보다 작은 값이여야 한다.
따라서 A[i]를 마지막 값으로 가지는 '가장 긴' 증가부분수열의 길이는 A[i]가 추가될 수 있는 증가부분수열 중 가장 긴 수열의 길이에 1을 더한 값이 된다.

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

풀이

n = int(input())
arr = list(map(int,input().split())
dp = [1 for _ in range(n))]

for i in range(n):
	for j in range(i):
    	if arr[i] > arr[j]:
        	dp[i] = max(dp[i],dp[j])

print(max(dp))

2. 두번째 알고리즘(O(NlogN))

두 번째 알고리즘은 첫 번째 알고리즘을 개량한 형태이다. 두 번째 알고리즘은 다음과 같은 의문에서 시작한다.

D[i]를 계산하기 위해 A[0] ~ A[i - 1]를 꼭 다 훑어봐야 하는가?

첫 번째 알고리즘에서 A[0] ~ A[i - 1]를 훑어본 것은 A[i]보다 작은 A[j]를 가지는 j들 중 가장 큰D[j]를 찾기 위함이었다. 여기서 다음과 같은 생각을 이끌어낼 수 있다.

만약 D[j] = k를 만족하는 j 중 A[j]의 값이 가장 작은 j만 어딘가에 저장해 놓으면, 나중에 D[i] (i > j)를 계산할 때 그 값들만 참조하면 D[i]의 값을 쉽게 알 수 있다.

 

예시 문제

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

출처

최장 증가 부분 수열 - 나무위키