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

1. 문제

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

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

 

2. 알고리즘 분류

• 이분 탐색
• 가장 긴 증가하는부분 수열

 

3. 소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX_N 1000001

using namespace std;

int nums[MAX_N];
vector<int> ans;

// 이진 탐색 알고리즘
int binary_search(int n)
{
	int low = 0;
	int high = ans.size() - 1;
	int ret = MAX_N;

	while (low <= high) {
		int mid = (low + high) / 2;
		int num = ans[mid];

		if (num >= n) {
			ret = min(ret, mid);
			high = mid - 1;
		}
		else
			low = mid + 1;
	}

	return ret;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	// N : 수열 A의 크기
	int N;
	cin >> N;

	// 수열 입력
	for (int i = 0; i < N; i++)
		cin >> nums[i];

	// 첫번째 인자 push
	ans.push_back(nums[0]);

	// 수열 순서대로 탐색
	for (int i = 1; i < N; i++) {

		/*
		* ans 벡터의 마지막 값보다 수열 값이 크면
		* 그대로 해당 값push
		* ex) 현재 ans = [1, 10]이고 수열 다음 숫자가 20일 경우, ans = [1, 10, 20] 으로 추가
		*/
		if (ans.back() < nums[i])
			ans.push_back(nums[i]);
		/*
		* ans 벡터의 마지막 값보다 해당 수열 값이 작으면,
		* Binary Search를 통해 해당 수열 값이 대체될 수 있는 ans 벡터의 index 값 구하기
		* ex) 현재 ans = [1, 10, 20]이고 수열 다음 숫자가 8일 경우, ans = [1, 8, 20]으로 변경
		* 위의 예제에서 수열 순서가 뒤섞이므로, 실질적인 부분 수열은 아니지만 가장 긴 부분수열의 길이는 유지된다.
		* 해당 풀이는 정확한 부분 수열 값을 구하는 방법은 아니지만, 가장 긴 부분수열의 길이를 구하는 방법은 맞다.
		*/
		else {
			int idx = binary_search(nums[i]);
			ans[idx] = nums[i];
		}
	}

	// 정답 출력
	cout << ans.size();

	return 0;
}

 

4. 유용한 알고리즘

1) 이진 탐색(이분 탐색, Binary Search)

1. O(logN) 방법으로 배열에서 특정 값을 찾는 알고리즘

vector<int> ans;

// 이진 탐색 알고리즘
int binary_search(int n)
{
	int low = 0;
	int high = ans.size() - 1;
	int ret = MAX_N;

	while (low <= high) {
		int mid = (low + high) / 2;
		int num = ans[mid];

		if (num >= n) {
			ret = min(ret, mid);
			high = mid - 1;
		}
		else
			low = mid + 1;
	}

	return ret;
}