[Algorithm] 6주차 스터디 - 이분탐색과 파라메트릭 탐색

이분 탐색

정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법.

시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다.

단계마다 탐색 범위를 절반씩 줄이기 때문에 시간복잡도는 O(log N)이다.

(순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데리터를 하나씩 확인하는 방법.)

파라매트릭 탐색

주어진 범위 내에서 원하는 값 또는 원하는 조건에 가장 일치하는 값을 찾아내는 알고리즘

최적화 문제를 결정 문제로 바꾸어 풀 수 있게 된다. 즉, 주어진 상황에서 최솟값, 최댓값 등의 특정 값을 구하는 문제를 특정 값이 어떠한 조건을 만족하는지만 확인하면 되는 문제로 바뀐다는 의미이다.

 

c++에서는 이진 탐색으로 원소를 탐색하는 lower_bound, upper_bound 함수를 제공한다.

lower_bound

• 찾으려는 key 값보다 같거나 큰 숫자가 배열의 몇번째에서 처음 등장하는지 확인
• 사용 조건: 리스트가 오름차순 정렬되어있어야 한다.
• 반환형이 iterator이므로 몇 번째 인덱스인지 알고 싶다면 배열의 첫 번째 주소를 가리키는 값을 빼면 된다.

upper_bound

• 찾으려는 key 값을 초과하는 숫자가 배열의 몇 번째에서 처음 등장하는 지 확인
• 사용 조건: 리스트가 오름차순 정렬되어있어야 한다.
• 반환형이 iterator이므로 몇 번째 인덱스인지 알고 싶다면 배열의 첫 번째 주소를 가리키는 값을 빼면 된다

---

<10816 - 숫자카드 2>

https://www.acmicpc.net/problem/10816

여러 개의 정수가 주어졌을 때, 이 수가 적혀 있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구해야 한다.

풀이

상근이가 가지고 있는 카드는 순차적으로 정렬이 되어있지 않아 이분탐색을 할 수 없다. 따라서 sort를 이용해 정렬을 해야한다. 그 후 upper_bound와 lower_bound를 이용해 갯수를 확인하면 된다. lower_bound는 해당 숫자가 처음 등장하는 위치, upper_bound는 해당 숫자가 끝나는 위치를 가리키게 된다. 따라서 upper_bound의 위치와 lower_bound의 위치를 빼주면 해당 숫자에 갯수를 알 수 있다.

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

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL); // 입력 속도 향상

	int n, m, tmp;
	vector<int> n_arr;

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		n_arr.push_back(tmp);
	}

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

	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> tmp;
		cout << upper_bound(n_arr.begin(), n_arr.end(), tmp) - lower_bound(n_arr.begin(), n_arr.end(), tmp) << " ";
	}

	return 0;
}

 

<1654 - 랜선 자르기>

https://www.acmicpc.net/problem/1654

가지고 있는 랜선을 이용해 같은 길이의 랜선을 여러 개 만들어야한다. 특정 개수의 랜선을 만들 때 만들 수 있는 최대 랜선의 길이를 구해야한다.

풀이

랜선의 길이가 될 수 있는 시작점과 끝점을 고려해 이분 탐색을 진행하면 된다. 만들 수 있는 랜선의 길이 범위는 1 에서부터 가지고있는 랜선 중 가장 긴 랜선의 길이이다. (만약 랜선이 1개만 필요하다면 기존 랜선 중 가장 긴 랜선이 답이 되기 때문. )

해당 길이 범위 내에서 만들 수 있는 랜선이 몇 개 인지 확인 한 후 그 결과가 n개보다 많거나 같으면 길이를 늘려야하기 때문에 시작점을 기존의 mid+1로 옮긴다. 반대로 결과가 n개보다 작으면 길이를 줄여야하기 때문에 끝점을 mid-1로 옮기면 된다. 이때 n개의 랜선을 만들 수 있는 길이가 여러개가 나올 수 있다. 문제에서는 최대 랜선의 길이를 찾으므로 조건에 부합하는 길이 중 가장 큰 값을 구하면 된다. 이때 랜선의 길이는 2의 31제곱 - 1 보다 작거나 같은 자연수라는 말이 있으므로 자료형 크기에 주의해야 한다.

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

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL); // 입력 속도 향상

	int k, n;
	long long tmp = 0, ans = 0, maxx = 0;
	vector<long long> v;

	cin >> k >> n;
	for (int i = 0; i < k; i++) {
		cin >> tmp;
		maxx = max(tmp, maxx); //될 수 있는 최대 길이
		v.push_back(tmp);
	}

	long long left = 1, right = maxx, mid;

	while (left <= right) {
		mid = (left + right) / 2;
		long long q = 0; //몫
		for (int i = 0; i < k; i++) {
			q += v[i] / mid;
		}
		if (q < n) { //목표 개수보다 적음 -> 길이 줄이기
			right = mid - 1;
		}
		else { //목표 개수보다 같거나 많음 -> 길이 늘리기
			left = mid + 1;
			ans = max(ans, mid); //최대 길이 선정
		}
	}

	cout << ans;

	return 0;
}

 

