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

[문제 링크]

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

---

LIS를 구하는 문제였다. 다만 수열의 길이가 1,000,000 으로 매우 길기 때문에 이중 for문을 돌려서 답을 얻는 일반적인 방법으로 구현할 경우 시간복잡도가 매우 커지게 된다.

따라서 다른 방법으로 구현해야 하는데... 예를 들어 다음과 같은 수열이 있다고 하자.

 

1  2  3  3  1  4  6  5

 

방법은 다음과 같다.

우선 첫 번째 인덱스에 있는 원소는 바로 추가한다.

1

 

그 다음 인덱스를 확인하여 LIS의 마지막 원소와 비교한다.

다음 인덱스의 원소는 2, LIS의 마지막 원소는 1 이다.

다음 인덱스의 원소가 더 클 경우 LIS의 맨 끝에 원소를 추가한다.

1  2

 

그 다음 인덱스를 확인하여 LIS의 마지막 원소와 비교한다.

다음 인덱스의 원소가 3이므로 2보다 크기 때문에 LIS의 맨 끝에 원소를 추가한다.

1  2  3

 

그 다음 인덱스를 확인하여 LIS의 마지막 원소와 비교한다.

다음 인덱스의 원소는 3, LIS의 마지막 원소 또한 3으로 같다.

다음 인덱스의 원소가 같거나 더 작을 경우 LIS 배열에서 정렬이 깨지지 않는 위치에 값을 덮어씌운다.

이때 LIS 배열은 오름차순으로 정렬되어 있는 상태이므로 이분 탐색을 통해 값을 바꿀 위치를 O(logN) 시간만에 찾을 수 있다.

1  2  3

 

이런 방식으로 배열의 모든 원소를 탐색하면 된다.

다음 인덱스의 원소는 1, LIS의 마지막 원소는 3 이다. 따라서 LIS 배열에서 값을 바꿀 위치를 찾는다.

1  2  3

 

다음 인덱스의 원소는 4, 마지막 원소는 3 이다. 따라서 LIS 배열 맨 끝에 4를 추가한다.

1  2  3  4

 

다음 인덱스의 원소는 6, 마지막 원소는 4 이다.

1  2  3  4  6

 

다음 인덱스의 원소는 5, 마지막 원소는 6이다.

1  2  3  5  6

 

LIS 배열의 원소는 총 5개. 따라서 LIS 의 길이는 5임을 알 수 있다.

 

이 방식으로 구현하게 되면 LIS가 어떻게 이루어져 있는지는 알 수 없지만, LIS 길이를 구하는데 있어서는

크기가 N인 배열의 모든 원소에 대하여 이분탐색을 수행하는 최악의 경우에도 O(NlogN)의 시간복잡도를 보장해준다.

---

#include <iostream>
using namespace std;

int N;
int arr[1000001];
int LIS[1000001];

int binary_search(int start, int end, int num) {
	int ret;

	while (start <= end) {
		int mid = (start + end) / 2;
		if (LIS[mid] >= num) {
			ret = mid;
			end = mid - 1;
		}
		else
			start = mid + 1;
	}

	return ret;
}

int getLIS() {
	int length = 1;
	
	LIS[0] = arr[0];
	for (int i = 1; i < N; i++) {
		if (LIS[length - 1] < arr[i]) {
			LIS[length] = arr[i];
			length++;
		}
		else {
			int idx = binary_search(0, length - 1, arr[i]);
			LIS[idx] = arr[i];
		}
	}

	return length;
}

int main(void) {
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> arr[i];

	cout << getLIS() << endl;

	return 0;
}