해외취준

LeetCode 1011, Capacity To Ship Packages Within D Days 접근 binary-search 로 적절한 배의 weight 용량을 찾는다. 처음 lo, hi 는 max(weights), sum(weight) 이다. 각각 용량에서 옮기는데 걸리는 날짜를 계산해서, 총 날짜보다 적은 시간으로 옮겼으면 lower bound 를 올리고 아니라면 upper bound를 내린다. 사고 릿코드에 binary search 문제 정말 많다. 기본적으로 이런 유형의 최적값 찾기 binary search 는 lower, upper bound 사이에 조건 충족하는 값이 1개 이상 있다고 전제한다. 조건 days 가 5라면 직관적으로 5를 다 써서 옮기는 수 중에 최적이 있을거 같아보인다. 하지만 4일이나 3일만에 옮기고 그때의 배 용량이 최적일수도 있다. 어쨌거나 우리는 최소 날짜를 구하는게 아니라 최소 용량을 구하는거라 과정을 들여다보면 binary search 가 정말 아름답게 그 값을 찾는다는 것을 알 수 있다.. 문제의 조건을 차근차근 이해함에 따라 binary search 로 뭘 찾을지, bound 는 무엇이고 어떤 경우에 bound 를 어떻게 수정할지도 보인다. ...

접근 가능한 속도 1 과 10^7 사이에서 binary search 로 최소 속도를 찾는다. 각 속도마다 train list 를 돌며 걸리는 시간을 계산에서 binary search range 를 조정한다. 시간복잡도 O(Nlog10^7) 사고 적정값을 찾아야 되는 문제는 binary search 로 접근하는 경우가 많은거같다. 무난한 binary search 유형이다. import math class Solution: def minSpeedOnTime(self, dist: list[int], hour: float) -> int: lo, hi = 1, 10000000 minspeed = float('inf') while hi >= lo: mid = (hi + lo) // 2 timetook = 0 for i in range(len(dist) - 1): timetook += math.ceil(dist[i] / mid) timetook += dist[-1] / mid if timetook <= hour: minspeed = mid hi = mid - 1 else: lo = mid + 1 if minspeed == float('inf'): return -1 else: return minspeed