[백준 12015] 이진 탐색으로 LIS 최적화하기
문제 개요
백준 12015번 문제입니다. LIS(Longest Increasing Sequence)의 길이를 $O(n\log n)$ 시간에 구해야 하는 문제로, 동적 계획법을 사용한 $O(n^2)$ 풀이와는 다른 방법이 필요합니다. 이진 탐색을 사용하여, LIS가 될 수 있는 후보군을 계속 갱신하는 방식의 풀이를 소개합니다.
문제 분석
새로운 원소 조회
동적 계획법 풀이와 같이 앞에서부터 원소를 하나씩 조회합니다. 지금까지 조회한 원소가 2와 5라고 합시다. LIS는 `2, 5` 일 것입니다.
이제 다음 원소가 3이라고 합시다. 가능한 LIS는 `2, 3` 과 `2, 5` 의 두 가지입니다. 그런데 마지막 원소가 작은 편이 뒤에 나올 원소들을 LIS에 넣기에 더욱 유리하므로, `2, 3` 을 선택하기로 합니다. (e.g. 다음 원소가 4일 경우 `2, 3` 은 `2, 3, 4` 로 확장이 가능하지만, `2, 5` 는 불가능합니다)
이번에는 다음 원소로 1이 나오면 어떻게 해야 할까요? `2, 3` 을 확장할 수는 없으니 무시해야 한다고 생각할 수 있습니다. 그런데 만약 1 뒤에도 2, 3, 4가 계속 이어진다면, LIS는 그림과 같이 1부터 시작하는 `1, 2, 3, 4`가 될 것입니다.
따라서 1을 단순히 무시할 수 없습니다. 일반화하면, 가장 작은 원소가 등장했을 때 단순히 무시할 수 없습니다. 대신, 그 원소부터 시작하는 LIS가 존재할 수 있는 가능성을 인정하고 후보군에 추가해야 할 것입니다. 이제 LIS의 후보군은 `2, 3` 과 `1` 이 되었습니다.
실제로 다음 원소는 2가 들어왔다고 합시다. LIS의 후보군들과 비교했을 때, 새로운 원소 2는 `2, 3` 의 마지막 원소인 3보다 작으므로 `2, 3` 을 확장할 수 없습니다. 반면 `1` 의 마지막 원소인 1보다는 크므로, `1` 을 `1, 2` 로 확장할 수 있습니다.
그런데 후보군을 보면 `1, 2` 와 `2, 3` 은 길이가 같지만, `2, 3` 의 마지막 원소인 3은 `1, 2` 의 마지막 원소인 2보다 큽니다. 즉, 확장하기에 불리합니다. 따라서 `2, 3` 은 더 이상 고려할 필요가 없습니다. 일반화하면, 후보군들 중 길이가 같을 때는 확장하기 가장 유리한 후보군 하나 외에는 모두 버려도 괜찮습니다.
반면 확장되기 전의 `1` 은 버려선 안 되는데, 나중에 2보다 작은 1.5 같은 원소가 들어올 경우 `1, 1.5` 로 확장할 수 있는 여지가 아직 남아있기 때문입니다. (원본 문제에는 소수가 없지만, 편의상 예시입니다) 따라서 LIS 후보군은 `1` 과 `1, 2` 로 갱신됩니다.
규칙 찾기
위의 예시에서 후보군을 갱신하는 중요한 규칙으로는 새로운 원소와 후보군의 마지막 원소의 비교를 통해 기존의 LIS 후보를 확장하거나, 버리거나, 새로운 후보를 추가하였습니다. 앞으로 새로운 원소와 LIS 후보를 비교할 때, LIS 후보의 마지막 원소보다 작으면 '후보보다 작다', 크면 '후보보다 크다'는 표현을 사용하겠습니다.
새로운 원소를 처리하는 상황은 다음의 3가지 중 하나입니다.
- 새로운 원소가 가장 작을 때
- 새로운 원소가 어떤 후보보다는 작고, 어떤 후보보다는 클 때
- 새로운 원소가 가장 클 때
1번 경우는 앞에서 살펴본 상황 중 1이 추가되는 상황으로, 새로운 LIS 후보로 추가해야 합니다. 아래는 예시입니다.
LIS 후보군
7, 8
2, 3, 4
새로운 원소 1 처리 후
1
7, 8
2, 3, 4
2번 경우는 다소 까다로운 경우입니다. 앞서 2가 추가된 상황처럼, 기존 후보군들과의 비교를 통해 어떤 후보보다는 작고, 어떤 후보보다는 큰지 위치를 선정해야 합니다. 이후 찾은 위치의 후보를 확장한 후, 같은 길이를 가진 다른 후보를 모두 버리면 됩니다. 반면 확장하기 전 기존 후보는 버리면 안 됩니다.
LIS 후보군
1
4, 5
7, 8, 9
새로운 원소 2 처리 후
// 2는 LIS 후보 {1}보다는 크고, {7, 8}보다는 작습니다.
// {1}을 {1, 2}로 확장하고, 같은 길이인 {7, 8}을 버립니다.
1
1, 2
2, 3, 4
3번 경우는 아주 쉽습니다. 기존 후보들 중 가장 큰 후보를 그대로 확장하면 됩니다. 2번 경우와 똑같은 이유로 확장하기 전 후보는 버리면 안 됩니다.
LIS 후보군
1
2, 3
새로운 원소 4 처리 후
1
2, 3
2, 3, 4
문제 풀이
위의 규칙을 실제로 구현할 때는 LIS 후보군을 관리하는 자료구조의 선정이 문제가 됩니다. 그런데 모든 경우에서 후보군의 마지막 원소를 상대로만 비교가 이루어지고 있습니다. 따라서 LIS 후보의 수열을 통째로 저장할 필요가 없이, 후보군의 마지막 원소들만 저장하는 배열 등을 사용하면 간편하게 구현할 수 있습니다.
풀이에서는 `tail` 이라는 STL 벡터를 사용합니다. 벡터의 원소로는 각 후보들의 마지막 원소만 저장되어 있습니다. 이렇게 마지막 원소만 저장하는 벡터 등의 선형 자료구조를 사용하면, 재밌는 성질이 3가지 발생합니다.
- 새로운 원소를 $O(\log n)$ 시간에 처리할 수 있습니다.
- 이진 탐색을 통해 위치를 찾은 후 삽입하면 정렬된 상태를 유지할 수 있기 때문입니다.
- `i` 번째 원소는 길이가 `i ` 인 가장 유리한 후보의 마지막 원소가 됩니다. (인덱스 1부터 시작)
- 2번과 3번 경우에서, 확장 전의 기존 후보를 버리지 않기 때문에 가능합니다.
- 벡터의 길이가 곧 LIS의 길이가 됩니다.
- 2번 성질에 의한 자연스러운 결과입니다.
입력으로 5, 6, 1, 2, 3이 주어지는 예제를 통해 벡터를 사용한 풀이가 실제로 동작하는 과정을 살펴보겠습니다. 위의 3가지 성질이 그대로 나타나는 모습을 볼 수 있습니다.
새로운 원소 5 처리 후
tail[1] 5
새로운 원소 6 처리 후
// 이진 탐색을 하면 위치는 2번째입니다.
tail[1] 5
tail[2] 6
새로운 원소 1 처리 후
// 이진 탐색을 하면 위치는 1번째입니다.
// 길이 1인 후보는 {1}이 더 유리하니, {5}를 버립니다.
tail[1] 1
tail[2] 6
새로운 원소 2 처리 후
// 이진 탐색을 하면 위치는 2번째입니다.
// 길이 2인 후보는 {1,2}가 더 유리하니, {5,6}을 버립니다.
tail[1] 1
tail[2] 2
새로운 원소 3 처리 후
// 이진 탐색을 하면 위치는 3번째입니다.
tail[1] 1
tail[2] 2
tail[3] 3
더욱 재밌는 점은, 이진 탐색을 사용하면 1번 경우와 2번 경우를 똑같이 처리할 수 있습니다. 또한 버리는 작업을 단순히 해당 위치의 원소를 교체하기만 하면 쉽게 할 수 있습니다. 실제 코드에서 이진 탐색은 `std::lower_bound` 를 사용했습니다.
int main() {
vector<int> tail;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
tail.emplace_back(arr[0]);
for (int i = 1; i < n; i++) {
auto iter = lower_bound(tail.begin(), tail.end(), arr[i]);
if (iter == tail.end()) {
tail.emplace_back(arr[i]);
} else {
*iter = arr[i];
}
}
cout << tail.size() << "\n";
return 0;
}
참고자료
[1] Venki. "Longest Increasing Subsequent Size (NlogN)." GEEKSFORGEEKS.org. https://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/ (accessed Jul. 17, 2021).