※ 가장 긴 증가하는 부분 수열(Longest Increasing Subsequence)이란?
부분 수열 중에서 각 원소가 이전 원소보다 큰 부분 수열 중에서 가장 긴 것!
예를 들어서, { 2, 5, 1, 7, 4, 8, 3} 이라는 배열이 있을 때,
증가하는 부분 수열은 { 2, 5 }, { 1, 4, 3} 등이 있지만 LIS는 { 2, 5, 7, 8 } 이다!
알고리즘은 시간복잡도에 따라서 2가지가 있다. ( O(N^2)과 O(N log N) )
첫 번째 방법은 다이나믹 프로그래밍을 통한 방법이다. 시간 복잡도는 O(N^2)
code#1
|
1
2
3
4
5
6
7
|
for (int i = 0; i < n;i++) {
int here = 0;
for (int j = 0;j < i;j++) {
if (arr[i] > arr[j]) here = max(here, DP[j]);
}
DP[i] = here + 1;
}
|
cs |
code#2
|
1
2
3
4
5
6
7
8
|
for (int i = 0 ; i < n ; i++) {
DP[i] = 1;
for (int j = 0 ; j < i ; j++) {
if (arr[i] > arr[j] && DP[i] < DP[j] + 1) {
DP[i] = DP[j] + 1;
}
}
}
|
cs |
DP[i]에는 i번째 원소를 마지막으로 하는 LIS의 길이를 저장하고 인덱스를 한 칸씩 늘려가며 확인한다. i번째 원소를 확인할 때는 1부터 i-1까지 전부 확인해서 O(N)라는 시간이 걸리고, 전체로 따질 경우 O(N^2)가 된다.
두 번째 방법은 Lower Bound와 이진 탐색을 이용한 방법이다. 시간 복잡도는 O(N log N)
백준 12015번 : 가장 긴 증가하는 부분 수열2
|
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
|
#include <iostream>
using namespace std;
int n;
int arr[1000001], dp[1000001];
int binary(int left, int right, int key) {
int mid;
while (left <= right) {
mid = (left + right) / 2;
if (dp[mid] >= key) right = mid - 1;
else left = mid + 1;
}
return left;
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
dp[0] = arr[0];
int idx = 0;
for (int i = 1; i < n;i++) {
if (dp[idx] < arr[i]) dp[++idx] = arr[i];
else {
int lower_bound = binary(0, idx, arr[i]);
dp[lower_bound] = arr[i];
}
}
cout << idx + 1;
}
|
cs |
Lower Bound의 개념을 알아야 이진 탐색을 이용한 LIS 알고리즘을 이해하기 쉽다. Lower Bound란 어떤 배열을 정렬된 상태로 유지하면서 어떤 값이 삽입될 수 있는 위치 중에서 가장 작은 인덱스이다.
예를 들어, { 1, 3, 5, 7 } 라는 배열에 2가 정렬된 상태를 유지하면서 위치할 수 있는 인덱스는 1이고, 4는 2번 인덱스이다. 따라서 2의 Lower bound는 1이고, 4의 Lower bound는 2이다.
값이 저장된 배열 arr에서 배열 DP로 저장될 값의 변화 과정을 보이면,
| arr | 10 | 20 | 10 | 30 | 20 | 50 |
| DP | 10 |
다음 값(20)이 이전 값보다 크기 때문에 그냥 넣는다.
| DP | 10 | 20 |
다음 값(10)이 이전 값보다 작기 때문에 이진 탐색으로 들어갈 위치를 찾아 넣는다.
이진 탐색이 0을 반환해 DP[0]에 10을 저장한다. 따라서 변화는 없다.
| DP | 10 | 20 |
다음 값(30)이 이전 값보다 크기 때문에 그냥 넣는다.
| DP | 10 | 20 | 30 |
다음 값(20)이 이전 값보다 작기 때문에 위치(1)를 찾아 저장한다. 따라서 변화는 없다.
| DP | 10 | 20 | 30 |
다음 값(50)이 이전 값보다 크기 때문에 그냥 넣는다.
| DP | 10 | 20 | 30 | 50 |
모든 과정이 끝나 DP의 크기가 LIS의 길이가 된다.
사실 C++에는 Lower bound를 구하는 함수가 이미 있지만 알고리즘의 완벽한 이해를 위해서 따로 배열을 만들어 이진 탐색을 통해 Lower bound를 구해 LIS를 구현했다. 여기서 주의할 것은 따로 만들어진 배열의 원소들은 LIS의 원소가 아니라는 점이다.
LIS의 원소를 보이기 위해서는 또 추가적인 배열에 만들어 그곳에 인덱스를 저장하고, 저장된 인덱스를 통해서 LIS의 값들을 보여야 한다.
'개인 공부 > 알고리즘' 카테고리의 다른 글
| [알고리즘] 재귀 & 그리디 알고리즘 (0) | 2023.05.03 |
|---|---|
| [알고리즘] 정렬 & 탐색 알고리즘 (0) | 2023.04.28 |
| [알고리즘] 에라토스테네스의 체 (0) | 2022.07.01 |
| [알고리즘] 배낭 채우기 (Knapsack Problem) (0) | 2021.11.24 |
| [알고리즘] 유클리드 알고리즘(최대공약수, 최소공배수 구하기) (2) | 2021.07.03 |
댓글