반응형 이분탐색2 [BOJ-3079] 입국심사(JAVA) 백준 3079 입국 심사 https://www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 문제 설명 - 상근이와 친구들은 오스트레일리아로 여행을 떠났다. - 상근이와 친구들은 총 M명이고, 한 줄로 서서 입국심사를 기다리고 있다. - 입국 심사대는 총 N개가 있다. - 각 입국 심사관이 심사를 하는데 걸리는 시간은 Tk이다. - 한 심사대에서는 한 번에 한 사람만 심사를 할 수 있다. - 가장 앞에 서 있는 사람은 비어있는 심사대가 보이면 거기로.. 2021. 10. 12. 탐색 알고리즘 - 이분 탐색(Binary Search) 이분 탐색(Binary Search) 이분 탐색이란? - 정렬되어 있는 데이터에서 원하는 값을 찾을 때 효율적으로 사용할 수 있는 알고리즘이다. - 순차 탐색 보다 훨씬 좋은 성능을 보인다. - n개의 데이터가 주어지면 O(logn)의 시간복잡도를 가진다. - 데이터를 절반씩 나누어 가며 탐색한다. 이분 탐색 과정 - 1. 데이터의 중앙 값과 찾는 값을 비교한다. - 2-1. 찾는 값 > 중앙 값인 경우 중앙 값의 오른쪽 부분을 탐색한다. 2-2. 찾는 값 Right위치가.. 2020. 6. 22. 이전 1 다음 반응형
