이것이 코딩테스트다 - 7) 이진탐색

 

 

 

7.1_1) 부품 찾기 (이진탐색 이용)

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


using namespace std;

int n, m;
vector<int> items;
vector<int> order;

int binarySearch(int Left, int Right, int number) {//이진탐색 재귀함수 이용

	if (Left > Right) return 0;//끝까지 갔는데 없으면 0 리턴

	int mid = (Left + Right) / 2;

	if (items[mid] == number) {//찾으면 1리턴
		return 1;
	}
	else if (items[mid] < number) {//범위에 없다면 범위를 다시 정해서 탐색
		binarySearch(mid + 1, Right, number);
	}
	else {
		binarySearch(Left, mid - 1, number);
	}



}
int main() {
	cin >> n;

	for (int i = 0; i < n; i++)//부품목록 입력받기
	{
		int number;
		cin >> number;
		items.push_back(number);
	}
	sort(items.begin(), items.end());

	cin >> m;
	for (int i = 0; i < m; i++)//구매목록 입력받기
	{
		int number;
		cin >> number;
		order.push_back(number);
	}

	for (int i = 0; i < m; i++)//이진탐색 함수를 이용해서 부품이 있으면 Yes, 없으면 No 출력
	{
		if (binarySearch(0, n - 1, order[i]) == 1) cout << "Yes" << " ";
		else cout << "No" << " ";
	}


	return 0;




}

 

 

 

7.1_2) 부품 찾기 (계수정렬 이용)

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


using namespace std;

int n, m;
int items[1000001];
int order[100000];

int main() {
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int number;
		cin >> number;
		items[number]++;
	}

	cin >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> order[i];
	}

	for (int i = 0; i < m; i++)
	{
		if (items[order[i]] != 0) cout << "Yes" << " ";
		else cout << "No" << " ";
	}


	return 0;

}

 

 

 

 

7.1_3) 부품 찾기 (set함수 이용(값이 알아서 정렬되어 저장))

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


using namespace std;

int n, m;
set <int> items;
vector<int> order;
int main() {
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int number;
		cin >> number;
		items.insert(number);
	}

	cin >> m;
	for (int i = 0; i < m; i++)
	{
		int number;
		cin >> number;
		order.push_back(number);
	}

	for (int i = 0; i < m; i++)
	{
		if (items.find(order[i]) != items.end()) cout << "Yes" << " ";//setÇÔ¼ö¿¡ ÀÖÀ¸¸é
		else cout << "No" << " ";
	}


	return 0;

}

 

 

 

7.2) 떡볶이 떡 만들기 (대표적인 이진탐색 문제)

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


using namespace std;

int Max = -2147000000;
int n, m;
vector<int> height;

int binarySearch(int Left, int Right, int Max) {//이진탐색
	while (Left <= Right) {
		int sum = 0;
		int mid = (Left + Right) / 2;
		for (int i = 0; i < n; i++)//생산한 떡의 양 계산
		{
			if (height[i] > mid) sum += (height[i] - mid);
		}
		if (sum < m)Right = mid - 1;//주어진 길이보다 생산한 떡의 양이 작다. 
		else {//주어진 길이보다 크거나 같은 떡을 생산할 수 있다. 
			Max = mid;
			Left = mid + 1;
		}
	}

	return Max;
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		int number;
		cin >> number;
		height.push_back(number);
	}
	sort(height.begin(), height.end());

	cout << binarySearch(0, height[n - 1], Max) << endl;


	return 0;
}

 

 

 

 

경우의 수가 많아지는 문제에 이진탐색을 생각해보자!