컨베이어 벨트 위에 있는 패키지들을 D일 안에 한 항구에서 다른 항구로 배송해야 하는 상황을 가정해 봅시다. 벨트 위의 i번째 패키지 무게는 weights[i]로 주어집니다. 매일 배에 패키지를 싣게 되며, 배의 최대 적재 용량을 초과해서 실을 수는 없습니다. 우리가 구해야 할 것은 컨베이어 벨트의 모든 패키지를 D일 이내에 전부 배송할 수 있는 배의 최소 무게 용량입니다.
문제 예시
예를 들어 입력이 [3, 2, 2, 4, 1, 4]이고 D = 3이라면, 출력은 6이 됩니다. 배의 용량이 6일 때 3일 만에 모든 패키지를 배송할 수 있고, 그보다 작은 용량으로는 불가능하기 때문입니다.
- 1일차: 3, 2
- 2일차: 2, 4
- 3일차: 1, 4
접근 방법: 이진 탐색(Binary Search)
이 문제는 이진 탐색을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 배의 용량 후보 범위에서 중간값(mid)을 선택합니다.
- 그 용량으로 D일 안에 모든 패키지를 배송할 수 있는지 확인합니다.
- 배송이 가능하면 더 작은 용량도 가능한지 탐색 범위를 줄이고, 불가능하면 용량을 늘립니다.
검증 함수 solve() 정의
먼저 주어진 용량(maxWeight)으로 모든 패키지를 D일 내에 나눠 실을 수 있는지 확인하는 재귀 함수 solve()를 정의합니다.
- index := 0으로 초기화합니다.
- ships 배열의 각 날짜(i)에 대해 다음을 반복합니다.
- ships[i] := 0으로 초기화합니다.
- index가 weights 배열 길이 미만이면서 ships[i] + weights[index]가 maxWeight 이하인 동안:
- ships[i]에 weights[index]를 더합니다.
- index를 1 증가시킵니다.
- 모든 패키지를 실었다면(index == weights 배열 길이) true를 반환하고, 그렇지 않으면 false를 반환합니다.
메인 로직
- 길이가 D인 ships 배열을 생성하고 0으로 채웁니다.
- maxWeight := 패키지 무게 중 최댓값 (가장 무거운 패키지 하나라도 실을 수 있어야 하므로)
- low := maxWeight, high := maxWeight × 패키지 개수 + 1
- low < high인 동안 반복:
- mid := low + (high − low) / 2
- solve(weights, mid, ships)가 true면 high := mid, 아니면 low := mid + 1
- 반복이 끝나면 high를 반환합니다.
Python 구현 코드
class Solution(object):
def shipWithinDays(self, weights, D):
ships = [0 for i in range(D)]
max_w = max(weights)
low = max_w
high = max_w * len(weights)+1
while low<high:
mid = low + (high-low)//2
if self.solve(weights,mid,ships):
high = mid
else:
low = mid+1
return high
def solve(self,weights,max_w,ships):
index = 0
for i in range(len(ships)):
ships[i] = 0
while index < len(weights) and ships[i]+weights[index]<= max_w:
ships[i] += weights[index]
index+=1
return index == len(weights)
ob = Solution()
print(ob.shipWithinDays([3,2,2,4,1,4],3))입력
[3,2,2,4,1,4] 3
출력
6
정리
이 알고리즘의 시간 복잡도는 O(N × log S)입니다. 여기서 N은 패키지 개수, S는 탐색 범위(최대 용량과 최소 용량의 차이)입니다. 매번 검증 함수 solve()가 O(N) 시간에 동작하고, 이진 탐색이 log S번 반복되기 때문입니다. 이처럼 "최솟값 찾기" 유형의 최적화 문제는 결정 함수와 함께 이진 탐색을 적용하면 깔끔하게 해결할 수 있습니다.