프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
# 학습 키워드
이진탐색
최적화 문제 접근
시간 복잡도 최적화
# 문제 접근 방법
이 문제는 각기 다른 심사 시간이 주어졌을 떄, 주어진 인원을 가장 짧은 시간 안에 모두 심사하는 시간을 구하는 문제이다. 각 심사관은 고유한 심사 속도를 가지므로 특정 시간 내에 심사가 가능한 인원의 수를 계산하고, 최단 시간을 찾아내야 한다.
1. 이진 탐색을 통한 범위 축소
- 이 문제를 일반적인 반복문을 통해 해결하는 것은 비효율적이므로, 특정 시간 내에 필요 조건을 만족하는지를 기준으로 범위를 축소해가는 이진 탐색기법을 사용했다.
- 최솟값(left)은 가장 빠른 심사 시간을 의미하고, 최댓값(right)은 모든 인원이 가장 느린 심사관에게 심사를 받을 경우의 최장 시간을 의미한다.
2. 심사 가능한 인원 수 계산
- 특정 시간(mid) 내에 각 심사관이 처리할 수 있는 인원의 수를 계산하고, 이를 모든 심사관에 대해 합산하여 해당 시간 내에 처리 가능한 총 인원수(checked)를 구한다.
- 이때 checked가 목표 인원 n보다 크거나 같다면 더 짧은 시간에서도 가능할 수 있으므로 right값을 줄이고, 반대의 경우 left값을 늘리며 탐색 범위를 축소한다.
# 코드 작성
def solution(n, times):
answer = 0
left = min(times)
right = max(times)*n
while left <= right:
mid = (left + right) // 2
checked = 0
for time in times:
checked += mid // time
if checked >= n:
break
if checked >= n:
answer = mid
right = mid - 1
elif checked < n:
left = mid +1
return answer
# 회고
이진 탐색을 활용한 최적화 문제를 풀어본 경험이 있어 기본적인 접근 방식에는 큰 어려움이 없었다.
하지만 이번 문제를 통해 탐색 범위 설정의 유연함이 필요하다는 것을 다시 느꼈다.
가장 짧은 심사 시간부터 시작하는 것이 반드시 최선이 아니고, 최댓값을 정할 때도 문제 상황에 따라 유연하게 설정할 수 있다는 점에서 새로운 인사이트를 얻었다.
목표 인원 이상이 될 경우 반복을 종료하는 조건을 넣어 반복문 효율성을 높이는 방법을 복습할 수 있었다. 이와같은 최적화 조건을 문제에 따라 다르게 적용할 수 있다는 점에서 이진 탐색 문제의 다양한 응용을 다시금 채감했다.
'대외활동 > 항해99' 카테고리의 다른 글
| 99클럽 코테 스터디 8일차 - 백준 2644번 촌수계산 [Python] (4) | 2024.11.04 |
|---|---|
| 99클럽 코테 스터디 5일차 TIL - 백준 2444번 알고리즘수업 너비우선탐색 1 [Python] (1) | 2024.11.01 |
| 99클럽 코테 스터디 4일차 TIL - 백준 24475번 알고리즘수업 깊이우선탐색1 [Python] (1) | 2024.10.31 |
| 99클럽 코테 스터디 2일차 TIL - 백준 11561번 징검다리 [Python] (0) | 2024.10.29 |
| 99클럽 코테 스터디 1일차 TIL - 백준 1072번 게임 [Python] (0) | 2024.10.28 |
