알고리즘/Binary Search2 [이분탐색] 프로그래머스 입국심사 - 파이썬 Python https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 생각하기 처음에는 모든 경우를 살펴보자는 생각이었지만 n의 개수와 시간이 너무 커서 불가했다 이분 탐색으로 풀기 위해서 기준을 정해야 하지만 어떤 기준을 정해야할지 생각하는데에 오래 걸렸다 이분 탐색의 기준을 심사 시간이라고 가정 = 각 심사관이 사람을 처리할 수 있는 시간 right (max)는 가장 오랜 시간이 걸리는 심사관이 모든 사람(n)을 처리했을 때, .. 2022. 2. 1. [Binary Search] 이진 탐색이란 무엇인가? 나누면서 탐색? 반으로 나누면서 원하는 값을 찾아가는 탐색방법 - 전제는 정렬 시작점 중간점 끝점이 제일 중요하다 중간점을 기준으로 찾으려는 값이 작으면 중간점 아래로 찾고 중간점을 기준으로 찾으려는 값이 크면 중간점 위로 찾는다 중간점과 찾으려는 값이 같으면 idx 토해내고 시작점이 끝점보다 더 커지는 순간이 온다면 찾지 못했다는 뜻이니 None을 반환 시작점이 왜 끝점보다 클때 그만? 요소가 한개인 경우에는 시작점과 끝점이 같다 한개인 경우에 그게 찾는 수가 아니라면 끝점이 -1 되거나 시작점이 +1 될 것이다 두 경우 모두다 시작점이 끝점을 초과시이므로 그 때 끝낸다 시간복잡도 절반으로 나누어지면서 찾아가기 때문에 트리 모양이다 O(logN) 재귀를 통해 푸는 방법 def binary_search(array, l,.. 2021. 9. 17. 이전 1 다음