Algorithm 공부 #09 - 탐색(이진 탐색)

 

Algorithm 공부 #09 - 탐색(이진 탐색)

 

 

이진 탐색(Binary Search)

    ● 데이터가 정렬된 상태에서 원하는 값을 찾아내는 알고리즘

    ● 구현 및 원리가 비교적 간단하고 시간 복잡도는 O(logn)

    ● 탐색 방법

       1. 현재 데이터셋에서 중앙값 찾기

       2. target이 중앙값보다 작다면 end=middle-1

       3. target이 중앙값보다 크다면 start=middle+1

       4. target==중앙값일 때 데이터 탐색을 종료

 

 

백준 1920번 수 찾기

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

1920번: 수 찾기

 

※ N이 100,00까지이므로 단순 반복문으로는 풀 수 없음 => O(logn)의 이진 탐색 활용하기

● 배열을 입력받고 정렬 후 이진 탐색

 

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

int main() {

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

	int N;
	cin >> N;
	vector<int>A(N, 0);
	for (int i = 0; i < N; i++)
		cin >> A[i];
	sort(A.begin(), A.end()); // 배열 정렬

	int M;
	cin >> M;
	vector<int>find(M, 0);
	for (int i = 0; i < M; i++)
		cin >> find[i];
			
	for (int i = 0; i < M; i++) {
		int target = find[i];
		int start = 0; // 시작 지점은 첫 번째 인덱스 
		int end = N - 1; // 끝 지점은 마지막 인덱스
		while (start <= end) { // 이진 탐색 시작
			int middle = (start + end) / 2;
			int middlevalue = A[middle]; // 중앙값 찾기
			if (target == middlevalue) { // 중앙값이 target이랑 일치할 때
				check = true;
				break;
			}
			else if (target < middlevalue) { // 중앙값이 target보다 크면 중앙값 왼쪽에서 탐색을 해야함
				end = middle - 1;
			}
			else
				start = middle + 1; // 중앙값이 target보다 작으면 중앙값의 오른쪽에서 탐색을 해야 함
		}
		if (check)
			cout << 1 << '\n';
		else
			cout << 0 << '\n';
		check = false; // false로 안 바꿔주면 계속 1이 출력됨
	}
	

}

 

 

백준 2343번 기타 레슨

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

2343번: 기타 레슨

 

※ 블루레이의 크기가 모두 갖ㅌ고 녹화 순서가 바뀌지 않아야 함 -> 이진 탐색의 조건 ※

● 시작 인덱스를 강의의 길이 중 가장 긴 길이, 끝 인덱스를 모든 강의의 총합

● 위와 같이 인덱스를 설정하고 이진 탐색을 돌리기

● 중앙값을 찾고 N개만큼 반복문을 돌려서 크기가 중앙값인 블루레이가 총 몇개 필요한지 확인하기

 

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

int main() {

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

	int N, M;
	int end = 0, start = 0;
	cin >> N >> M;
	vector<int>A(N, 0);

	for (int i = 0; i < N; i++) {
		cin >> A[i];
		if (start < A[i])
			start = A[i]; // 시작 인덱스 값 구하기
		end += A[i]; // 끝 인덱스 값 구하기
	}

	while (start <= end) { // 이진 탐색 시작
		int middle = (start + end) / 2; // middle값 구하기
		int sum = 0; // 총 몇개의 블루레이가 필요한지
		int count = 0; // 구하기 위한 변수들
		for (int i = 0; i < N; i++) {
			if (sum + A[i] > middle) { // middle보다 커지면 블루레이가 더 필요해짐
				count++; // 블루레이의 개수 더 더해주고
				sum = 0; // 새로운 블루레이에 그 다음 변수부터 더하므로 0으로 초기화
			}
			sum += A[i]; // sum값 갱신
		}
		if (sum != 0)
			count++; // sum이 0이 아니라면 마지막 블루레이가 필요함
		if (count > M) // => 현재 middle값이 더 커져야 함,
			start = middle + 1; 
		else
			end = middle - 1;
	}
	cout << start;
}

 

백준 1300번 K번째 수

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

1300번: K번째 수

 

※ k의 범위가 1~min(10^9,N^2)이므로 시간 복잡도가 N^2인 알고리즘은 사용할 수 없음 => 이진 탐색 사용 ※

● 2차원 배열은 N행이 N의 배수로 구성되어 있으므로 k번째 수는 k를 넘지 않음

● 중앙값 크기보다 작은 수가 k보다 작으면 start=중앙값 +1

● 중앙값 크기보다 작은 수가 k보다 크거나 같으면 end=중앙값-1, 정답 변수 = 중앙값 

 

#include<iostream>
using namespace std;

int main() {

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

	long N, K;
	cin >> N >> K;

	long start = 1; // 시작 인덱스
	long end = K; // 종료 인덱스
	long ans = 0; // 정답값

	while (start <= end) {
		long middle = (start + end) / 2; // middle값 설정
		long cnt = 0;

		for (int i = 1; i <= N; i++) {
			cnt += min(middle / i, N); //중앙값보다 작은 수는 몇 개인지 계산
		}

		if (cnt < K)
			start = middle + 1; 
		else {
			end = middle - 1;
			ans = middle; // 정답값 입력
		}

	}
	cout << ans;
}