99클럽 코테 스터디 3일차 이분 탐색/ 이진 탐색

Seongbin·2024년 10월 30일

99클럽 코테 스터디

목록 보기

3/24

오늘의 학습 키워드

이분 탐색/이진 탐색(Binary Search)

이분 탐색(이진 탐색)이란?

정렬되어 있는 리스트에서 탐색 범위를 타노스처럼 절반씩 좁혀가며 데이터를 탐색하는 방법이다.

탐색 기법중 하나로, 탐색하고 싶은 범위를 두 부분으로 분할해서 찾는 방법이다.

두 부분으로 계속 분할해서 조건에 맞는지 찾아가기 때문에, 시간 복잡도가 O(log n)으로 매우 빠른편

무조건 정렬되어 있는 상태에서 이분 탐색을 해야 한다!

오늘의 문제

프로그래머스 코딩테스트 연습 > 이분탐색 > 입국심사

https://school.programmers.co.kr/learn/courses/30/lessons/43238

문제 설명

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한사항

입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
심사관은 1명 이상 100,000명 이하입니다.

입출력 예

n	times	return
6	[7, 10]	28

~~입국 심사 참 힘들게 생각한다; 문제 만들기도 힘들겠다~~

문제 생각해보기

위 입출력 예시에 따르면 결론적으로
7분에 1명 -> 10분에 2명 -> 17분에 3명 -> 20분에 4명 -> 21분에 5명 -> 28분에 6명
그래서 28분이라는 값이 결과로 나오는 것이다.

그래서 이걸 왜 이분 탐색으로 푸냐?

이분 탐색을 사용함으로써 탐색 시간을 줄이고, 모든 사람이 최소 시간 안에 심사를 받을 수 있는지 판단할 수 있다.
n의 최대 범위가 100,000명이다. 위에서 내가 예시로 계산한 것처럼 1부터 계산하면 최대 n * max(times) 번의 연산이 필요할 수 있다.

1. 이분 탐색 범위 정하기

def solution(n, times):
	answer = 0
    left = 1
    right = max(times) * n

right는 가장 비효율적으로 심사했을 때 걸리는 시간
가장 긴 심사시간이 소요되는 심사관에게 n 명 모두 심사받는 경우이다.
n이 6, times가 [7, 10]이라면 right = 10 * 6 = 60

2. 이분 탐색을 통해 심사 가능한 인원 수 계산

while left <= right:
        mid = (left+ right) // 2
        people = 0
        
        for time in times:
            people += mid // time
            if people >= n:
                break

while left <= right: :
- 이분 탐색을 사용하여 최적의 시간을 찾기 위해 탐색 범위를 좁혀 나가는 반복문
- left는 가능한 최소 시간, right는 가능한 최대 시간을 나타내며, left가 right보다 작거나 같을 때까지 반복
mid = (left + start) // 2 :
- mid는 현재 탐색 범위의 중간 시간을 의미
- 이 시간 동안 모든 사람이 심사를 받을 수 있는지 여부를 확인
```
people = 0

for time in times:
    people += mid // time
    if people >= n:
        break
```
- for time in times: :
  - times 배열의 각 요소를 하나씩 순회하는 반복문
  - 여기서 times는 각 심사관이 한 사람을 심사하는 데 걸리는 시간을 담고 있는 배열
  - 예를 들어, times = [7, 10]이면 첫 번째 심사관은 한 사람을 심사하는 데 7분, 두 번째 심사관은 10분이 걸린다는 의미
- people은 현재 mid 시간 동안 각 심사관이 심사할 수 있는 사람 수의 합
- 각 심사관이 주어진 시간 동안 몇 명을 처리할 수 있는지를 계산하여(mid // time), 이를 모두 더해 총 심사 가능한 인원 수를 구하기
- 만약 people이 n 이상이면, 이미 모든 사람이 심사를 받을 수 있으므로 반복문을 종료

3. 탐색 범위 조정:

		if people >= n:
            answer = mid
            right = mid - 1
        elif people < n:
            left = mid + 1
            
	return answer

if people >= n: :
- 만약 people이 n명 이상이라면, 현재 mid 시간 내에 모든 사람이 심사를 받을 수 있음.
- 따라서, 더 짧은 시간으로도 심사가 가능한지 확인하기 위해 right = mid - 1로 탐색 범위를 줄임.
- 현재의 mid 값을 answer에 저장.
elif people < n: :
- 반대로, people이 n보다 작다면, 현재 시간 mid로는 모든 사람을 심사하기에 부족함.
- 따라서 더 긴 시간이 필요하므로 left = mid + 1로 탐색 범위를 늘림.
탐색이 끝난 후 모든 사람이 심사를 받을 수 있는 최소 시간인 answer를 return.

입출력 예시 적용시

첫 번째 반복 (탐색 범위: [1, 60])
중간값 계산: mid = (1 + 60) // 2 = 30
mid = 30일 때 각 심사관이 심사할 수 있는 사람 수를 계산:
7분 소요되는 심사관: 30 // 7 = 4명
10분 소요되는 심사관: 30 // 10 = 3명
총 people = 4 + 3 = 7
조건 확인:
people (7)이 n (6)보다 크므로 answer = 30, right = 29

두 번째 반복 (탐색 범위: [1, 29])
중간값 계산: mid = (1 + 29) // 2 = 15
mid = 15일 때 각 심사관이 심사할 수 있는 사람 수를 계산:
7분 소요되는 심사관: 15 // 7 = 2명
10분 소요되는 심사관: 15 // 10 = 1명
총 people = 2 + 1 = 3
조건 확인:
people (3)이 n (6)보다 작으므로 left = 16

.
.
.

다섯 번째 반복 (탐색 범위: [27, 29])
중간값 계산: mid = (27 + 29) // 2 = 28
mid = 28일 때 각 심사관이 심사할 수 있는 사람 수를 계산:
7분 소요되는 심사관: 28 // 7 = 4명
10분 소요되는 심사관: 28 // 10 = 2명
총 people = 4 + 2 = 6
조건 확인:
people (6)이 n (6)과 같으므로 answer = 28, right = 27

여섯 번째 반복 (탐색 범위: [27, 29])
중간값 계산: mid = (27 + 27) // 2 = 27
mid = 27일 때 각 심사관이 심사할 수 있는 사람 수를 계산:
7분 소요되는 심사관: 27 // 7 = 3명
10분 소요되는 심사관: 27 // 10 = 2명
총 people = 3 + 2 = 5
조건 확인:
people (5)이 n (6)보다 작으므로 left = 28

탐색 종료
left=28이 right=27보다 크므로 반복문 종료.
최종 answer 값은 28 -> 모든 사람이 심사를 받는 데 걸리는 최소 시간은 28분.

전체 풀이

def solution(n, times):
    answer = 0
    left = 1
    right = max(times) * n
    
    while left <= right:
        mid = (left+ right) // 2
        people = 0
        
        for time in times:
            people += mid // time
            if people >= n:
                break
        
        if people >= n:
            answer = mid
            right = mid - 1
        elif people < n:
            left = mid + 1
            
    return answer