백준 알고리즘 중급 - 이분 탐색 (연습)

이쪽으로 갔다가 저쪽으로 갔다가

하나 정리해둘 것 : 최댓값의 최솟값, 최솟값의 최댓값을 구하라고 하면 이분 탐색이라고 보면 된다.

중급 1 마지막 강의다. 여기까지 정리하고, 당분간은 자소서 쓰기 바쁠 것 같다.

정리 시작!

-

* 기타 레슨 (mid) : 가능한 블루레이의 길이 중 최소를 구하는 문제다. 

2343번: 기타 레슨

- n개의 레슨을 m개의 블루레이에 저장하려고 한다. 구하려는 최댓값의 최솟값은 블루레이의 크기다.

- left는 레슨 중 가장 긴 값을 넣는다. 그러면 모든 레슨을 하나씩 담을 수 있을 거다. right에는 모든 레슨 길이의 합을 구한다. 하나의 블루레이에 모든 레슨을 넣을 수 있을 거다. check 함수에서는 블루레이의 크기가 mid일 때, 나눠지는 그룹의 수가 m이하면 최솟값을 갱신하고 크기를 줄인다. m보다 크면 크기를 키운다. 크기를 줄이면 더 많은 그룹을 만들 수 있고, 크기를 키우면 그룹의 수가 적어진다.

#include <iostream>
using namespace std;

int n, m;
int a[100000];

bool check(int mid) {
	int cnt = 1;
	int sum = 0;
	for (int i = 0; i < n; i++) {
		if (sum + a[i] > mid) {
			cnt += 1;
			sum = a[i];
		}
		else {
			sum += a[i];
		}
	}
	return cnt <= m;
}

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

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

 

* 구간 나누기 2 (mid) : 구간 점수의 최댓값을 최소로 하는 값을 찾는 문제다.

13397번: 구간 나누기 2

- 구간 점수는 구간에 속한 수의 최대와 최소의 차이를 말한다. n개 수가 주어지고, m개 이하의 구간으로 나눴을 때, 각 구간의 최대와 최소의 차이를 구하고 그것들 중 최대를 최소로 만들고 싶은 거다 (아 머리야)

- left는 0이다. 구간 안에 같은 값이 있으면 0이 나오고 0 미만은 나올 수 없다. right는 정확히 말하면 가장 큰 값에 1을 빼주는 거지만, 그냥 가장 큰 값으로 해놓고 풀었다. check 함수에서는 구간의 점수가 mid일 때, 가능한 그룹의 수가 m이하인 경우 더 작은 값으로, m보다 클 경우 더 큰 값으로 탐색을 이어간다.

#include <iostream>
using namespace std;

int n, m;
int a[5000];

bool check(int mid) {
	int t1 = a[0];
	int t2 = a[0];
	int cnt = 1;
	for (int i = 1; i < n; i++) {
		if (t1 < a[i]) t1 = a[i];
		if (t2 > a[i]) t2 = a[i];
		if (t1 - t2 > mid) {
			cnt += 1;
			t1 = a[i];
			t2 = a[i];
		}
	}
	return cnt <= m;
}

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

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

- (이게 왜 정답률이 65%나 되는지 모르겠다.) mid에 따라 그룹을 나눠주는 함수 구현이 좀 이해하기 어려웠다. t1에 최댓값, t2에 최솟값을 저장하고 그 차이가 mid보다 클 때 cnt에 +1을 해주고 t1, t2를 현재 위치의 값으로 초기화 해줬다. mid가 최대니까 t1-t2가 mid보다 크면 같은 그룹에 있는 게 아니니 이런 식으로 해주는 것 같다.

 

* 배열에서 이동 (mid) : (1,1)에서 (n,n)으로 이동할 때, 거쳐간 수의 최댓값과 최솟값의 차이가 최소가 되도록 해야 한다.

1981번: 배열에서 이동

- left는 0, right는 200이다. 200은 문제에서 주어진 배열의 원소 범위다. check 함수에서는 mid를 기준으로 최대와 최소를 잡아주는데 x를 최소, x+mid를 최대라고 할 때 x가 0일 때부터 시작해서 x+mid <= 200 일 때까지 bfs로 일일이 확인해주면 된다. n값의 범위도 100까지니까 다 확인할 여유가 된다.

- 마지막 항을 방문했다면 더 작은 값으로, 방문하지 않았다면 더 큰 값으로 탐색을 이어간다.

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

int n;
int a[100][100];
bool c[100][100];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };

