フルナビゲーションTLE→デュアルナビゲーション考慮

条件関数==単調関数→二分探索

決定関数==二分化&&条件関数==単調関数→一般問題→決定問題→パラメータ探索

1. Merge Sort

は常にO(Nlogn)O(Nlogn)O(Nlogn)O(Nlogn)O(Nlogn)の時間的複雑さを保証するため、安定した実行速度を保証する必要がある場合に使用される.

再帰呼び出し方式でリストのコピーを継続するため、メモリ領域が増加するという欠点がある.

1. 정렬되지 않은 리스트를 절반으로 잘라 두 개의 리스트로 나눈다.
2. 생성된 두개의 리스트를 Merge Sort 알고리즘을 재귀 호출하여 정렬한다.
3. 정렬된 두개의 리스트를 다시 하나의 정렬된 리스트로 Merge한다.

int	arr[MAX_N + 10];
int	sorted[MAX_N + 10];

void	merge(int left, int mid, int right)
{
	int	i, j, k;

	i = left;
	j = mid + 1;
	k = left;
	while (i <= mid && j <= right)
	{
		if (arr[i] <= arr[j])
			sorted[k++] = arr[i++];
		else
			sorted[k++] = arr[j++];
	}
	if (i > mid) // 남아있는 값들 일괄 복사
	{
		while (j <= right)
			sorted[k++] = arr[j++];
	}
	else
	{
		while (i <= mid)
			sorted[k++] = arr[i++];
	}
	for (i = left; i <= right; ++i) // 배열 복사
		arr[i] = sorted[i];
}

void	merge_sort(int left, int right)
{
	int mid;

	if (left < right)
	{
		mid = (left + right) / 2;
		merge_sort(left, mid);
		merge_sort(mid + 1, right);
		merge(left, mid, right);
	}
}

2. Quick Sort

は、最悪の場合、O(N 2)O(N^2)O(N 2)の時間的複雑さを有する.

は平均的にO(Nlogn)O(Nlogn)O(Nlogn)の時間的複雑さを有する.

一般的には、迅速にソートできます.

1. 리스트 내에 임의의 원소를 선택하여 pivot이라 명합니다.
2. pivot을 기준으로 pivot보다 작은 원소는 좌측으로, pivot보다 큰 원소는 우측으로 이동합니다.
3. pivot을 제외하고 좌측 리스트와 우측 리스트를 Quick Sort 알고리즘을 재귀 호출하여 정렬합니다.
4. pivot으로 나눠진 리스트의 크기가 1이 될 때까지 반복합니다.

void	quick_sort(int left, int right)
{
	int start, end, pvt;

	start = left;
	end = right;
	pvt = arr[(left + right) / 2];
	if (left >= right)
		return ;
	while (start <= end)
	{
		while (arr[start] > pvt)
			++start;
		while(arr[end] < pvt)
			--end;
		if (start <= end)
		{

			arr[start] ^= arr[end];
			arr[end] ^= arr[start]
			arr[start] ^= arr[end];
			++start;
			--end;
		}
	}
	quick_sort(left, end);
	quick_sort(start, right);
}

3. Binary Search

二分探索の必要条件

は入力範囲が広く、アプリケーションを完全にナビゲートするとTLEが生成される.

入力を簡単にソートすることができる.

探索範囲の最小値と最大値は明確である.

閲覧範囲はソート形式であるか、O(n)O(n)O(n)以内に問題要求の数値を算出することができる.

条件関数の形式は単調関数です.

int	binary_search(int arr[], int start, int end, int target)
{
	int	mid;

	while (start <= end)
	{
		mid = (start + end) / 2;
		if (arr[mid] == target)
			return (mid);
		elseif (arr[mid] < target)
			start = mid + 1;
		else
			end = mid - 1;
	}
	return (-1);
}

int	main(void)
{
	int arr[4] = {0, 1, 2, 3};
	int ans;

	ans = binary_search(arr, 0, 3, 2);
	return (0);
}

int count_by_range(vector<int> &v, int left, int right)
{
	vector<int>::iterator right_idx = upper_bound(v.begin(), v.end(), right);
	vector<int>::iterator left_idx = lower_bound(v.begin(), v.end(), left);
	return (right_idx - left_idx);
}

3-1. パラメータ検索:一般問題→決定問題

これは

最適化問題を決定問題に変換して解決する方法である.

ex)特定の条件を満たす最適値をすばやく検索する最適化問題

は一般に符号化試験において、パラメータ探索問題はバイナリ探索によって解決することができる.

の広い探索範囲から見ると,バイナリ探索を思い出すべきである.

誤差範囲内で

の特定の条件を満たす最適値を見つけることが望ましい.(最小、最大、最小)

Binary Search + YES/NO Problem

の特定の条件を満たすエンクロージャ(組み合わせ)は、複数であってもよい.

結晶関数は二分化し,条件関数の形式は単調関数である.

下限→最小値を求める。

最小値がxであれば、x以上の値に対して条件を満たす.

int	solve(void)
{
	int	start, end, mid, ans;

	start = MIN;
	end = MAX;
	ans = mid = 0;
	while (start <= end)
	{
		mid = (start + end) / 2;
		if (verify(mid))
		{
			ans = mid;
			end = mid - 1;
		}
		else
			start = mid + 1;
	}
	return (ans);
}

Upper Bound→最大値を求めます。

最大値がxである場合、x以下の値については、いずれも条件を満たす.

int	solve(void)
{
	int	start, end, mid, ans;

	start = MIN;
	end = MAX;
	ans = mid = 0;
	while (start <= end)
	{
		mid = (start + end) / 2;
		if (verify(mid))
		{
			ans = mid;
			start = mid + 1;
		}
		else
			end = mid - 1;
	}
	return (ans);
}

[参照]パラメータ検索
[BOJ]白準2110ルータを取り付ける