LIS - 최장 증가 부분 수열 - soo:bak
작성일 :
LIS란?
수열 [10, 20, 10, 30, 20, 50]에서 순서를 유지하면서 원소를 선택하여 오름차순으로 증가하는 부분 수열을 만든다고 가정해보겠습니다.
가능한 증가 부분 수열은 여러 가지입니다:
[10]→ 길이 1[10, 20]→ 길이 2[10, 20, 30]→ 길이 3[10, 20, 30, 50]→ 길이 4[10, 30, 50]→ 길이 3
이 중 가장 긴 것은 [10, 20, 30, 50]으로 길이가 4입니다. 이것이 LIS(Longest Increasing Subsequence, 최장 증가 부분 수열) 입니다.
부분 수열은 연속하지 않아도 됩니다.
원래 수열에서 일부 원소를 선택하되, 상대적인 순서만 유지하면 됩니다.
예를 들어, [10, 20, 10, 30, 20, 50]에서 1번째(20), 3번째(30), 5번째(50) 원소를 선택하면 [20, 30, 50]이라는 부분 수열이 됩니다.
LIS 문제가 중요한 이유
LIS는 단순히 “가장 긴 증가 수열 찾기”를 넘어 다양한 문제에 응용됩니다.
1. 전깃줄 문제
왼쪽과 오른쪽에 전봇대가 있고, 전깃줄이 연결되어 있습니다.
전깃줄이 교차하지 않도록 최소 개수만 제거하려면, 남길 수 있는 최대 전깃줄 수를 구해야 합니다.
이는 LIS 문제로 변환됩니다.
2. 상자 쌓기 문제
상자를 쌓을 때 위의 상자가 아래 상자보다 작아야 합니다.
최대로 쌓을 수 있는 상자 수는 LIS와 같은 원리로 구합니다.
3. 2차원 점 문제
2차원 평면에서 점들을 x좌표로 정렬한 뒤, y좌표에 대해 LIS를 구하면 특정 조건을 만족하는 최대 점의 개수를 구할 수 있습니다.
O(n²) DP 풀이
아이디어
dp[i] = i번째 원소를 마지막으로 하는 LIS의 길이
각 위치 i에서, 자신보다 앞에 있으면서 값이 작은 원소 j를 찾습니다.
그중 dp[j]가 가장 큰 값에 1을 더하면 dp[i]가 됩니다.
점화식
\[dp[i] = \max(dp[j] + 1) \quad (j < i \text{ 이고 } arr[j] < arr[i])\]모든 dp[i]의 초깃값은 1입니다. 자기 자신만으로도 길이 1의 LIS가 되기 때문입니다.
동작 과정
수열: [10, 20, 10, 30, 20, 50]
| i | arr[i] | 앞에서 작은 값 | dp[i] |
|---|---|---|---|
| 0 | 10 | 없음 | 1 |
| 1 | 20 | arr[0]=10 | dp[0]+1 = 2 |
| 2 | 10 | 없음 | 1 |
| 3 | 30 | 10, 20, 10 | max(1,2,1)+1 = 3 |
| 4 | 20 | 10, 10 | max(1,1)+1 = 2 |
| 5 | 50 | 10,20,10,30,20 | max(1,2,1,3,2)+1 = 4 |
최종 dp 배열: [1, 2, 1, 3, 2, 4]
LIS 길이 = max(dp) = 4
구현 (C++)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
int lis_dp(vi& arr) {
int n = arr.size();
vi dp(n, 1); // 모든 원소의 초기 LIS 길이는 1
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
// j번째 원소가 i번째보다 작으면 이어붙일 수 있음
if (arr[j] < arr[i])
dp[i] = max(dp[i], dp[j] + 1);
}
}
return *max_element(dp.begin(), dp.end());
}
int main() {
vi arr = {10, 20, 10, 30, 20, 50};
cout << lis_dp(arr) << "\n"; // 4
return 0;
}
시간 복잡도: O(n²) - 각 원소에 대해 앞의 모든 원소를 확인 공간 복잡도: O(n)
n이 1,000 이하이면 이 방법으로 충분합니다. 하지만 n이 100,000 이상이면 시간 초과가 발생합니다.
O(n log n) 이분탐색 풀이
아이디어
LIS의 길이만 필요한 경우, 더 효율적인 방법이 있습니다.
핵심 아이디어는 간단합니다. 같은 길이의 증가 수열이라면, 마지막 원소가 작을수록 더 긴 수열로 확장하기 유리합니다.
예를 들어, [10, 20]과 [10, 15]는 둘 다 길이 2의 증가 수열입니다.
하지만 [10, 15]는 마지막이 15이므로 17이 오면 이어붙일 수 있는 반면, [10, 20]은 17을 이어붙일 수 없습니다.
배열 관리
이 관찰을 활용하여, 각 길이별로 가능한 가장 작은 끝 값만 기억합니다.
lis[k] = 길이가 k+1인 증가 수열의 마지막 원소 중 최솟값
이 배열은 항상 오름차순 정렬 상태를 유지합니다. 더 긴 수열을 만들려면 현재 끝 값보다 큰 값이 필요하기 때문입니다.
새 원소 처리
배열이 정렬되어 있으므로, 새 원소 x의 위치를 이분탐색으로 빠르게 찾을 수 있습니다.
x가lis배열의 마지막보다 크면 → 배열 끝에 추가 (LIS 길이 증가)- 그렇지 않으면 →
x이상인 첫 위치를 찾아 교체
동작 과정
수열: [10, 20, 10, 30, 20, 50]
1
2
3
4
5
6
arr[0]=10: lis = [10] (길이 1, 마지막 10)
arr[1]=20: 20 > 10 → lis = [10, 20] (길이 2)
arr[2]=10: 10의 위치 찾기 → 인덱스 0 → [10, 20] (변화 없음)
arr[3]=30: 30 > 20 → lis = [10, 20, 30] (길이 3)
arr[4]=20: 20의 위치 찾기 → 인덱스 1 → [10, 20, 30] (변화 없음)
arr[5]=50: 50 > 30 → lis = [10, 20, 30, 50] (길이 4)
최종적으로 LIS 길이 = lis.size() = 4 가 됩니다.
이 예시에서 lis 배열 [10, 20, 30, 50]은 실제 LIS와 일치하지만, 항상 그런 것은 아닙니다.
이 배열은 길이를 구하기 위한 보조 배열이며, 실제 LIS 수열이 필요하다면 별도의 역추적이 필요합니다.
구현 (C++)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
int lis_binary(vi& arr) {
vi lis; // 길이별 마지막 원소의 최솟값
for (int x : arr) {
// x 이상인 첫 위치를 찾음
auto pos = lower_bound(lis.begin(), lis.end(), x);
if (pos == lis.end())
lis.push_back(x); // LIS 길이 증가
else
*pos = x; // 더 작은 값으로 교체
}
return lis.size();
}
int main() {
vi arr = {10, 20, 10, 30, 20, 50};
cout << lis_binary(arr) << "\n"; // 4
return 0;
}
시간 복잡도: O(n log n) - 각 원소에 대해 이분탐색 공간 복잡도: O(n)
LIS 복원하기
길이뿐 아니라 실제 LIS 수열을 구해야 할 때가 있습니다.
아이디어
각 원소가 LIS에서 몇 번째 위치인지 저장하고, 마지막부터 역추적합니다.
구현 (C++)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
vi lis_reconstruction(vi& arr) {
int n = arr.size();
vi lis, pos(n); // pos[i]: arr[i]가 LIS에서 몇 번째 위치인지
for (int i = 0; i < n; i++) {
auto it = lower_bound(lis.begin(), lis.end(), arr[i]);
pos[i] = it - lis.begin();
if (it == lis.end())
lis.push_back(arr[i]);
else
*it = arr[i];
}
// 역추적으로 LIS 복원
vi result;
int lisLen = lis.size();
int target = lisLen - 1;
for (int i = n - 1; i >= 0 && target >= 0; i--) {
if (pos[i] == target) {
result.push_back(arr[i]);
target--;
}
}
reverse(result.begin(), result.end());
return result;
}
int main() {
vi arr = {10, 20, 10, 30, 20, 50};
vi result = lis_reconstruction(arr);
for (int x : result)
cout << x << " "; // 10 20 30 50
cout << "\n";
return 0;
}
역추적 시 가장 뒤에서부터 탐색하여, 해당 위치에 속하는 원소를 찾습니다.
LIS 변형 문제
최장 비감소 부분 수열
같은 값도 포함하려면 < 대신 <=를 사용합니다. 이분탐색에서는 lower_bound 대신 upper_bound를 사용합니다.
1
auto pos = upper_bound(lis.begin(), lis.end(), x);
최장 감소 부분 수열 (LDS)
수열을 뒤집거나, 비교 조건을 반대로 합니다.
1
2
3
4
5
6
// 방법 1: 수열 뒤집기
reverse(arr.begin(), arr.end());
int lds = lis_binary(arr);
// 방법 2: 비교 함수 변경
auto pos = lower_bound(lis.begin(), lis.end(), x, greater<int>());
2차원 LIS
점이 (x, y) 형태로 주어지고, x와 y가 모두 증가하는 최장 수열을 구하는 문제입니다.
- x 기준 오름차순 정렬 (x가 같으면 y 기준 내림차순)
- y 값에 대해 LIS 수행
시간 복잡도 비교
| 방법 | 시간 복잡도 | 적합한 n 범위 | 특징 |
|---|---|---|---|
| O(n²) DP | O(n²) | n ≤ 1,000 | 구현 간단, 역추적 용이 |
| 이분탐색 | O(n log n) | n ≤ 1,000,000 | 효율적, 길이만 구할 때 적합 |
마무리
LIS는 수열에서 순서를 유지하면서 가장 긴 증가 부분 수열을 찾는 문제입니다.
| 방법 | 핵심 아이디어 |
|---|---|
| O(n²) DP | dp[i] = i번째로 끝나는 LIS 길이 |
| O(n log n) | 길이별 마지막 원소 최솟값 유지 + 이분탐색 |
n의 크기에 따라 적절한 방법을 선택하면 됩니다.
관련 문제