Algorithm/이분탐색

[BOJ 7795] 먹을 것인가 먹힐 것인가

https://www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 아이디어 A 원소의 크기가 B의 원소보다 작은 쌍을 구해야 한다. 먼저 순차 탐색을 생각해봤다. A의 모든 원소마다 B의 모든 원소를 비교하면 (1 ≤ N, M ≤ 20,000)이므로 시간 복잡도가 O(N^2) 즉, O(4*10^8) 이므로 1초 내에 풀 수 없다. 탐색 시간을 줄이기 위해 이분탐색을 이용한다. B를 정렬 후 A 원소들을 기준으로..

[Algorithm] 이분 탐색(Binary Search)

류호석님의 패스트캠퍼스 강의 자료를 참고하여 정리한 글입니다. 출처 : https://github.com/rhs0266/FastCampus 탐색 수열과 탐색 대상 x가 주어진 경우 x가 존재하는가? x 이하 or 미만 or 이상 or 초과 하는 원소의 개수는? x랑 가장 가까운 원소는 무엇인가? ... 모든 원소를 보면서 x와 비교를 하는 경우 O(N)의 시간복잡도로 위의 질문을 대답할 수 있다. 그런데 만약 정렬이 된 수열이 주어진다면 어떻게 될까? 정렬된 수열과 탐색 대상 x가 주어진 경우 이분 탐색을 이용하면 더 빠르게 위의 질문을 대답할 수 있다. 이분 탐색 (Binary Search) 정렬이 보장되는 배열에서 기준 x를 가지고 범위를 "이분"하면서 탐색하는 방법 정렬이 보장된다는 의미는 무엇일까..