백준 알고리즘 중급 - 이분 탐색

binary search

이분 탐색에 대해 ARABOJA

-

* 이분 탐색 (binary serach) : 어떤 기준을 가지고 yes or no 판별을 반복하여 답을 구하는 방법이다.

 - 가능한 정답의 최솟값 (left), 최댓값 (right), yes or no 판별 함수가 필요하고 조건에 따라 값이 더 커지거나 작아진다.

 - 어느정도의 포맷이 있어서 좀 적응하면 문제의 해결의 틀은 비교적 쉽게 잡힌다. 바로 예제 풀어보자.

 

* 수 이어 쓰기 (mid) : n까지 수를 이어서 썼을 때, k번째 수가 뭔지 찾는 문제다.

1790번: 수 이어 쓰기 2

- n의 범위가 1억, k의 범위가 10억까지 가능하기 때문에 n개를 다 붙여서 판별하는 건 어림도 없다.

- 이 문제의 핵심은 n까지 나열한 수의 길이를 구하는 함수다. 짜는 요령을 잘 기억해두자.

- left를 1, right를 n으로 두고 시작한다. mid까지 나열한 수의 길이를 구하고, k보다 작으면 더 큰 수를 구하고, k보다 크면 k를 포함하고 있으므로 mid 값을 저장하고 더 작은 수를 구한다. 그럼 누적해서 나열한 길이가 k보다 같거나 큰 수의 끝인 ans를 구할 수 있다.

- 다시 말해 ans값은 k번째 수를 포함하고 있는 정수 값이다. 예를 들어 ans가 123이면, k번째 수는 1, 2, 3 중에 하나인 것이다. ans값 자체의 길이에 ans까지 나열한 수의 길이를 빼준 뒤에 k를 더하고 1을 빼주면 정확한 k번째 수를 구할 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

long long calc(int n) {
	long long ans = 0;
	for (int start = 1, len = 1; start <= n; start *= 10, len++) {
		int end = start * 10 - 1;
		if (end > n) {
			end = n;
		}
		ans += (long long)(end - start + 1)*len;
	}
	return ans;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	long long k;
	cin >> n >> k;

	if (calc(n) < k) {
		cout << -1;
		return 0;
	}

	int left = 1;
	int right = n;
	int ans;
	while (left <= right) {
		int mid = (left + right) / 2;
		if (calc(mid) < k) {
			left = mid + 1;
		}
		else {
			ans = mid;
			right = mid - 1;
		}
	}

	string a = to_string(ans);
	long long l = calc(ans);
	cout << a[a.size() - l + k - 1] << '\n';

	return 0;
}

 

* 랜선 자르기 (mid) : k개의 랜선을 잘라 n개 이상의 랜선을 만드는 길이의 최댓값을 구하는 문제다.

1654번: 랜선 자르기

- left는 1, right는 주어진 랜선에서 가장 긴 랜선으로 잡으면 된다. 함수는 주어진 길이로 나눴을 때, n개 이상의 랜선으로 나눌 수 있는지 확인하고 된다면 더 긴 쪽으로, 안 된다면 더 작은 쪽으로 이동하면서 값을 확인해주면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int k, n;
long long a[10000];
bool check(long long div) {
	int cnt = 0;
	for (int i = 0; i < k; i++) {
		cnt += a[i] / div;
	}
	return cnt >= n;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> k >> n;
	long long lmax = 0;
	for (int i = 0; i < k; i++) {
		cin >> a[i];
		if (lmax < a[i]) lmax = a[i];
	}

	long long left = 1;
	long long right = lmax;
	long long ans = 0;
	while (left <= right) {
		long long mid = (left + right) / 2;
		if (check(mid)) {
			if (ans < mid) {
				ans = mid;
			}
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}

	cout << ans << '\n';
	return 0;
}

 

* 나무 자르기 (mid) : 랜선 자르기와 거의 똑같은 문제라고 보면 된다.

2805번: 나무 자르기

- left는 0, right는 가장 긴 나무로 잡는다. 함수는 위의 문제와 같이 주어진 길이로 나무를 잘랐을 때 얻을 수 있는 길이의 합이 주어진 값 이상인지 확인하고, 된다면 더 높은 위치로, 안 된다면 더 낮은 위치로 이동하면서 확인한다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
int a[1000000];

bool check(int h) {
	long long ans = 0;
	for (int i = 0; i < n; i++) {
		if (a[i] > h) {
			ans += a[i] - h;
		}
	}
	return ans >= m;
}

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

	cin >> n >> m;
	int tmax = 0;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		if (tmax < a[i]) tmax = a[i];
	}
	int left = 0;
	int right = tmax;
	int ans = 0;
	while (left <= right) {
		int mid = (left + right) / 2;
		if (check(mid)) {
			if (ans < mid) ans = mid;
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}

	cout << ans << '\n';
	return 0;
}

 

