[알고리즘/문제풀이][BOJ 12015번] 가장 긴 증가하는 부분 수열 2

가장 긴 증가하는 부분 수열 2는 이분법을 사용하여(솔직히 이 문제의 핵심은 이분법이 아닌 것 같습니다. 이분법만 아는 것으로는 조금 부족할 수도 있을 것 같습니다.;) 풀 수 있는 문제입니다. 원래 문제인 가장 긴 증가하는 부분 수열(LIS)문제는 동적계획법(완전탐색 + 메모이제이션)으로 해결할 수 있으나 N의 개수가 100만이 되어서 더 빠른 방식의 알고리즘을 고안해야 합니다.

문제를 곰곰히 생각해보면 다음과 같은 통찰을 얻을 수 있습니다. 수열의 어떠한 위치를 탐색하고 있다고 가정하면 우리는 그 이전의 수들로만 구성된 수열들을 상상할 수 있습니다. 어떤 수열은 1개의 숫자로만 이루어질 수도 있고, 어떤 수열을 2개, 3개 혹은 그 이상의 숫자로 만들어질 수 있을 것입니다.  우리가 구하고자 하는 것은 수열의 길이입니다. 따라서 이미 만들어진 그런 수열들의 뒤에 현재 탐색하는 숫자를 붙일 수 있는지만 확인하면 됩니다. 위의 부분 수열들을 길이에 따라 분류하면 각 수열 그룹들의 마지막 위치의 최소 숫자가 해당 그룹 중의 어떠한 수열에 현재 탐색한 숫자를 붙일 수 있는지 결정한다는 사실을 알게 됩니다. 

예로 들어 길이가 2인 수열 그룹의 마지막 최소 숫자가 현재 탐색한 숫자보다 작고 길이가 3인 수열 그룹의 마지막 최소 숫자가 현재 탐색한 숫자보다 크다고 가정해 봅시다. 우리는 현재 탐색한 숫자는 길이가 2인 수열 그룹의 뒤에 붙일 수 있게 되어 길이가 3인 수열을 만들 수 있으며 동시에 길이가 3인 숫자 그룹의 마지막 최소 숫자를 더 작은 값으로 갱신할 수 있게 됩니다.

수열 그룹의 마지막 최소 숫자가 현재 탐색한 숫자와 같은 경우도 고려해야 하지만 위에서 설명한 논리를 활용하여 이 글을 읽는 독자분들이 충분히 생각하실 수 있을거라고 생각합니다. 

이러한 사실을 바탕으로 수열 그룹을 매 탐색마다 갱신하면 최종적으로 만들 수 있는 수열의 최대 길이를 구할 수 있게 됩니다.

문제에서는 이분법을 사용할 수 있다고 하였는 데 이 이분법은 위의 수열 그룹의 마지막 최소 숫자를 배열에 저장했을 때 오름차순의 형태를 가진다는 사실에서 현재 탐색한 숫자로 각 수열 그룹의 마지막 최소 숫자를 갱신하는 데 사용하라고 의도한 것 같습니다.(;;;;;)

작성한 코드는 다음과 같습니다.

#include<stdio.h>
#pragma warning(disable : 4996)
//https://ark-hive.tistory.com

int N;
int A[1000020];
int B[1000020];
int K=1;
//i길이의 증가수열들의 가장 작은 마지막 숫자를 저장.

int main(void) {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &A[i]);
	}

	B[1] = A[0];

	for (int i = 1; i < N; i++) {
		int lo, hi;
		int ans;
		lo = 1;
		hi = K;
		ans = 0;
		while (lo <= hi) {
			int mid = (lo + hi) / 2;
			if (B[mid] < A[i]) {
				lo = mid + 1;
			}
			else if (B[mid] == A[i]) {
				ans = -1;
				break;
			}
			else {
				ans = mid;
				hi = mid - 1;
			}
		}
		if (ans == -1) continue;

		if (ans != 0) {
			B[ans] = A[i];
		}
		else {
			B[++K] = A[i];
		}
	}

	printf("%d\n", K);
}

문제는 다음의 링크에서 확인할 수 있습니다.

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