이분탐색 문제 풀이[Binary Seach PS]

1. 이분탐색 문제 푸는 방법

2. 이분탐색 문제 풀이

---

 

1. 이분탐색 문제 푸는 방법

 

이분탐색을 이용하여 풀 수 있는 문제는 어떤 유형이고

문제를 해결하기 위해서는 어떻게 이분탐색을 이용할까?

 

-> 정답을 구할 수 없지만, X가 가능한지 아닌지 알아내는 것은 가능한 문제들이 있다.

 

1. 정답을 구하는 문제(최적해 문제)
A에서 B까지 가는 가장 빠른 시간을 구하는 것
2. 가능한지 살펴보는 문제(Yes/No 문제)
A에서 B까지 X라는 시간으로 이동할 수 있나?

1.를 풀 수 있으면 2 또한 풀 수 있다.

2를 풀 수 있을때, 1을 풀 수 있을까?

풀 수 있다.
X라는 시간에 작은 것부터 순서대로 대입하면 No가 계속 나오다. Yes가 나오는 시점이 해가 된다.
=어느 한 기점을 기준으로 yes와 no가 달라지는 기점.(어떤 기준 X를 가지고 Yes/No로 나누어지는 문제)

(고로 1,2 둘중에 하나만 해결 가능해도 둘 다 해결 가능하다.)

위의 2번을 이분탐색으로 문제를 풀 경우 
1~10억까지 있다고 했을 때, 절반씩 확인하면 log10억 번만 반복하면 확인 가능하다.

이분탐색으로 문제를 풀 경우 결정하는 것.
1. 가능한 정답의 최솟값(left)
2. 가능한 정답의 최댓값(right)
3. 정답을 하나 결정했을 때, 이것이 문제의 조건에 맞는지 검사하는 방법(Yes or NO 형태의 함수)
4. 조건에 맞는 경우 정답을 더 크게 해야 하는지 작게 해야 하는지 결정.

문제유형 : 
최솟값의 최댓값을 구해라
최댓값의 최솟값을 구해라.
거의 대부분 이분탐색으로 구할 수 있다.

 

2. 이분탐색 문제 풀이

1790 수 이어 쓰기 2 : https://www.acmicpc.net/problem/1790

풀이 :

가장 쉬운 방법 : 1부터 n까지 문자열로 만든 후 찾는다.
하지만 n <= 1억 이므로 너무 많은 시간과 큰 메모리가 필요하다.

1~N까지의 길이를 실제로 문자열로 만들지 않아도 구할 수 있음을 이용한다.
1~9 : 9
10~99 : 90
100~999 : 900
등을 구간별로 구하고 이후 구간을 구하면 된다.

중간값을 선택 후 길이를 k와 비교하고 다른 구간을 탐색한다.

#include <iostream>
#include <tuple>
#include <cmath>
#include <string>
using namespace std;

pair<int, int> check(int a) {				//a의 첫번째 길이와 마지막 길이 리턴
	int size = 0, tmp = a, min = 0, max = 0;
	for (int i = 0; tmp != 0; ++i) {		//a의 사이즈 구하기		ex) a = 3774, size = 4
		size++;
		tmp /= 10;
	}
	for (int i = 1; i < size; ++i)			//1 ~ 10^(size-1)-1의 길이 구하기, ex) a = 3774, 1~999까지 길이
		max += 9 * pow(10, i - 1) * (i);

	max += (a - pow(10, size - 1) + 1)*size;	//10^(size-1) ~ a, ex) a = 3774, 1000~3774 까지의 길이
	min = max - size + 1;					// 
	return { min, max };
}

void binary_search(int left, int right, int k) {
	int min, max, mid = (left + right) / 2;
	tie(min, max) = check(mid);

	if (k > max)
		binary_search(mid + 1, right, k);
	else if (k < min)
		binary_search(left, mid, k);
	else {							//정답 구간일 경우 답 출력
		string s = to_string(mid);
		cout << s[k - min];
		return;
	}
}

int main(void) {
	int n, k;
	cin >> n >> k;
	int min, max;
	tie(min, max) = check(n);
	if (max < k)	//범위 확인
		cout << -1;
	else binary_search(1, n, k);
}

1654 랜선자르기 : https://www.acmicpc.net/problem/1654

풀이 :

left = 1, right = 랜선 길이의 최댓값
mid 길이로 랜선을 잘랐을때 
k개 보다 같거나 많다면 mid 보다 큰 길이로 잘라보고
k개 보다 적다면 mid 보다 작은 길이로 잘라본다.

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

long long n, k;
vector<long long> v;

long long check(long long num) {
	long long ret = 0;
	for (auto a : v)
		ret += a / num;
	return ret;
}

long long binary_search(long long start, long long end) {
	if (start > end) return 0;
	long long ret = 0;
	long long mid = (start + end) / 2;
	long long cnt = check(mid);
	//cout << "start : "<< start << " mid : " << mid <<  ", end : " << end<<   ", cnt : " << cnt << endl;
	if (cnt >= k) {
		ret = mid;
		ret = max(ret, binary_search(mid + 1, end));
	}
	else
		ret = max(ret, binary_search(start, mid - 1));
	return ret;
}
int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> k;
	for (long long i = 0; i < n; ++i) {
		long long num;
		cin >> num;
		v.push_back(num);
	}
	//sort(v.begin(), v.end());
	cout << binary_search(1, *max_element(v.begin(), v.end()));
}

 

