최장 증가 부분 수열
LIS란?
“Longest Increasing Subsequence”의 약자로, 배열의 원소들 중 일부만 골랐을 때, 그 수열의 원소들이 이전의 원소보다 크다는 조건을 만족하면서 그 길이가 가장 큰 수열을 만족하도록 하는 수열을 찾는 알고리즘이다.
쉽게 얘기하면, 부분수열을 골랐을 때 수열이 모든 부분에서 증가하는 모양을 띠도록 하는 최대 길이의 부분수열을 찾는 알고리즘이라고 할 수 있다.
예시로, 만약 수열
알고리즘 해법
이 단계에서는 LIS 문제를 해결하기 위해, 문제 예시와 그 해법에 대해 설명한다.
시나리오 예시
문제 해결을 위한 예시 문제로 아래와 같은 문제들을 예시로 가져와 설명한다.
1. 가장 긴 증가하는 부분 수열
백준 11053 : 가장 긴 증가하는 부분 수열
LIS 문제를 해결하기 위한 가장 기본형의 문제이다. 따라서 이 문제의 해결법이 LIS 문제를 해결하는 가장 기본적인 방법이라고 생각하면 된다.
문제에서 사용된 예시 수열은
LIS 길이를 저장할 배열을 하나 생성하고 0으로 초기화하자. (
고른 수열은 오른쪽으로 갈수록 계속해서 커져야하므로, 현재 원소에서의 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]);
}
위 예시
2중 for문을 이용하여 모든 원소를 탐색하므로 시간복잡도는
2. 가장 긴 증가하는 부분 수열 2
백준 12015 : 가장 긴 증가하는 부분 수열 2
위와 같은 LIS 문제이다. 다만 달라진 점은 시간과 원소의 개수이다. 크게 바뀐게 없어보이지만 원소의 개수가 달라졌다고 하면 99% 확률로 시간복잡도에서부터 문제를 발생시키게 된다. 이 문제도 마찬가지로, 기존 방법인
원소의 개수가
- 모든 원소에 대해서 반복한다
- LIS 배열에 현재 원소를 어디에 넣을 수 있을지 판단한다. 판단 근거는 “LIS 배열이 계속해서 LIS를 만족하도록”
- 예를 들어, 현재 원소가
이고 LIS 배열이 인 상황이라면, LIS를 유지하면서 를 넣을 수 있는 위치는 이 있는 위치일 것이다- 그렇게 바꾼다면 LIS 배열은
로 갱신된다 - LIS 배열에 50이 이미 있었으면, 이 50은 22보다 먼저 등장한 수일 것이다. 따라서 22 다음에 50이 오는 것이 실제 LIS는 아닐 것이다. 즉, 최종적으로 만들어지는 LIS 배열은 실제 LIS는 아니라는 것
- 그렇게 바꾼다면 LIS 배열은
- LIS를 이런 식으로 갱신하는 이유는, 이후에 나올 원소들을 가장 최적의 위치에 배치시키고 싶기 때문이다. 다음에 나올 원소들에 대해서 뒤에 추가할 수 있는 가능성을 최대한 열어두겠다는 것
- 또, 그 원소를 끝으로 할 때 만들 수 있는 LIS의 길이를 저장하고 있다는 것도 하나의 목적
문제에서 사용하는 예시로 과정을 알아보자.
- 초기 상태 :
, 선택 : 배열에는 아무것도 없으므로, 그냥 집어넣을 수 있다 선택 : 20은 LIS 배열의 가장 끝인 10보다 크다. 현재 LIS로 성립할 수 있음 선택 : 10은 LIS 배열의 가장 끝인 20보다 크지 않다. 이분탐색 결과는 0번 index이므로 그곳에 집어넣음 선택 : 30은 LIS 배열의 가장 끝인 20보다 크다. 현재 LIS로 성립할 수 있음 선택 : 20은 LIS 배열의 가장 끝인 30보다 크지 않다. 이분탐색 결과는 1번 index이므로 그곳에 집어넣음 선택 : 50은 LIS 배열의 가장 끝인 30보다 크다. 현재 LIS로 성립할 수 있음- 모든 원소에 대해 탐색하고, 그 때의 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
이다.
전체 시간복잡도는 원소의 개수
3. 가장 긴 증가하는 부분 수열 5
백준 14003 : 가장 긴 증가하는 부분 수열 5
2번 문제와 상황이 같다. 다른 점은 LIS일 때의 원소를 모두 출력하는 것. 사실 LIS는 여러개 나올 수 있기 때문에, 그 중에서 아무거나 출력해도 된다. 다만 주의해야할 것은 2번 문제에서 만들어진 LIS 배열은 실제 LIS를 나타내지는 않는다는 점이다. 이 배열을 그대로 출력하면 안된다.
시간복잡도상 LIS 배열은 2번 문제에서 만들던 대로 만들어야한다. 하지만 이후 결과를 출력할 때 LIS를 역추적할 수 있도록 장치를 마련해야한다. 물론 LIS 배열의 길이가 1 늘어날 때 현재의 LIS 배열을 백업해두었다가 마지막에 출력해도 된다. 다만 백업 과정이 길어서 복잡도에 영향이 갈 수도 있어서, 시간이 빡빡한 문제라면 다른 방법도 고려해야할 때가 있을 것이다.
백업을 하지 않고 역추적을 통해서 계산하려면, 현재 값을 LIS에 적용시킬 때 이전 값이 무엇이었는지를 기록해두면 역추적하기 쉽다. pre[]
배열을 하나 만들어서, 현재 노드가 어떤 노드와 LIS로 연결되는지 그 index를 기록하도록 하자. LIS 연결 방법은 기존
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]);
}