이분 탐색아 반갑다..? 또 너구나..?
이분탐색을 완벽하게 이해하고 넘어가겠다는 항해99의 공부 방식에 맞춰 오늘도 이분탐색을 시작해보려고 한다...
근데 사실 아직 다 이해 못한거같기도.. mid가 뭘 의미하는지를 찾는게 가장 어려워...
프로그래머스 입국심사 문제 풀이
문제
n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.
처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.
모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.
입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.
[제한사항]
입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
심사관은 1명 이상 100,000명 이하입니다.
문제 해석하기
- 일단, 해당 문제가 이분탐색을 사용해야 한다는 점을 확인한다
- 이분 탐색을 통해 "모든 사람이 심사를 받는 데 걸리는 최소 시간"을 구해야 한다
- 이분 탐색이 효과적인 이유는, 특정 시간 동안 각 심사관이 몇 명의 사람을 처리할 수 있는지를 계산해 전체 인원을 처리할 수 있는지를 판별할 수 있기 때문이다
- start와 end를 찾아서 설정한다
- start는 1로 시작하도록 하고,
- end는 Times 배열에서 받은 값 중 가장 큰 값 max를 찾아 n명을 모두 해당 심사관이 모두 심사하는 최악의 경우로 설정한다.
- mid가 의미하는 것이 무엇인지를 생각해보기
- mid는 우리가 설정한 시간 범위 안에서 현재 예상되는 최소 심사 시간을 의미한다고 생각했다
- 각 반복을 mid시간 동안 심사관이 몇명을 처리할 수 있는 지를 합산하여 n명 이상인지 확인하도록 했다.
- n명 이상을 처리할 수 있다면, 시간을 줄여 탐색한다 (왼쪽 반 탐색)
- n명을 처리하지 못한다면, 시간을 늘려 탐색하도록 한다 (오른쪽 반 탐색)
def solution(n, times):
# 시작 시간과 끝 시간을 설정
start = 1
end = max(times) * n
answer = end # 최악의 경우 시간을 초기 답안으로 설정해둠
while start <= end:
# 현재 예상 최소 시간
mid = (start + end) // 2
# mid 시간 동안 심사할 수 있는 총 인원 수
people_checked = sum(mid // time for time in times)
if people_checked >= n:
# 충분한 인원을 처리할 수 있으면 시간을 줄여서 더 최적의 값을 찾음
answer = mid
end = mid - 1
else:
# 인원을 처리할 수 없다면 시간을 늘려야 함
start = mid + 1
return answer
이분탐색에서 mid의 의미를 찾는 방법
이분 탐색을 오늘까지 3개의 문제를 풀어보면서 mid를 찾는 것이 가장 어렵다는 것을 느낄 수 있었다.
그래서 문제를 통해서 mid가 무엇을 의미하는지를 찾는 방법에 대해서 조금 생각을 해보았다.
1. 문제에서 "최소값"이나 "최대값"을 찾는 요구 확인하기
이분 탐색 문제는 보통 특정 범위 내에서 최소 혹은 최대값을 찾으라는 요구가 있다.
예를 들어, 이 문제에서는 모든 사람이 심사를 받을 수 있는 최소 시간을 찾는 것이 목표이다.2. mid가 어떤 값의 "최대/최소"를 나타내는지 정의하기
mid는 시작과 끝의 중간값으로, 가능한 후보 시간 값입니다.
문제를 풀기 위한 특정 시간 범위를 설정한 후, mid는 이 시간 범위의 중간값으로 간주되어 해당 시간 내에 작업을 완료할 수 있는지를 판단하는 기준이 된다.3. mid의 의미를 찾기 위한 질문들
mid가 특정 시간이라면, "이 시간 내에 모든 사람을 처리할 수 있는가?" 같은 질문을 던져 볼 수 있다.
이 질문을 통해 mid가 "최소 시간"이라는 의미를 가지며, 이 시간을 만족하도록 각 심사관이 처리할 수 있는지 계산하게 된다.4. mid와 목표 비교하는 조건식 작성
이 문제에서는 mid 시간 동안 각 심사관이 몇 명을 처리할 수 있는지 확인한 후, 그 합이 총 인원보다 크거나 같은지를 확인한다.
이렇게 mid의 의미를 계산하는 기준으로 만들면, start, end 값을 조정해 범위를 좁혀가며 목표에 도달할 수 있다.
- 보통 이분 탐색 문제에서 mid는 문제 상황에 맞춰 최소 혹은 최대수치와 같은 특정 기준의 후보값으로 설정된다.
- mid의 역할을 정해놓고 그 역할을 충족하는 지 확인하는 방법을 반복적으로 연습하게 되면, 다양한 문제에서 mid의 의미를 파악하는데 더 익숙해질 수 있을 것이다.
오늘의 회고
이분 탐색을 3일째 공부하면서, 이분 탐색의 방식에 대해서 조금씩 익숙해져가고 있는 것 같다. 일단 문제를 확인할 때 해석하면서 이분탐색을 활용해야한다는 것을 일차적으로 내가 먼저 결정할 수 있다는 점에서 성장하고 있다고 생각한다.
이분 탐색에 대해서 더 공부하고 좀더 복잡한 문제를 만나도 쉽게 해결해내고 싶다는 생각이 들었다.
