백준 12015 가장 긴 증가하는 수열(이진 탐색)

코드

#include <iostream>   
#include <vector>
 
using namespace std;
 
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
 
	int N; cin >> N;
	vector<int> arr;
	arr.reserve(N);
	for (int i = 0; i < N; i++)
	{
		int a; cin >> a;
		if (arr.empty() || a > arr.back()) arr.push_back(a);
		else
		{
			int index = lower_bound(arr.begin(), arr.end(), a) - arr.begin();
			arr[index] = a;
		}
	}
 
	cout << lis.size() << '\n';
 
	return 0;
}

코드 자체는 간단합니다. 이진탐색은 직접 구현하지 않고 lower_bound 함수를 사용했어요.

알고리즘

다음과 같은 알고리즘으로 LIS의 길이를 구하게 됩니다.

1. 일단 첫 입력은 push_back
2. 새로운 입력 a가 arr의 마지막 원소보다 크면 push_back
3. 작으면 기존 arr의 a보다 큰 원소 중에서 최솟값(Lower Bound)을 찾아서 a와 교체 ⇒ a 가 그 자리를 대신함

교체를 하는 이유

여기서 직관적으로 이해되지 않는 부분이 있었는데 LIS의 길이를 표현하기 위한 벡터(위 코드에서 arr)에 새로운 요소를 추가할 때 왜 기존 원소와 교체하는가? 에 대한 것이었습니다.

이것이 이상하게 보이는 이유는 이렇습니다.

1. 증가하는 수열을 구해야 하는 문제는 수열의 순서가 보존되어야 한다.
2. 나중에 들어온 요소가 arr에 추가될 때 arr의 마지막 요소보다 작으면 원래 배열에서의 자기 순서를 지키지 않고 앞에 있는 원소와 교체하면서 새치기가 일어난다.
3. 이렇게 새치기를 하면 수열의 순서가 보존되지 않는 것 아닌가? 이것이 LIS(가장 긴 증가하는 수열)과 무슨 상관?

일단 다음을 명심해야 합니다

arr는 실제 LIS가 아니고 LIS의 길이만을 추적하기 위한 배열임

먼저 입력 배열이 애초에 증가하는 수열이고 길이가 N인 경우를 생각해 봅니다. 항상 마지막 요소보다 큰 요소가 새로 들어오므로 (입력 배열의 길이) = (LIS의 길이) = N이 되는 것은 자명합니다.

그러면 이번에는 길이가 N+M인데 N>M인 수열이 입력 배열인 경우를 생각해 봅니다. 이 때 뒤의 길이 M인 부분의 첫 요소가 앞의 길이 N인 부분의 첫 요소보다 작다고 가정해 봅시다. 예를 들어 N=5, M=3인 다음과 같은 수열입니다.

{3, 4, 5, 6, 7, 1, 2, 3}

이 수열을 앞의 5개와 뒤의 3개로 자르고 앞 수열은 A, 뒷 수열은 B라고 할게요.

A: {3, 4, 5, 6, 7} B: {1, 2, 3}

전체 수열의 LIS의 길이는 {3, 4, 5, 6, 7}로 이루어진 5입니다.

일단 위 코드의 알고리즘대로 arr를 처리하면 최종 결과는

{1, 2, 3, 6, 7}

이 될 것입니다. arr 가 LIS 길이를 잘 추적하고 있습니다. 이번에는 앞의 3부터 7까지의 배열은 그대로 두고, 뒤의 배열 B: {1, 2, 3}이 {1, 2, 3, 4, 5, …} 처럼 더 길어지는 상상을 해봅시다. 즉

A: {3, 4, 5, 6, 7} B: {1, 2, 3, 4, 5} 전체 수열: {3, 4, 5, 6, 7, 1, 2, 3, 4, 5}

LIS의 길이는 언제 변할까요? B와 B 이후에 나타나는 LIS의 길이가 5보다 커질 때 입니다. 위 경우에는 arr 가 {1, 2, 3, 4, 5} 로 정확히 B로 대체됩니다.

여기서 알 수 있는 것은 arr의 길이가 더 늘어나려면 기존 arr의 길이보다 긴 새로운 증가하는 수열이 나타나야 한다는 것입니다.

즉 arr의 값 교체가 앞에서부터 일어나다가 기존 요소가 전부 새로운 요소로 교체됐다면 그때 기존의 arr의 길이와 동일한 LIS가 B와 B 이후에서 발견된 것입니다.

교체 전: {3, 4, 5, 6, 7} 교체 후: {1, 2, 3, 4, 5}

에서 보는것처럼 교체된 수열의 가장 뒤의 값(=7)은 교체되기 전의 수열의 가장 뒤의 값(=5)보다 작기 때문에 B의 뒤에 어떤 수가 왔을때 LIS가 길어질 가능성이 더 높아집니다. 이렇게 해서 LIS의 길이를 잘 추적할 수 있습니다.