bool bfs(int mn, int mx) {
	if (a[0][0] < mn || a[0][0] > mx) return false;
	memset(c, false, sizeof(c));
	queue<pair<int, int> > q;
	q.push(make_pair(0, 0));
	c[0][0] = true;
	while (!q.empty()) {
		int x, y;
		tie(x, y) = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
			if (c[nx][ny] == false) {
				if (mn <= a[nx][ny] && a[nx][ny] <= mx) {
					c[nx][ny] = true;
					q.push(make_pair(nx, ny));
				}
			}
		}
	}
	return c[n - 1][n - 1];
}

bool check(int mid) {
	for (int mn = 0; mn + mid <= 200; mn++) {
		if (bfs(mn, mn + mid)) {
			return true;
		}
	}
	return false;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> a[i][j];
		}
	}
	int left = 0;
	int right = 200;
	int ans = 200;
	while (left <= right) {
		int mid = (left + right) / 2;
		if (check(mid)) {
			right = mid - 1;
			ans = min(ans, mid);
		}
		else {
			left = mid + 1;
		}
	}
	cout << ans << '\n';
	return 0;
}

- bfs를 시작할 때, 출발점인 a[0][0]이 최솟값보다 작거나, 최댓값보다 크면 모순이므로 바로 건너 뛰어줘야 한다는 것에 주의하자.

 

* k번째 수 (mid) : n*n 크기의 배열에 a[i][j] = i*j와 같은 방식으로 원소를 넣고, 이를 일차원 배열에서 오름차순 했을 때, k번째 수가 무엇인지 구하는 문제다.

1300번: K번째 수

- 문제에서 인덱스는 1부터 시작한다고 했으므로 left는 1, right는 n*n이 된다. 

- 관건은 mid일 때 몇 번째에 오는지 구하는 것이다. a[i][j] = i*j인 것을 활용해서 mid를 i행으로 나눠주면 mid보다 작은 값의 개수를 구할 수 있다. 계산 과정에서 mid의 개수까지 포함하므로 mid까지 나열한 끝 인덱스를 구할 수 있다. n범위에 있는 값만 포함해야 하므로, min(m,mid/i)와 같이 처리해줘야 한다는 것에 주의한다.

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

long long n, k;

int main() {
	cin >> n >> k;
	long long left = 0;
	long long right = n*n;
	long long ans = 0;
	while (left <= right) {
		long long mid = (left + right) / 2;
		long long sum = 0;
		for (int i = 1; i <= n; i++) {
			sum += min(n, mid / i);
		}
		if (sum >= k) {
			ans = mid;
			right = mid - 1;
		}
		else {
			left = mid + 1;
		}
	}

	cout << ans << '\n';

	return 0;
}

 

* 놀이공원 (mid) : 이분 탐색을 활용한 센스가 필요한 문제였다.

1561번: 놀이 공원

- n명의 어린이가 m개의 놀이기구를 탄다고 했을 때, 마지막 아이가 타게 될 놀이기구의 번호를 구하는 문제다.

- left는 0, right는 n의 최댓값*운행 시간의 최댓값으로 두면 된다. mid 분이 지났을 때, 몇 명의 아이가 탔는지 구하고, (end)이를 이용해서 mid 분에 놀이기구를 타는 가장 작은 번호를 구한다. (begin)

- n이 begin보다 작다면, 이미 n명을 넘은 것이므로 작은 값으로 이동하고, n이 end보다 크다면 아직 n명이 되지 않았으므로 더 큰 값으로 이동한다. 만약 둘다 아니라면 n이 begin과 end 사이에 있다는 것이므로, begin을 +1 해가면서 마지막 아이가 타게 될 놀이기구의 번호를 구하면 된다.

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

int main() {
	long long n, m;
	cin >> n >> m;
	vector<int> a(m);
	for (int i = 0; i < m; i++) cin >> a[i];
	long long left = 0;
	long long right = 60000000000LL;
	while (left <= right) {
		long long mid = (left + right) / 2;
		long long begin, end;
		begin = end = 0;
		end = m;
		for (int i = 0; i < m; i++) {
			end += mid / a[i];
		}
		begin = end;
		for (int i = 0; i < m; i++) {
			if (mid % a[i] == 0) {
				begin -= 1;
			}
		}
		begin += 1;
		if (begin > n) {
			right = mid - 1;
		}
		else if (end < n) {
			left = mid + 1;
		}
		else {
			for (int i = 0; i < m; i++) {
				if (mid % a[i] == 0) {
					if (begin == n) {
						cout << i + 1 << '\n';
						return 0;
					}
					begin += 1;
				}
			}
		}
	}
	return 0;
}

 

이분 탐색도 bfs처럼 패턴을 익히면 크게 어렵지 않게 풀 수 있을듯 하다.

큰 사이즈의 문제에 적합한 경우가 많으니, 잘 익혀두도록 하자. 

정리 끝!