[BOJ] 12015 : 가장 긴 증가하는 부분 수열 2 (C++)

https://www.acmicpc.net/problem/12015

12015번: 가장 긴 증가하는 부분 수열 2

---

꽤 유명하지만 약간은 마이너한 가장 긴 증가하는 부분 수열, LIS 알고리즘이다.

간단히 생각해보면 O(N^2) 알고리즘은 생각하지 쉽지만 이보다 더 줄일 수 있다.

O(N^2)

[6, 2, 5, 1, 7, 4, 8] 이라는 배열의 LIS 를 구하는 경우를 보자. 답은 [2, 5, 7, 8] 이다.

length 라는 배열을 length[i] = (i 에서 끝나는 LIS의 길이) 로 생각해보자.

이전까지의 배열을 탐색해 자신보다 낮으면 증가하는 부분수열이 가능하다는 것이므로 업데이트할 수 있다. 단, length에 1을 더한 값과 자신을 비교해 자신이 더 작아야 한다.

1. i = 0 일 때, length[0] 은 당연히 그냥 1이 된다.
2. i = 1 일 때, 이전에 있던 원소인 6은 2보다 크기 때문에 LIS가 성립하지 않는다.
3. i = 2 일 때, 이전에 있던 원소 2 보다 현재 원소 5가 더 크기 때문에 length[2] = 2를 넣는다.
4. i = 3 일 때, 이전에 있던 원소들보다 자신이 제일 작으므로 1이다.
5. i = 4 일 때, 원소 5가 길이 2의 LIS를 가지고 있어, 이보다 큰 길이 3의 LIS가 가능하다.
6. i = 5 일 때, 원소 1이 길이 1의 LIS를 가지고 있어, 이보다 큰 길이 2의 LIS가 가능하다.
7. i = 6 일 때, 원소 7이 길이 3의 LIS를 가지고 있어, 이보다 큰 길이 4의 LIS가 가능하다.

O(NlogN)

이번엔 length 라는 배열 말고 LIS 라는 배열을 두고, LIS 를 다음과 같은 방식으로 채워나간다.

배열을 탐색하면서 LIS가 오름차순 정렬을 유지하도록 해당 원소를 어디에 삽입할지 이진탐색

1. 만약 LIS의 맨 뒤 원소가 자신보다 낮다면 계속 더 긴 증가 수열을 만들 수 있으므로 자신을 맨 뒤에 삽입한다. 즉, LIS 배열의 길이가 LIS의 길이이다.
2. 하지만 만약 그렇지 않다면 무조건 LIS를 업데이트한다. 자신보다 크거나 같은 원소를 찾아가 자신을 삽입한다.

위의 예인 [6, 2, 5, 1, 7, 4, 8] 를 다시 보자. 답은 [2, 5, 7, 8] 이다.

1. i = 0 일 때, LIS는 [6] 이 된다.
2. i = 1 일 때, LIS의 맨 뒤 원소인 6이 자신보다 크므로 업데이트해야 한다. LIS는 [2] 가 된다.
3. i = 2 일 때, LIS의 맨 뒤 원소인 2 보다 자신이 크다. 맨 뒤에 삽입할 수 있다. LIS는 [2, 5]가 된다.
4. i = 3 일 때, LIS의 맨 뒤 원소인 5가 자신보다 크므로 업데이트해야 한다. LIS는 [1, 5] 가 된다.  
   • 여기서 LIS를 보자.
     1이 배열의 첫 번째에 위치하는 것은 1이라는 원소까지의 LIS는 1개라는 것이다.
     5가 배열의 두 번째에 위치하는 것은 5라는 원소까지의 LIS는 2개라는 것이다.
   • 즉, 이 배열의 원소들이 하나의 LIS를 말하는 것이 아니라, 각각 따로따로 의미가 있는 것이다. 하나의 LIS 배열에 데이터를 남기지 않고 파괴적으로 업데이트한다.
5. i = 4 일 때, LIS의 맨 뒤 원소보다 자신이 크다. LIS는 [1, 5, 7]이 된다.
6. i = 5 일 때, LIS를 업데이트 해야 한다. LIS는 [1, 4, 7]이 된다.
7. i = 6 일 때, LIS의 맨 뒤 원소보다 자신이 크다. LIS는 [1, 5, 7, 8]이 된다.

최종적으로 LIS의 길이인 4가 답이 된다.

시간 복잡도 계산

모든 원소를 보는 데서 N, 그리고 자신보다 크거나 같은 원소를 찾는데서 이진 탐색을 수행해 logN 이 든다. 즉 O(NlogN) 이다.

LIS 자체는 어떻게 찾을까

파괴적인 알고리즘 때문에 LIS 자체를 찾기 쉽지 않을 것 같다.

배열을 하나 더 추가하자. LIS 배열 작성 중 해당 원소가 삽입된 인덱스+1 을 저장하는 배열을 만든다. 이는 O(N^2) 의 length 배열과 같다. 이를 역순으로 탐색해 1씩 줄여나가며 가장 먼저 나온 수들이 LIS를 구성한다.

예시의 경우 length 배열은 [1, 1, 2, 1, 3, 2, 4] 로 완성되게 된다. 여기서 실제 LIS를 찾아보자.

1. LIS 배열의 길이가 4 이므로 4를 뒤에서부터 찾는다. 맨 마지막에 온 원소를 찾는 것이다.
   [1, 1, 2, 1, 3, 2, 4] -> 실제 원소는 8이다.
2. 4를 찾았으므로 3을 찾는다.
   [1, 1, 2, 1, 3, 2, 4] -> 실제 원소는 7이다.
3. 3를 찾았으므로 2를 찾는다.
   [1, 1, 2, 1, 3, 2, 4] -> 실제 원소는 5이다.
4. 2를 찾았으므로 1를 찾는다.
   [1, 1, 2, 1, 3, 2, 4] -> 실제 원소는 2이다.

이를 거꾸로 나열하면 2, 5, 7, 8 이다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

int main(void) {
	int n;
	cin >> n;
	int arr[1000001];
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	vector<int> LIS;
	for (int i = 0; i < n; i++) {
		if (LIS.size() == 0 || LIS.back() < arr[i]) LIS.push_back(arr[i]);
		else {
			int index = lower_bound(LIS.begin(), LIS.end(), arr[i]) - LIS.begin();
			LIS[index] = arr[i];
		}
	}
	cout << LIS.size();
	return 0;
}