가장 긴 증가하는 부분수열이란?
Dynamic Programming으로 풀 수 있는 유명한 문제이다.
정의
어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수를 제거해서 부분수열을 만들 수 있음
이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 가장 긴 부분 수열 (최장 증가 부분 수열)이라고 함
예를 들어, 다음 수열이 주어졌다고 가정해보자
3 5 7 9 2 1 4 8
위 수열에서 몇 개의 수를 제거해 부분수열을 만들 수 있음
3 7 9 1 4 (5, 2, 8 제거)
7 9 2 1 (3, 5, 4, 8 제거)
3 5 7 8 (9, 2, 1, 4 제거)
1 4 8 (3, 5, 7, 9, 2 제거)
이들 중 첫 번째, 두 번째 수열은 일부가 오름차순으로 정렬되어 있음
반면에, 세 번째, 네 번째 수열은 전체가 오름차순으로 정렬되어 있음
위와 같이 일부, 혹은 전체가 오름차순인 수열을 ‘증가 부분 수열’이라고 함
그리고 이런 증가 부분 수열 중 가장 긴 수열을 ‘최장 증가 부분 수열 (LIS)’이라 함
즉, 위 예시에서의 수열의 집합에서는 부분수열 3 5 7 8 가 LIS임
한 수열에서 여러 개의 LIS가 나올 수도 있음
예를 들어 수열
4 1 6 2 7 3 8
에서 부분수열
1 2 3 8
4 6 7 8
은 모두 길이가 4인 LIS임
LIS의 길이 구하기 문제
길이 N인 임의의 수열이 주어졌을 때 그 수열의 LIS의 길이를 구하는 문제를 생각해보자
이 문제를 푸는 알고리즘은 2가지가 있다.
첫 번째 알고리즘 :
새로운 배열 DP를 정의하자
DP[i]의 정의는 다음과 같다.
DP[i] : arr[i]를 마지막 값으로 가지는 가장 긴 증가부분수열의 길이
arr[i]가 어떤 증가부분수열의 마지막 값이 되기 위해서는 arr[i]가 추가되기 전 증가부분수열의 마지막 값이 arr[i]보다 작은 값이여야 함
따라서 arr[i]를 마지막 값으로 가지는 ‘가장 긴’ 증가부분수열의 길이는 arr[i]가 추가될 수 있는 증가부분수열 중 가장 긴 수열의 길이에 1을 더한 값이 됨
수열 arr = 3 5 7 9 2 1 4 8 을 예시로 들어 알고리즘을 살펴보자
(알고리즘의 규칙성을 위해 i = 0일 때를 정의하자. i = 0일때 A[i] = 0, D[i] = 0이다.)
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| arr | 0 | 3 | 5 | 7 | 8 | 2 | 1 | 4 | 8 |
| dp | 0 |
i = 1 일 때를 살펴보자
arr[1] = 3이다.
3은 arr[0] = 0 뒤에 붙을 수 있다. 따라서 dp[1] = dp[0] + 1이다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| arr | 0 | 3 | 5 | 7 | 8 | 2 | 1 | 4 | 8 |
| dp | 0 | 1 |
i = 2 일 때를 살펴보자
arr[2] = 5이다.
arr[0] = 0, arr[1] = 3 뒤에 붙을 수 있다.
이때, dp[0] = 0, dp[1] = 1 중에서 dp[1] = 1이 가장 크다. 이 말은 A[1] = 3을 가장 마지막 값으로 가지는 증가부분수열의 길이가 가장 길다는 뜻이다.
A[2]가 가장 긴 증가부분수열 뒤에 붙는 게 더 긴 증가부분수열을 만들 수 있다. 따라서 dp[2] = dp[1] + 1 = 2이다
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| arr | 0 | 3 | 5 | 7 | 8 | 2 | 1 | 4 | 8 |
| dp | 0 | 1 | 2 |
i = 3 일 때를 살펴보자
arr[3]=7이다.
arr[0]=0, arr[1]=3, arr[2]=5 뒤에 붙을 수 있다.
이때 dp[0]=0, dp[1]=1, dp[2]=2에서 dp[2]가 가장 크다.
따라서, dp[3] = dp[2] + 1 = 3이 된다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| arr | 0 | 3 | 5 | 7 | 8 | 2 | 1 | 4 | 8 |
| dp | 0 | 1 | 2 | 3 |
i = 4 일 때를 살펴보자
arr[4] = 8
arr[0]=0, arr[1]=3, arr[2]=5, arr[3]=7 뒤에 붙을 수 있다.
이때 dp[0]=0,dp[1]=1,dp[2]=2, dp[3]=3에서 dp[3]이 가장 크다.
따라서 dp[4]= dp[3] + 1 = 4이다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| arr | 0 | 3 | 5 | 7 | 8 | 2 | 1 | 4 | 8 |
| dp | 0 | 1 | 2 | 3 | 4 |
i = 5 일 때를 살펴보자
arr[5] = 2이다.
arr[0]=0 뒤에 붙을 수 있다.
이때 dp[0] =0
따라서 dp[5] =dp[0] + 1 = 1이다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| arr | 0 | 3 | 5 | 7 | 8 | 2 | 1 | 4 | 8 |
| dp | 0 | 1 | 2 | 3 | 4 | 1 |
i = 6 일 때를 살펴보자
arr[6] = 1 이다
arr[0] = 0 뒤에 붙을 수 있다.
이때 dp[0] = 0
따라서 dp[6] = dp[0] + 1 = 1이다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| arr | 0 | 3 | 5 | 7 | 8 | 2 | 1 | 4 | 8 |
| dp | 0 | 1 | 2 | 3 | 4 | 1 | 1 |
i = 7 일 때를 살펴보자
arr[7] = 4
arr[0] = 0, arr[1]= 3, arr[5] = 2 뒤에 붙을수 있다.
이때 dp[0] = 0 , dp[1]= 1, dp[5]=1
따라서 dp[7] = dp[1] or dp[5] + 1 = 2이다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| arr | 0 | 3 | 5 | 7 | 8 | 2 | 1 | 4 | 8 |
| dp | 0 | 1 | 2 | 3 | 4 | 1 | 1 | 2 |
마지막 i = 8 일 때를 살펴보자
arr[8] = 8이다.
arr[0] = 0, arr[1]=3, arr[2]=5, arr[3]=7, arr[5]=2, arr[6]=1, arr[7]=4 뒤에 붙을 수 있다.
이때 dp[3]=3이 제일 크므로
dp[8]= dp[3] + 1 = 4이다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| arr | 0 | 3 | 5 | 7 | 8 | 2 | 1 | 4 | 8 |
| dp | 0 | 1 | 2 | 3 | 4 | 1 | 1 | 1 | 4 |
이렇게 배열 dp를 다 완성했다.
dp의 값들 중 가장 큰 값 dp[4] = dp[8] = 4이므로
배열 arr = 3 5 7 8 2 1 4 8의 LIS의 길이는 4이다.
이 알고리즘은 N개의 수들에 대해 자기 자신 전의 모든 수를 다 훑어봐야 하므로 의 시간복잡도를 가지는 알고리즘이 된다.
코드
#include<iostream>
#include<algorithm>
using namespace std;
const int SIZE = (int)1e3 + 1;
int arr[SIZE];
int dp[SIZE];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> arr[i];
}
for (int i = 1; i <= N; i++) {
dp[i] = dp[0] + 1;
for (int j = 1; j < i; j++) {
if (arr[j] < arr[i]) {
dp[i] = max(dp[i], dp[j] +1);
}
}
}
int sol = dp[0];
for (int i = 1; i <= N; i++) {
sol = max(sol, dp[i]);
}
cout << sol <<'\n';
return 0;
}두 번째 알고리즘 :
두 번째 알고리즘은 첫 번째 알고리즘을 개량한 형태이다.
이 알고리즘은 다음과 같은 의문에서 시작함
dp[i]를 계산하기 위해 arr[0] ~ arr[i - 1]를 꼭 다 훑어봐야 하는가?
첫 번째 알고리즘에서 arr[0] ~ arr[i-1]를 훑어보는 것은 arr[i] 보다 작은 arr[j]를 가지는 j들 중에서 가장 큰 dp[j]를 찾기 위함이었다. 여기서 다음과 같은 생각을 이끌어낼 수 있다.
만약 dp[j] = k를 만족하는 j 중 arr[j]의 값이 가장 작은 j만 어딘가에 저장해 놓으면, 나중에 dp[i] ( i > j )를 계산할 때 그 값들만 참조하면 dp[i]의 값을 쉽게 알 수 있다.
마찬가지로 수열 arr = 3 5 7 9 2 1 4 8 을 예시로 알고리즘을 살펴보자
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| arr | 0 | 3 | 5 | 7 | 8 | 2 | 1 | 4 | 8 |
| dp | 0 |
위 표에 대해 하나의 표를 더 만들어서 생각해보자
| dp[i] | 0 |
|---|---|
| arr[i] | 0 |
이 표는 dp[i] = k인 값들 중 arr[i]의 값이 가장 작은 값을 계속 저장한다. 이 표의 이름을 X라고 하자.
i = 1일 때를 살펴보자
arr[i] = 3이다.
이 때 X를 살펴보면 가장 마지막 arr[i]의 값이 0이고, 이는 3보다 작다. 이 말은 현재 arr[1] 앞의 수들로 만든 가장 긴 증가부분수열 중 마지막 값이 0인 증가부분수열이 있다는 것이다.
그리고 arr[1]을 그 뒤에 붙일 수 있다. 따라서 dp[1] = 0 + 1 = 1이다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| arr | 0 | 3 | 5 | 7 | 8 | 2 | 1 | 4 | 8 |
| dp | 0 | 1 |
| dp[i] | 0 | 1 |
|---|---|---|
| arr[i] | 0 | 3 |
i = 2일 때를 살펴보자
arr[2] = 5이다.
이때 X를 살펴보면 가장 마지막 arr[i]의 값이 3이고, 이는 5보다 작다.
이 말은 현재 arr[2] 앞의 수들로 만든 가장 긴 증가부분수열 중 마지막 값이 3인 증가부분수열이 있다는 말이다.
그리고 arr[2]를 그 뒤에 붙일 수 있다. 따라서 dp[2] = 1 + 1 = 2이다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| arr | 0 | 3 | 5 | 7 | 8 | 2 | 1 | 4 | 8 |
| dp | 0 | 1 | 2 |
| dp[i] | 0 | 1 | 2 |
|---|---|---|---|
| arr[i] | 0 | 3 | 5 |
i = 3 일 때를 살펴보자
arr[3] = 7이다.
이 때 X를 살펴보면 가장 마지막 arr[i]의 값이 5이고, 이는 7보다 작음
이 말은 현재 arr[3] 앞의 수들로 만든 가장 긴 증가부분수열 중 마지막 값이 5인 증가부분수열이 있다는 말임
그리고 arr[3]을 그 뒤에 붙일 수 있음
따라서 dp[3] = 2 + 1 = 3이다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| arr | 0 | 3 | 5 | 7 | 8 | 2 | 1 | 4 | 8 |
| dp | 0 | 1 | 2 | 3 |
| dp[i] | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| arr[i] | 0 | 3 | 5 | 7 |
i = 4일 때를 살펴보자
arr[4] = 9이다.
이때 X를 살펴보면 마지막 arr[i]의 값이 7이고 이는 9보다 작다.
따라서 dp[4] = 3 + 1 = 4이다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| arr | 0 | 3 | 5 | 7 | 8 | 2 | 1 | 4 | 8 |
| dp | 0 | 1 | 2 | 3 | 4 |
| dp[i] | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| arr[i] | 0 | 3 | 5 | 7 | 9 |
i = 5 일 때를 살펴보자
arr[5] = 2 이다.
이 때 X의 arr[i] 값들을 살펴보면 2는 0과 3 사이의 값이다. 그러므로 dp[5] = 0 + 1이다.
X에서 dp[i] = 1 일 때 arr[i] 값은 현재는 3이나. a[5]= 2이므로 더 작은 2로 갱신해준다.
이 말은 증가부분수열의 길이가 1인 수열 중 끝이 3으로 끝나는 증가부분수열(기존)과 끝이 2로 끝나는 증가부분수열(현재)이 있으므로, 이들 중 끝값이 더 작은 2를 X에 저장해놓겠다는 것이다.
추후 dp[i] = 2인 수열을 찾기 위해 arr[5] = 2 뒤에 붙일 수 있는지만 확인하면 되기 때문이다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| arr | 0 | 3 | 5 | 7 | 8 | 2 | 1 | 4 | 8 |
| dp | 0 | 1 | 2 | 3 | 4 | 1 |
| dp[i] | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| arr[i] | 0 | 2 | 5 | 7 | 9 |
i = 6 일 때를 살펴보자
arr[6] = 1
이 때의 X의 arr[i] 값들을 살펴보면 1은 0과 2 사이의 값이다.
그러므로 dp[6] = 0 + 1
X에서 dp[i] = 1 일 때 arr[i]을 2에서 1로 갱신해준다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| arr | 0 | 3 | 5 | 7 | 8 | 2 | 1 | 4 | 8 |
| dp | 0 | 1 | 2 | 3 | 4 | 1 | 1 |
| dp[i] | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| arr[i] | 0 | 1 | 5 | 7 | 9 |
i = 7일 때를 살펴보자.
arr[7]=4
이때 X의 arr[i] 값들을 살펴보면 4는 1과 5사이의 값이다.
그러므로 dp[7]=1+1 = 2
X에서의 dp[i]= 2 일 때 arr[i]를 5에서 4로 갱신해준다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| arr | 0 | 3 | 5 | 7 | 8 | 2 | 1 | 4 | 8 |
| dp | 0 | 1 | 2 | 3 | 4 | 1 | 1 | 2 |
| dp[i] | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| arr[i] | 0 | 1 | 4 | 7 | 9 |
i = 8 일때를 살펴보자
arr[8] = 8
X의 arr[i] 값들을 살펴보면 8은 7과 9 사이의 값이다.
그러므로 dp[8] = 3 + 1 = 4
X의 dp[i] = 4일 때 arr[i]의 값을 9에서 8로 갱신해준다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| arr | 0 | 3 | 5 | 7 | 8 | 2 | 1 | 4 | 8 |
| dp | 0 | 1 | 2 | 3 | 4 | 1 | 1 | 2 | 4 |
| dp[i] | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| arr[i] | 0 | 1 | 4 | 7 | 9 |
이렇게 해서 배열 dp를 다 완성했다.
dp의 값들 중 가장 큰 값 dp[4] = dp[8] = 4 가 수열 arr의 LIS의 길이이다.
이 알고리즘은 N개의 수들에 대해 X의 A[i]들을 훑어본다.
이때 X는 오름차순으로 항상 정렬되어 있으므로 이진 탐색을 사용할 수 있다.
이진 탐색을 사용하여 현재 arr[i]보다 작은 arr[j]를 x에서 찾는다. 그 A[j]에 해당하는 D값에 1을 더하면 D[i]를 쉽게 구할 수 있다.
따라서 이 알고리즘은 의 시간복잡도를 가진다.
코드
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int SIZE = (int)1e3 + 1;
int arr[SIZE];
int dp[SIZE];
vector<int> lis;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> arr[i];
}
for (int i = 1; i <= N; i++) {
auto iter = lower_bound(lis.begin(), lis.end(), arr[i]);
if (iter == lis.end()) {
lis.push_back(arr[i]);
}
else {
*iter = arr[i];
}
}
for (int num : lis) {
cout << num <<' ';
}
cout <<'\n';
cout << lis.size() <<'\n';
return 0;
}