[0x13] 이분탐색

이분탐색

 

정렬되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신, 탐색 범위를 절반으로 줄여가며 찾는 탐색 방식.

 

이분탐색의 주의 사항

 

1. 주어진 배열은 반드시 오름차순으로 정렬되어 있어야 한다.
2. 무한 루프에 빠지지 않게 mid 값을 정해야 한다.

 

정렬된 배열에서 중복된 데이터를 제거할 땐 unique와 erase를 이용한다.

2개의 값들을 묶거나 어느 한쪽의 값을 이분탐색으로 찾아서 시간복잡도를 낮추는 아이디어는 이분탐색 관련 응용문제에서 핵심적으로 많이 나온다.

 

Parametric Search (매개 변수 탐색)

 

조건을 만족하는 최소/최댓값을 구하는 문제(최적화 문제)를 결정 문제로 변환해 이분탐색을 수행하는 방법

최적화 문제를 결정 문제로 바꿀 수 있는지 생각하고 그 결정 문제로 얻어낸 함수가 감소 혹은 증가함수인지를 따져봐야 한다.

 

문제에서 최소/최대 얘기가 있고 범위가 무지막지하게 크거나 시간 복잡도에서 값 하나를 로그로 떨어트리면 될 것 같을때 Parametric Search 풀이를 고민할 수 있다.

 

 

연습 문제

 

1920: 수 찾기

#include <iostream>
#include <algorithm>

int arr[100001];
int n, m;

int bsearch(int &t)
{
	int st = 0;
	int en = n - 1;

	while (st <= en) {
		int mid = (st + en) / 2;

		if (arr[mid] > t) en = mid - 1;
		else if (arr[mid] < t) st = mid + 1;
		else return 1;
	}
	return 0;
}

using namespace std;

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		cin >> arr[i];
	}
	sort(arr, arr + n);
	cin >> m;
	while (m--)
	{
		int t;
		cin >> t;
		cout << bsearch(t) << '\n';
	}

	return 0;
}

 

10816: 숫자 카드 2

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

	vector<int> cards;	
	int n, m, data;

	cin >> n;

	while (n--)
	{
		cin >> data;
		cards.push_back(data);
	}

	sort(cards.begin(), cards.end());

	cin >> m;

	while (m--)
	{
		cin >> data;
		cout << upper_bound(cards.begin(), cards.end(), data) - lower_bound(cards.begin(), cards.end(), data) << " ";
	}

	return 0;
}

 

lower_bound와 upper_bound의 결과를 pair로 반환해주는 equal_range라는 함수가 있다.

이 경우 second - first로 더 간단하게 표현할 수 있다.

 

18870: 좌표 압축

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int arr[1000001];
vector<int> ans;

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n;
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		cin >> arr[i];
		ans.push_back(arr[i]);
	}
	sort(ans.begin(), ans.end());
	ans.erase(unique(ans.begin(), ans.end()), ans.end());

	for (int i = 0; i < n; ++i)
	{
		cout << lower_bound(ans.begin(), ans.end(), arr[i]) - ans.begin() << ' ';
	}

	return 0;
}

 

2295: 세 수의 합

추후 풀어볼 예정

 

1654: 랜선 자르기

#include <iostream>
#include <algorithm>

using namespace std;
using ll = long long;

int k, n;
int arr[1000001];

// 핵심 메소드
bool cut(int v)
{
	ll ans = 0;
	for (int i = 0; i < k; ++i)
		ans += arr[i] / v;
	return ans >= n;
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> k >> n;
	for (int i = 0; i < k; ++i)
		cin >> arr[i];

	sort(arr, arr + k);

	ll st = 0;
	ll en = (1<<31)-1;
	while (st < en)
	{
		ll mid = (st + en + 1) / 2;
		if (cut(mid)) st = mid;
		else en = mid - 1;
	}
	cout << st;

	return 0;
}

 

Parametric Search의 대표 문제.

최적화 문제 : N개를 만들 수 있는 랜선의 최대 길이

->결정 문제 : 랜선의 길이가 X일 떄 랜선이 N개 이상인가 아닌가?

 

기본 문제

 

10815: 숫자 카드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m;
int v1[500001];
int v2[500002];

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> v1[i];

	cin >> m;
	for (int i = 0; i < m; ++i)
		cin >> v2[i];

	sort(v1, v1 + n);

	for (int i = 0; i < m; ++i)
		cout << binary_search(v1, v1 + n, v2[i]) << ' ';

	return 0;
}

 

1822: 차집합

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using ll = long long;

int n, m;
ll arr1[500001];
ll arr2[500001];
vector<ll> answer;

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; ++i)
		cin >> arr1[i];
	for (int i = 0; i < m; ++i)
		cin >> arr2[i];

	sort(arr1, arr1 + n);
	sort(arr2, arr2 + m);

	for (int i = 0; i < n; ++i)
		if (!binary_search(arr2, arr2 + m, arr1[i])) answer.push_back(arr1[i]);

	cout << answer.size() << '\n';
	for (auto& elem : answer)
		cout << elem << ' ';

	return 0;
}

 

16401: 과자 나눠주기

#include <iostream>
#include <algorithm>

using namespace std;
using ll = long long;

int n, m;
int arr[1000001];

// 이 함수를 잘 기억해야 한다
bool cut(int v)
{
	if (v == 0) return true;
	ll ans = 0;
	for (int i = 0; i < m; ++i)
		ans += arr[i] / v;
	return ans >= n;
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m;
	for (int i = 0; i < m; ++i)
		cin >> arr[i];

	sort(arr, arr + m);

	int st = 0;
	int en = 1000000000;
	while (st < en)
	{
		int mid = (st + en + 1) / 2;
		if (cut(mid)) st = mid;
		else en = mid - 1;
	}
	cout << st;

	return 0;
}

 

Parametric Search

최적해가 없는 경우에 0을 출력해야 하므로 cut 메소드에서 0일때도 true를 반환하도록 한다.