[Do it! 알고리즘 코딩테스트: Chpater 5. 탐색(Search)] 이진 탐색(Binary Search)

본 포스팅은 Do it! 알고리즘 코딩테스트: C++편을 토대로 공부한 내용을 정리하기 위한 포스팅입니다.

https://github.com/KwonKiHyeok/Do_it_Alogrithm_Coding_Test_with_Cpp

GitHub - KwonKiHyeok/Do_it_Alogrithm_Coding_Test_with_Cpp: Do it! 알고리즘 코딩 테스트: C++편

 

이진 탐색(Binary Search)

 이진 탐색(Binary Search) 알고리즘은 정렬된 배열이나 리스트에서 특정한 값을 빠르게 찾는 알고리즘이다. 시간 복잡도는 O(log⁡n)으로, 데이터의 크기가 커질수록 선형 탐색(Linear Search)보다 훨씬 빠르게 동작한다.

 

이진 탐색의 원리

1. 중간값 선택: 배열의 가운데 요소를 선택한다.
2. 비교: 찾고자 하는 값과 중간값을 비교한다.
   • 찾는 값이 중간값과 같으면 탐색 종료.
   • 찾는 값이 중간값보다 작으면 중간값 기준으로 왼쪽 데이터셋에서 다시 탐색.
   • 찾는 값이 중간값보다 크면 중간값 기준으로 오른쪽 데이터셋에서 다시 탐색.
3. 반복: 찾을 때까지 위 과정을 반복하거나, 찾는 값이 없으면 탐색을 종료한다.

 

이진 탐색의 시간 복잡도

• 최선의 경우 (Best case): O(1) → 첫 번째 비교에서 값을 찾는 경우
• 평균 및 최악의 경우 (Average/Worst case): O(log⁡n) → 검색 범위를 절반으로 줄여나가기 때문

 

이진 탐색을 사용할 수 있는 조건

• 데이터가 반드시 정렬되어 있어야 한다.
• 배열이나 리스트에 인덱스를 통해 접근 가능해야 한다.

 

 

// Baekjoon Online Judge Problem. 1920

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

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M, num;
	cin >> N;
	vector<int> A(N);
	
	for (int i = 0; i < N; i++)
		cin >> A[i];
	
	sort(A.begin(), A.end());

	cin >> M;

	for (int i = 0; i < M; i++) {
		cin >> num;
		int start = 0, end = A.size() - 1;
		int sol = -1;

		while (start <= end) {
			int mid = (start + end) / 2;

			if (A[mid] == num) {
				sol = 1;
				break;
			}
			else if (A[mid] <= num)
				start = mid + 1;
			else
				end = mid - 1;
		}

		if (sol == 1)
			cout << '1' << '\n';
		else
			cout << '0' << '\n';
	}

	return 0;
}

 

 

// Baekjoon Online Judge Problem. 2343

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

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M;
	cin >> N >> M;
	int start = 0, end = 0;

	vector<int> lesson(N);

	for (int i = 0; i < N; i++) {
		cin >> lesson[i];
		
		if (start < lesson[i])
			start = lesson[i];

		end += lesson[i];
	}

	while (start <= end) {
		int mid = (start + end) / 2;
		int count = 0, sum = 0;

		for (int i = 0; i < lesson.size(); i++) {
			if (sum + lesson[i] > mid) {
				count++;
				sum = 0;
			}
			sum += lesson[i];
		}

		if (sum != 0)
			count++;

		if (count > M)
			start = mid + 1;
		else
			end = mid - 1;
	}
	
	cout << start << '\n';

	return 0;
}

 

 

// Baekjoon Online Judge Problem. 1300

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

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, k;
	cin >> N >> k;

	int start = 1, end = k;
	
	while (start <= end) {
		int mid = (start + end) / 2;
		int count = 0;
		
		for (int i = 1; i <= N; i++) {
			count += min(mid / i, N);
		}

		if (count < k)
			start = mid + 1;
		else
			end = mid - 1;
	}

	cout << start << '\n';

	return 0;
}

 

 이 문제는 이진 탐색으로 중앙값보다 작은 수의 개수를 세면서 범위를 절반씩 줄이는 방법으로 B[k] 값을 구한다. 다시 말해 작은 수의 개수가 k - 1개인 중앙값이 정답이 되는 문제이다. 이진 탐색으로 해결하는 문제라는걸 알았지만 어떻게 적용해야 하는지가 많이 어려웠다.

 

 중앙값을 각 행으로 나누어서 구한 몫이 중앙값보다 작은 수의 개수를 나타냄을 알 수 있다. 따라서 min(mid / i, N)으로 count 변수를 계속 추가한다. 최종적으로 start가 end를 초과하는 순간 start 값이 정답이 된다.