최장 증가 부분 수열(LIS; Longest Increasing Subsequence) - DP, 이분 탐색 (C++)

LIS(최장 증가 부분 수열)이란?

LIS란 말 그대로 어떤 수열의 부분 수열 중, 가장 긴 증가하는 부분 수열을 의미한다.

예를 들어, {10, 20, 10, 30, 20, 50} 인 수열의 LIS는 {10, 20, 30, 50} 이고, 길이는 4이다.

 

어떻게 구할까?

1. 완전 탐색 - $O(2^N)$

모든 부분 수열을 구한 후, 증가하는 부분 수열 중 가장 긴 수열을 구하는 방법이다.

말 그래도 모든 부분 수열을 구해야 하므로, $O(2^N)$의 시간이 걸린다.

 

2. 다이나믹 프로그래밍 - $O(N^2)$

$A_i$을 마지막으로 가지는 가장 긴 증가하는 부분 수열의 길이를 $DP[i]$라고 해보자.

1. 각 원소별로, 해당 원소($i$)보다 앞선 원소들($j$)을 탐색한다.
   • $A_i > A_j$인 원소들 중 $DP[j]$가 가장 큰 원소를 찾으면 된다.
2. $DP[i]$를 $DP[j] + 1$로 갱신한다. 

 

이중 반복문을 이용해 쉽게 구현할 수 있다. 아래 백준 11053번 문제의 코드를 보면서 살펴보자.

(arr[0] = dp[0] = 0으로 두고 구현하였다.)

#include <bits/stdc++.h>

using namespace std;

int n, answer = 0;
int arr[1001];
int dp[1001] = {0, };

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	for(int i = 0; i < n; i++) {
		cin >> arr[i + 1];
	}

	for(int i = 1; i < n + 1; i++) {
		// 앞의 원소들 탐색
		for(int j = 0; j < i; j++) {
		    // 해당 원소보다 크면
			if(arr[i] > arr[j]) {
			    // dp 갱신
			    dp[i] = max(dp[i], dp[j] + 1);
			    answer = max(answer, dp[i]);
			}
		}
	}
	
	cout << answer;
}

 

이렇게 하면 LIS의 길이를 구할 수 있다.

LIS에 속한 원소를 구하려면, $DP$를 거꾸로 살펴보면 된다.

int count = answer;
for(int i = n + 1; i > 0; i--) {
    if(count == dp[i]) { // 현재 길이랑 해당 원소까지의 LIS 길이가 같으면
        lis[--count] = arr[i]; // LIS 배열에 추가
    }
}

// 원래 순서대로 출력
for(int i = 0; i < answer; i++) {
    cout << lis[i] << " ";
}

위 코드를 추가하기만 하면 백준 14002번의 해답이 된다.

 

3. 이분 탐색 - $O(Nlog_2{N})$

앞선 방법에서 $A_i > A_j$인 원소들 중 $DP[j]$가 가장 큰 원소를 찾는 과정은 $O(N)$의 시간이 걸린다.

이분 탐색을 활용하면 이 시간을 $O(log_2{N})$으로 줄일 수 있다.

 

새로운 배열 $B$를 생각해보자. $B[i]$는 길이가 $i$인 증가 수열들 중 마지막 값의 최소값을 의미한다.

따라서 $B$를 완성했을 때 $B$의 크기가 곧 LIS의 길이가 된다. (해당 길이까지의 증가 수열이 만들어졌음을 나타내기 때문)

 

그렇다면 $B$는 어떻게 만들 수 있을까?

$A_i$를 순회하며 해당 원소를 $B$의 적합한 자리에 넣어주면 되는데, 이는 Lower Bound를 이용해 빠르게 구할 수 있다.

 

아래 백준 12015번 문제의 코드를 살펴보자.

#include <bits/stdc++.h>

using namespace std;

int n, tmp, answer = 0;
int lis[1000001] = {0};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	for(int i = 0; i < n; i++) {
		cin >> tmp;
		auto lb = lower_bound(lis + 1, lis + answer + 1, tmp);
		*lb = tmp;
		if (lb == lis + answer + 1) answer++;
	}
	
	cout << answer;
}

 

변수 이름을 lis로 짓긴 했으나, 해당 배열이 LIS는 아니다.

LIS를 구하려면 $DP$때와 같이 별도의 저장 및 역추적이 필요하다.

int count = answer;
for(int i = n + 1; i > 0; i--) {
    if(count == dp[i]) {
        lis[--count] = arr[i];
    }
}

for(int i = 0; i < answer; i++) {
    cout << lis[i] << " ";
}

위 코드를 추가하기만 하면 백준 14003번의 해답이 된다.

 

관련 문제 (BOJ)

LIS는 구현 자체는 간단하나 LIS를 적용하는 문제임을 알아내기 어려운 경우가 많다.

아래 문제를 풀어보는 것도 좋지만, 우연히 문제를 풀다가 마주하는 것이 더 좋다.

• [2352] 반도체: LIS 문제임을 파악하고 LIS의 길이를 구하면 되는 문제
• [13711] LCS 4: LCS인 척하는 LIS 문제
• [2532] 먹이사슬: LIS 응용 문제