O(NSum)에서 O(Nlog Sum)으로 단축한 Binary Search on Answer 최적화

Allocate Minimum Number of Pages | Binary Search on Answer

Jaspreet singh2026년 6월 21일4분intermediate

AI 요약

Context

연속된 도서 배분 시 학생 1인당 할당되는 최대 페이지 수를 최소화해야 하는 문제 상황. 모든 가능한 페이지 제한을 전수 조사하는 Brute Force 방식의 높은 시간 복잡도로 인한 성능 저하 발생.

정답의 범위가 [max(books), sum(books)] 내에 존재한다는 Monotonic 특성을 활용한 Binary Search on Answer 설계
특정 페이지 제한값 X에 대해 m명의 학생으로 배분이 가능한지 검증하는 Feasibility Function 구현
검증 결과가 YES일 경우 더 작은 최댓값을 찾기 위해 Search Space의 상한선을 하향 조정
검증 결과가 NO일 경우 배분 가능성 확보를 위해 Search Space의 하한선을 상향 조정
O(1) Space Complexity를 유지하며 정답 범위 내 최적값을 탐색하는 반복적 분할 정복 로직 적용

실천 포인트

1. 문제 요구사항에 '최솟값의 최대화' 또는 '최댓값의 최소화' 키워드가 있는지 확인

2. 임의의 값 X에 대해 True/False를 판별할 수 있는 Feasibility Check 함수 설계 가능 여부 검토

3. 정답의 범위(Low, High)를 명확히 정의하여 Search Space 설정

태그