2805 나무자르기 :  https://www.acmicpc.net/problem/2805

체크 함수 수정.

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

long long n, k;
vector<long long> v;

long long check(long long num) {
	long long ret = 0;
	for (auto a : v)
		ret += max(0, (int)(a - num));
	return ret;
}

long long binary_search(long long start, long long end) {
	if (start > end) return 0;
	long long ret = 0;
	long long mid = (start + end) / 2;
	long long cnt = check(mid);
	//cout << "start : "<< start << " mid : " << mid <<  ", end : " << end<<   ", cnt : " << cnt << endl;
	if (cnt >= k) {
		ret = mid;
		ret = max(ret, binary_search(mid + 1, end));
	}
	else
		ret = max(ret, binary_search(start, mid - 1));
	return ret;
}
int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> k;
	for (long long i = 0; i < n; ++i) {
		long long num;
		cin >> num;
		v.push_back(num);
	}
	//sort(v.begin(), v.end());
	cout << binary_search(0, *max_element(v.begin(), v.end()));
}

 

2110 공유기 설치 : https://www.acmicpc.net/problem/2110

체크 함수, 범위, 정렬
설치 간격(길이)을 기준으로 이분 탐색
check함수 :
0번집에 공유기를 설치했다고 생각하고 일정한 간격 이상일 경우 계속 설치,
설치한 개수 리턴

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

long long n, k;
vector<long long> v;
//0번집에 공유기를 설치했다고 생각하고 일정한 간격 이상일 경우 계속 설치,
long long check(long long num) {
	long long cnt = 1;
	for (int i = 1, last = 0; i < n; ++i) {
		if (v[i] - v[last] >= num) {
			last = i;
			cnt++;
		}
	}
	return cnt;
}

long long binary_search(long long start, long long end) {
	if (start > end) return 0;
	long long ret = 0;
	long long mid = (start + end) / 2;
	long long cnt = check(mid);
	//cout << "start : "<< start << " mid : " << mid <<  ", end : " << end<<   ", cnt : " << cnt << endl;
	if (cnt >= k) {
		ret = mid;
		ret = max(ret, binary_search(mid + 1, end));
	}
	else
		ret = max(ret, binary_search(start, mid - 1));
	return ret;
}
int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> k;
	for (long long i = 0; i < n; ++i) {
		long long num;
		cin >> num;
		v.push_back(num);
	}
	sort(v.begin(), v.end());
	cout << binary_search(1, *max_element(v.begin(), v.end()) - *min_element(v.begin(), v.end()));
}

 

1939 중량제한 : https://www.acmicpc.net/problem/1939

풀이 : 

최대 무게를 결정(이분탐색) -> 그 무게로 갈 수 있는지를 검사(그래프탐색)
그래프 탐색에서 이동가능 노드 탐색 시 메모리초과 이유
-> 10000x10000으로 탐색할경우 시간 + 메모리 초과
-> 인접리스트를 사용하여 방문가능을 100000 검사

-> 10000x10000으로 탐색할경우 시간 + 메모리 초과
int maps[10001][10001];
for (int next = 1; next <= n; ++next) {
	if (maps[now][next] >= num && visited[next] == false) {
		q.push(next);
		visited[next] = true;
	}
}
        
        
-> 인접리스트를 사용하여 방문가능을 100000 검사
vector<pair<int, int> > maps[10001];
for (auto &p : maps[now]) {
	int next = p.first;
	int cost = p.second;
	if (cost >= num && visited[next]==false) {
		q.push(next);
		visited[next] = true;
	}
}

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

long long n, m;
int st, en;
vector<pair<int, int> > maps[10001];
bool visited[10001];

bool check(int num) {
	queue<int> q;
	memset(visited, 0, sizeof(visited));
	visited[st] = true;
	q.push(st);
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		if (now == en) return true;
		for (auto &p : maps[now]) {
			int next = p.first;
			int cost = p.second;
			if (cost >= num && visited[next]==false) {
				q.push(next);
				visited[next] = true;
			}
		}
	}
	return false;
}

long long binary_search(long long start, long long end) {
	if (start > end) return 0;
	long long ret = 0;
	long long mid = (start + end) / 2;
	//cout << "start : "<< start << " mid : " << mid <<  ", end : " << end<<   ", check : " << check(mid) << endl;
	if (check(mid)) {
		ret = mid;
		ret = max(ret, binary_search(mid + 1, end));
	}
	else
		ret = max(ret, binary_search(start, mid - 1));
	return ret;
}
int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	for (long long i = 0; i < m; ++i) {
		int n1, n2, n3;
		cin >> n1 >> n2 >> n3;
		maps[n1].push_back(make_pair(n2, n3));
		maps[n2].push_back(make_pair(n1, n3));
	}
	cin >> st >> en;
	cout << binary_search(1, 1000000000);
}

 

2022 사다리 : https://www.acmicpc.net/problem/2022

식을 정리 할 경우 -> c를 d로 정의할 수 있음.
이 식에서 x, y를 상수로 생각하면 d가 커질수록 c는 작아지고, d가 작아질수록 c는 커지는 것을 알 수 있음.

C를 d로 표현

실수에서의 이분탐색
left = mid
right = mid으로 변경하고 이때 항상 left<=right이므로
for(int k=0; k<10000; ++k)
while(abs(right-left) > 1e-4)
if (end - start <= 0.0001) return 0;
으로 종료 조건을 표현한다.
특히 포문으로 할 경우 정밀도는 1/2^10000이다.