최장 증가 부분 수열(LIS)

최장 증가 부분 수열이란?

최장 증가 부분 수열(LIS, Longest Increasing Subsequence)은 어떤 수열이 주어졌을 때, 그 안에서 순서를 유지하면서 증가하는 가장 긴 부분 수열을 찾는 알고리즘이다. 여기서 말하는 "부분 수열"은 연속일 필요는 없지만 순서는 유지되어야 한다. 예를 들어, 수열이 [10 20 10 30 20 50] 이라면 최장 증가 부분 수열은 [10 20 30 50]이다. 최장 증가 부분 수열은 여러 개가 존재할 수 있다.

 

최장 증가 부분 수열은 다음과 같이 두 개의 방법으로 구현할 수 있다.

---

1. 동적 계획법(DP)

각 위치에서 끝나는 LIS 길이를 계산해 나가는 방식이다. 즉, DP[i]는 다음과 같이 정의된다.

dp[i] : arr[i]를 마지막 값으로 가지는 LIS의 길이

arr[i]가 어떤 증가 부분 수열의 마지막 값이 되기 위해서는 해당 부분 수열의 마지막 값이 arr[i] 보다 작아야 한다. 따라서 arr[i]를 마지막 값으로 가지는 LIS의 길이는 arr[i]가 들어갈 수 있는 증가 부분 수열 중 가장 긴 수열의 길이에 1을 더한 값이 된다.

예제

아래와 수열에서 DP를 사용해 LIS를 찾아보자. index = 1부터 시작하는 것에 주의한다.

index = 1일 때

arr[0] 뒤에 붙을 수 있다. 따라서 dp[1] = dp[0] + 1 = 1이 된다.

index = 2일 때

인덱스가 2보다 작은 원소에서 부분 수열의 길이가 가장 긴 arr[1] 뒤에 붙을 수 있다. 따라서 dp[2] = dp[1] + 1 = 2가 된다.

index = 3일 때

인덱스가 3보다 작은 원소에서 부분 수열의 길이가 가장 긴 arr[0] 뒤에 붙을 수 있다.(증가 수열이므로 arr[1]과 같이 값이 같아도 안된다.) 따라서 dp[3] = dp[0] + 1 = 1이 된다.

index = 4일 때

인덱스가 4보다 작은 원소에서 부분 수열의 길이가 가장 긴 arr[2] 뒤에 붙을 수 있다. 따라서 dp[4] = dp[2] + 1 = 3이 된다.

index = 5일 때

인덱스가 5보다 작은 원소에서 부분 수열의 길이가 가장 긴 arr[1] 또는 arr[3] 뒤에 붙을 수 있다. 따라서 dp[5] = dp[1 또는 3] + 1 = 2가 된다.

index = 6일 때

인덱스가 6보다 작은 원소에서 부분 수열의 길이가 가장 긴 arr[4] 뒤에 붙을 수 있다. 따라서 dp[6] = dp[4] + 1 = 4가 된다.

이렇게 모두 계산이 끝난 후 dp 배열에서 가장 큰 값을 찾으면 그게 LIS의 길이이다. 즉, 예제 수열에서 LIS의 길이는 4이다.

코드

위 예제와 같이 나보다 인덱스가 작은 원소를 탐색하며 ① 나보다 값이 작고 ② 부분 수열의 길이가 가장 긴 원소를 찾는다. 2중 for문을 사용하기 때문에 시간복잡도는 $ O(N^2) $ 이다.

for (int i = 0; i < N; ++i) {
	for (int j = 0; j < i; ++j) {
    	if (arr[j] < arr[i]) {
        	dp[i] = max(dp[i], dp[j] + 1);
        }
    }
}

---

2. 이분 탐색

DP를 사용하는 방법은 매번 arr[0] ~ arr[i - 1]을 탐색해야 한다는 단점이 있다. 이를 극복하기 위해 LIS 리스트를 하나 만든다고 생각해보자. 이 리스트는 현재까지의 LIS를 만드는 데 쓰인 숫자들 중 가장 작은 숫자만 유지하는 리스트이다. 실제 수열을 구하는 것은 아니고 길이만 빠르게 구할 때 사용한다. 왜 길이만 구할 수 있는지는 예제를 진행하며 설명한다.

예제

아래 수열에 대해 생각해보자.

초기 상태

초기상태의 LIS 리스트는 비어있다.

3일 때

LIS가 비어있으므로 3은 그냥 넣어준다.

2일 때

LIS에서 2가 들어갈 위치를 찾는다. 위치를 찾을 때 바로 이분탐색 알고리즘을 사용한다. lower_bound를 사용해 나보다 큰 값 중 가장 작은 값을 찾고, 그 값을 나로 교체해준다. 더 작은 값으로 시작하는 증가 수열이 더 많은 선택지를 줄 수 있기 때문이다.

2보다 큰 수 중 가장 작은 값은 3이다. 따라서 3을 2로 교체해준다.

6일 때

LIS에서 6이 들어갈 위치를 찾는다. LIS에 있는 모든 수보다 6이 더 크므로 뒤에 넣어준다.

4일 때

LIS에서 4가 들어갈 위치를 찾는다. 4보다 큰 수 중 가장 작은 값은 6이다. 따라서 6을 4로 교체해준다.

5일 때

LIS에서 5가 들어갈 위치를 찾는다. LIS에 있는 모든 수보다 5가 더 크므로 뒤에 넣어준다.

1일 때

LIS에서 1이 들어갈 위치를 찾는다. 1보다 큰 수 중 가장 작은 값은 2이다. 따라서 2를 1로 교체해준다.

 

원본 수열을 보면 알겠지만 1 4 5는 진짜 LIS는 아니다. LIS는 [3 4 5] 또는 [2 4 5] 이지만 우리는 길이만 필요하기 때문에 상관없다.

코드

 시간복잡도는 $ O(NlogN) $ 이다.

for (int i = 0; i < arr.size(); ++i) {
	int num = arr[i];
    
    // num이 들어갈 위치를 찾는다.
    auto it = lower_bound(LIS.begin(), LIS.end(), num);
    
    if (it == lis.end()) {
    	// num이 가장 큰 경우 뒤에 추가
        LIS.push_back(num);
    } else {
    	*it = num;
    }
}