* 공유기 설치 (mid) : 가장 인접한 두 공유기 사이의 거리가 최대가 되도록 설치하는 문제다.

2110번: 공유기 설치

- left는 1, right는 첫 집과 마지막 집 거리의 차이다. 함수는 주어진 길이를 최대로 c개의 공유기를 설치하는지 확인하는데, c개 이상도 상관 없다. c개 이상 설치하면 c개가 되도록 제거해도 공유기 간의 최대 거리가 커지면 커지지 짧아지지는 않기 때문이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, c;
vector<int> a;

bool check(int x) {
	int cnt = 1;
	int last = a[0];
	for (int i = 0; i < n; i++) {
		if (a[i] - last >= x) {
			cnt += 1;
			last = a[i];
		}
	}
	return cnt >= c;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> c;
	int t;
	for (int i = 0; i < n; i++) {
		cin >> t;
		a.push_back(t);
	}
	sort(a.begin(), a.end());
	int left = 1;
	int right = a[n - 1] - a[0];
	int ans = 0;
	while (left <= right) {
		int mid = (left + right) / 2;
		if (check(mid)) {
			if (ans < mid) ans = mid;
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}

	cout << ans << '\n';
	return 0;
}

 

* 중량 제한 (mid) : 섬에서 섬으로, 한 번의 이동에서 옮길 수 있는 중량의 최대값을 구하는 문제다.

1939번: 중량제한

- 섬과 섬 사이에 여러 다리가 존재할 수 있으므로, dfs나 bfs를 활용하여 모든 지점을 방문해주면서 조건을 확인한다.

- left는 1, right는 가장 큰 중량으로 뒀다. 함수는 주어진 중량으로 입력 받은 섬과 섬 사이를 이동할 수 있는지 판별한다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

int n, m;
int x, y;
vector<pair<int, int> > a[10001];
bool c[10001];

bool check(int now, int w) {
	if (c[now]) {
		return false;
	}

	c[now] = true;
	if (now == y) {
		return true;
	}

	for (auto &p : a[now]) {
		int next = p.first;
		int weight = p.second;
		if (weight >= w) {
			if (check(next, w)) {
				return true;
			}
		}
	}

	return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;

	int wmax = 0;
	int from, to, w;
	for (int i = 0; i < m; i++) {
		cin >> from >> to >> w;
		a[from].push_back(make_pair(to, w));
		a[to].push_back(make_pair(from, w));
		if (wmax < w) wmax = w;
	}

	cin >> x >> y;

	int left = 1;
	int right = wmax;
	int ans = 0;
	while (left <= right) {
		int mid = (left + right) / 2;
		memset(c, false, sizeof(c));
		if (check(x,mid)) {
			if (ans < mid) ans = mid;
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}

	cout << ans << '\n';
	return 0;
}

 

* 사다리 (mid) : 식을 유도해내기만 하면 쉽게 풀 수 있었다. 실수는 어떻게 이분 탐색하는지 배웠다.

2022번: 사다리

- 일단 피타고라스 정리를 활용해서 식을 유도해야 하는데 사진으로 설명을 대신한다.

- 그 다음엔 이거대로 이분탐색 하면 된다. 근데 실수는 정수처럼 이분탐색하면 안 된다. mid와 mid-1, mid와 mid+1 사이에 값이 있을 수도 있기 때문이다. left, right 값을 실수로 두고, mid-1,mid+1가 아닌 mid를 넣어주면 된다. '1e-n' 기호를 이용해 조건에 따라 오차를 생각해주면 된다.

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

int main() {
	double x, y, c;
	scanf("%lf %lf %lf", &x, &y, &c);

	double left = 0;
	double right = min(x, y);
	while (abs(right - left) > 1e-3) {
		double d = (left + right) / 2.0;
		double h1 = sqrt(x*x - d*d);
		double h2 = sqrt(y*y - d*d);
		double k = (h1*h2) / (h1 + h2);
		if (k > c) {
			left = d;
		}
		else {
			right = d;
		}
	}

	printf("%.3lf\n", left);

	return 0;
}

- 실수로 이분 탐색하는 요령도 익혀두자.

- 뒤에 삼분 탐색은 벡터를 사용하길래,, 일단 미뤄둔다. 굳이 지금 수준에 익혀 둘 필요는 없는 것 같다.

-

뭔가 현타가 오는 요즘.. 

그래도 꾸준히 할건 해나가자.

정리 끝!