<2343 - 기타 레슨>

https://www.acmicpc.net/problem/2343

여러 개의 강의를 블루레이에 담아야한다. 이때 강의의 순서는 바뀌지 않아야하며 블루레이의 개수는 가급적 줄이면서 크기는 작아야한다. 이때 블루레이는 모두 같은 크기이어야 한다.

풀이

1654번 문제와 마찬가지로 이분탐색을 사용할 수 있으며, 가능한 블루레이의 크기의 범위를 정하는 것이 중요하다. 블루레이의 최소 크기는 일단 하나의 강의가 들어갈 수 있어야한다. 따라서 강의 중 가장 길이가 긴 강의가 한 블루레이에 들어갈 수 있어야하므로 가장 긴 강의보다는 블루레이의 길이가 길어야한다. 또한 모든 강의를 하나의 블루레이에 넣을 수도 있는데 해당 블루레이의 크기가 가능한 가장 큰 블루레이의 크기이다. 이 범위를 고려해 이분 탐색을 진행하면 된다.

임의로 블루레이의 크키를 정해서 강의를 담았을 때 블루레이가 m개 이상 필요하다면 블루레이의 크기를 늘려야하므로 시작점을 mid+1로 옮긴다. 반대로, m개 이하가 필요하다면 크키를 줄여야하므로 끝점을 mid -1로 옮긴다. 문제에서 가능한 블루레이의 크기 중 최소를 구해야한다고 했으므로 시작점의 값이 정답이 된다.

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

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL); // 입력 속도 향상

	int n, m, tmp, sum=0, mid, mini=0; //강의 수, 블루레이 개수
	vector<int> v;
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		cin >> tmp;
		sum += tmp; //최대 블루레이 크키. 개수 1개일 때
		mini = max(mini, tmp); //가장 큰 강의 길이 == 최소 블루레이 길이
		v.push_back(tmp);
	}

	int left = mini;
	int right = sum; //가장 긴 강의 ~ 강의 총합

	while (left <= right) {
		mid = (left + right) / 2;
		int x = 0;
		tmp = 0;
		for (int i = 0; i < n; i++) {
			if (tmp + v[i] > mid) {
				tmp = 0;
				x++;
			}
			tmp += v[i];
		}
		if (tmp != 0) {
			x++;
		}

		if (x > m) {//블루레이 크기 늘려야함
			left = mid + 1;
		}
		else { //블루레이 크키 줄여야함
			right = mid - 1;
		}
	}

	cout << left;
	return 0;
}

 

<18113 - 그르다 김가놈>

https://www.acmicpc.net/problem/2343

김밥의 꼬다리를 자른 손질된 김밥들을 일정한 크기로 잘라서 특정 개수보다 많이 만들어야한다. 이때 가장 긴 김밥의 크기를 구해야한다.

풀이

1654, 2343 문제와 비슷하지만 이전에 김밥의 꼬다리를 자르는 과정을 구현해야한다. 김밥의 길이가 2k보다 작으면 한쪽만 자르고, k보다 작으면 그 김밥은 폐기한다. 해당 과정을 거친 값(김밥의 길이)만 벡터에 push한다. 김밥의 길이의 범위는 1에서 손질된 김밥의 가장 큰 길이보다는 작아야한다. 김밥조각이 1개 필요한 경우, 가장 긴 손질된 김밥의 길이가 답이 되기 때문이다.

해당 범위 내에서 임의로 길이를 정했을 때 해당 길이일때 나오는 김밥 조각의 갯수를 확인한다. 이때 김밥조각의 개수가 m개보다 적으면 크키를 줄여야하므로 끝점을 mid -1로 옮긴다. 반대로, 김밥조각의 개수가 m개보다 많거나 같으면 크기를 줄이면서 가장 큰 길이를 구하면 된다.

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

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL); // 입력 속도 향상

	int n, k, m, tmp;
	int left = 1, right = 0, mid;
	vector<int> v;

	cin >> n >> k >> m;

	for (int i = 0; i < n; i++) {
		cin >> tmp;
		if (tmp >= 2 * k) {
			tmp = tmp - 2 * k;
			v.push_back(tmp);
		}
		else if (tmp > k) {
			tmp = tmp - k;
			v.push_back(tmp);
		}
		right = max(tmp, right); //right = 가장 긴 김밥 길이
	}

	int ans = -1;
	while (left <= right) {
		mid = (left + right) / 2;
		int cnt = 0;
		for (int i = 0; i < v.size(); i++) {
			cnt += v[i] / mid;
		}
		if (cnt >= m) { //크기를 줄여야함
			ans = max(mid, ans);
			left = mid + 1;
		}
		else { // 크기를 늘려야함
			right = mid - 1;
		}
	}
	cout << ans;
	return 0;
}