최장 증가 부분 수열
LIS란?
“Longest Increasing Subsequence”의 약자로, 배열의 원소들 중 일부만 골랐을 때, 그 수열의 원소들이 이전의 원소보다 크다는 조건을 만족하면서 그 길이가 가장 큰 수열을 만족하도록 하는 수열을 찾는 알고리즘이다.
쉽게 얘기하면, 부분수열을 골랐을 때 수열이 모든 부분에서 증가하는 모양을 띠도록 하는 최대 길이의 부분수열을 찾는 알고리즘이라고 할 수 있다.
예시로, 만약 수열 $A = \lbrace 10, 20, 10, 30, 20, 50 \rbrace$ 가 있다고 가정할 때, 가장 긴 증가하는 부분 수열은 $B_A = \lbrace 10, 20, 30, 50 \rbrace$ 라고 할 수 있고, 이 길이의 수열은 유일하지 않기 때문에 여러개 존재할 수 있다. 하지만 알고리즘은 최장 증가 부분수열의 길이를 반환하므로 항상 4를 반환할 것이다.
알고리즘 해법
이 단계에서는 LIS 문제를 해결하기 위해, 문제 예시와 그 해법에 대해 설명한다.
시나리오 예시
문제 해결을 위한 예시 문제로 아래와 같은 문제들을 예시로 가져와 설명한다.
1. 가장 긴 증가하는 부분 수열
백준 11053 : 가장 긴 증가하는 부분 수열
LIS 문제를 해결하기 위한 가장 기본형의 문제이다. 따라서 이 문제의 해결법이 LIS 문제를 해결하는 가장 기본적인 방법이라고 생각하면 된다.
문제에서 사용된 예시 수열은 $A = \lbrace 10, 20, 10, 30, 20, 50 \rbrace$이다. 우리는 LIS의 길이를 구하기 위해 LIS 길이를 따로 저장하는 배열을 만들 수 있다. 배열의 값은 어떻게 저장할 수 있을까?
LIS 길이를 저장할 배열을 하나 생성하고 0으로 초기화하자. ( $LIS = \lbrace 0, 0, 0, 0, 0, 0 \rbrace$ ) 이후에 원소를 하나하나 비교해보며 가능한 최대의 길이를 저장하도록 해보자.
고른 수열은 오른쪽으로 갈수록 계속해서 커져야하므로, 현재 원소에서의 LIS를 구하기 위해서 오른쪽 원소들을 고려할 필요는 없다는 것을 알 수 있다. 하지만 왼쪽 원소들은 전부 비교해보아야한다. 우리는 이것을 2중 for문을 이용하여 구현할 수 있을 것 같다.
- 모든 원소에 대해서 반복하여 선택한다
- LIS의 기본값은 본인만 선택하였을 경우를 생각하여 1로 초기화할 수 있다
- 첫 원소부터 현재 선택되어있는 원소 직전까지의 원소들과 비교하여, 선택된 원소가 이전 원소보다 크다면 그 원소로부터 LIS를 이을 수 있다고 생각할 수 있다
- LIS를 이을 수 있다는 것은, 이전 원소의 LIS 길이보다 1 긴 LIS를 만들 수 있다는 의미
이것을 구현해보면 아래와 같다.
1
2
3
4
5
6
7
8
9
10
11
12
const int DEFAULT = 1;
int retval = 0;
for (int i = 0; i < n; ++i) {
LIS[i] = DEFAULT;
for (int j = 0; j < i; ++j) {
if (arr[j] < arr[i]) {
LIS[i] = max(LIS[j] + 1, LIS[i]);
}
}
retval = max(retval, LIS[i]);
}
위 예시 $A = \lbrace 10, 20, 10, 30, 20, 50 \rbrace$ 에서 위 코드를 이용하여 계산하면 LIS 배열은 $LIS = \lbrace 1, 2, 1, 3, 2, 4 \rbrace$ 라는 값을 갖게 된다. 이 중에서 LIS 값이 가장 큰 값은 $4$이며, 이것이 최장 증가 부분수열의 길이이다.
2중 for문을 이용하여 모든 원소를 탐색하므로 시간복잡도는 $O(N^2)$.
2. 가장 긴 증가하는 부분 수열 2
백준 12015 : 가장 긴 증가하는 부분 수열 2
위와 같은 LIS 문제이다. 다만 달라진 점은 시간과 원소의 개수이다. 크게 바뀐게 없어보이지만 원소의 개수가 달라졌다고 하면 99% 확률로 시간복잡도에서부터 문제를 발생시키게 된다. 이 문제도 마찬가지로, 기존 방법인 $O(N^2)$의 방법으로는 풀 수 없는 복잡도를 가지도록 설계되었다. 그렇다고 원소 개수가 $N$개인데 $O(N)$의 복잡도를 실현할 수는 없으니까, 시간복잡도를 줄일 방법을 찾아야한다. ( $O(N)$과 $O(N^2)$ 사이의 복잡도를 가져야하니까, 대충 $O(N \log N)$의 복잡도를 가지도록 하면 될 것 같다 )
원소의 개수가 $N$개이고 어짜피 전부 탐색해봐야하므로, 결국은 현재 LIS값이 몇인지를 계산하는 것을 $O(N)$에서 줄여야한다. 우리는 여기서 이분탐색 방법을 사용할 수 있다. LIS 배열에서 이분탐색을 이용해 각 원소를 적절한 위치에 놓도록 할 수 있다.
- 모든 원소에 대해서 반복한다
- LIS 배열에 현재 원소를 어디에 넣을 수 있을지 판단한다. 판단 근거는 “LIS 배열이 계속해서 LIS를 만족하도록”
- 예를 들어, 현재 원소가 $22$이고 LIS 배열이 $LIS = \lbrace 10, 20, 30, 50 \rbrace$인 상황이라면, LIS를 유지하면서 $22$를 넣을 수 있는 위치는 $30$이 있는 위치일 것이다
- 그렇게 바꾼다면 LIS 배열은 $LIS = \lbrace 10, 20, 22, 50 \rbrace$로 갱신된다
- LIS 배열에 50이 이미 있었으면, 이 50은 22보다 먼저 등장한 수일 것이다. 따라서 22 다음에 50이 오는 것이 실제 LIS는 아닐 것이다. 즉, 최종적으로 만들어지는 LIS 배열은 실제 LIS는 아니라는 것
- LIS를 이런 식으로 갱신하는 이유는, 이후에 나올 원소들을 가장 최적의 위치에 배치시키고 싶기 때문이다. 다음에 나올 원소들에 대해서 뒤에 추가할 수 있는 가능성을 최대한 열어두겠다는 것
- 또, 그 원소를 끝으로 할 때 만들 수 있는 LIS의 길이를 저장하고 있다는 것도 하나의 목적
문제에서 사용하는 예시로 과정을 알아보자.
- 초기 상태 : $A = \lbrace 10, 20, 10, 30, 20, 50 \rbrace$, $LIS = \lbrace \rbrace$
- $A_1$ 선택 : 배열에는 아무것도 없으므로, 그냥 집어넣을 수 있다
- $LIS = \lbrace 10 \rbrace$
- $A_2$ 선택 : 20은 LIS 배열의 가장 끝인 10보다 크다. 현재 LIS로 성립할 수 있음
- $LIS = \lbrace 10, 20 \rbrace$
- $A_3$ 선택 : 10은 LIS 배열의 가장 끝인 20보다 크지 않다. 이분탐색 결과는 0번 index이므로 그곳에 집어넣음
- $LIS = \lbrace 10, 20 \rbrace$
- $A_4$ 선택 : 30은 LIS 배열의 가장 끝인 20보다 크다. 현재 LIS로 성립할 수 있음
- $LIS = \lbrace 10, 20, 30 \rbrace$
- $A_5$ 선택 : 20은 LIS 배열의 가장 끝인 30보다 크지 않다. 이분탐색 결과는 1번 index이므로 그곳에 집어넣음
- $LIS = \lbrace 10, 20, 30 \rbrace$
- $A_6$ 선택 : 50은 LIS 배열의 가장 끝인 30보다 크다. 현재 LIS로 성립할 수 있음
- $LIS = \lbrace 10, 20, 30, 50 \rbrace$
- 모든 원소에 대해 탐색하고, 그 때의 LIS 배열의 길이가 문제에서 원하는 길이가 된다.
이 문제에서 사용되는 이분탐색은 ‘현재 값보다 큰 수들 중 최솟값’을 찾아야하므로, lower_bound를 사용한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int lower_bound(int x) {
int s = 0, e = lis_len + 1;
int mid;
while (s < e) {
mid = (s + e) / 2;
if (LIS[mid] < x) {
s = mid + 1;
} else {
e = mid;
}
}
return e;
}
lower_bound를 사용하여 원하는 위치를 찾을 수 있다면, 이제 원소를 적절하게 LIS 배열에 넣도록 하면 된다.
1
2
3
4
5
6
7
8
9
10
for (int i = 1; i < n; ++i) {
int a;
scanf("%d", &a);
if (a > LIS[lis_len]) {
LIS[++lis_len] = a;
} else {
LIS[lower_bound(a)] = a;
}
}
이렇게 만든다면 전체 LIS의 길이는 lis_len + 1이다.
전체 시간복잡도는 원소의 개수 $N$과 각 원소가 이분탐색을 하므로 $O(\log N)$, 합쳐서 $O(N \log N)$이다.
3. 가장 긴 증가하는 부분 수열 5
백준 14003 : 가장 긴 증가하는 부분 수열 5
2번 문제와 상황이 같다. 다른 점은 LIS일 때의 원소를 모두 출력하는 것. 사실 LIS는 여러개 나올 수 있기 때문에, 그 중에서 아무거나 출력해도 된다. 다만 주의해야할 것은 2번 문제에서 만들어진 LIS 배열은 실제 LIS를 나타내지는 않는다는 점이다. 이 배열을 그대로 출력하면 안된다.
시간복잡도상 LIS 배열은 2번 문제에서 만들던 대로 만들어야한다. 하지만 이후 결과를 출력할 때 LIS를 역추적할 수 있도록 장치를 마련해야한다. 물론 LIS 배열의 길이가 1 늘어날 때 현재의 LIS 배열을 백업해두었다가 마지막에 출력해도 된다. 다만 백업 과정이 길어서 복잡도에 영향이 갈 수도 있어서, 시간이 빡빡한 문제라면 다른 방법도 고려해야할 때가 있을 것이다.
백업을 하지 않고 역추적을 통해서 계산하려면, 현재 값을 LIS에 적용시킬 때 이전 값이 무엇이었는지를 기록해두면 역추적하기 쉽다. pre[] 배열을 하나 만들어서, 현재 노드가 어떤 노드와 LIS로 연결되는지 그 index를 기록하도록 하자. LIS 연결 방법은 기존 $O(n \log n)$ 방법 그대로 진행한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
lis_len = 0;
lis_cur = 0;
LIS[0] = (ND){arr[0], 0};
pre[0] = -1;
for (int i = 1; i < n; ++i) {
int x = arr[i];
if (x > LIS[lis_len].v) {
pre[i] = LIS[lis_len].idx;
LIS[++lis_len] = (ND){x, i};
lis_cur = i;
} else {
int t = lower_bound(x);
if (t > 0) {
pre[i] = LIS[t - 1].idx;
} else {
pre[i] = -1;
}
LIS[t] = (ND){x, i};
}
}
이렇게 각 노드에 대해 연결을 이었다면, 나중에 출력할 때 역순으로 출력하기만 하면 된다. 이것은 재귀함수로 끝까지 들어가서 나올 때 출력하는 방법이 있고, 백업하는 것처럼 하나의 배열에 저장했다가 출력하는 방법도 있다. 아래 코드는 후자의 경우다.
1
2
3
4
5
6
7
8
printf("%d\n", lis_len + 1);
for (int i = 0; lis_cur > END; ++i) {
lis[i] = arr[lis_cur];
lis_cur = pre[lis_cur];
}
for (int i = lis_len; i >= 0; --i) {
printf("%d ", lis[i]);
}