poArlim poArlim

https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 접근 우선 문제의 접근법부터 생각해야 한다. 이 문제를 이분탐색으로 풀게 된 이유는 문제의 범위를 보면 간단히 알 수 있다. 입국 심사를 기다리는 사람이 최대 1,000,000,000 명, 한 명을 심사하는 데 걸리는 시간이 최대 1,000,000,000 분이므로 O(n) 의 시간복잡도 마저 부담스러운 값이 나온다. 이러한 매우 큰 범위가 주어지면, O(logn)..

이분 탐색이란 주어진 데이터 중에서 원하는 데이터를 찾는 탐색 기법 중 하나로, 전체 범위를 두 부분으로 나누는 과정을 반복하여 목표값을 찾아내는 기법이다. 간단하게 예를 들면, 레크레이션 등에서 많이 하는 업다운(Up, Down) 게임을 생각하면 된다. 1~100 숫자 중 사회자가 생각한 숫자를 맞출 때 중간값인 50을 처음 부르고 이후 사회자의 Up, Down 대답에 따라 75, 25 등 나머지 범위의 중간값을 계속 부르는 방식으로 진행된다. 진행 순서 초기 설정 (left = 최소 index 값, right = 최대 index 값) mid 값 설정 (left : 최소 index 값, right : 최대 index 값, mid = (left+right)/2 ) 이분 탐색을 적용하기 위해서는 데이터가 ..