Binary-Search

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 를 어떻게 수정할지도 보인다. ...

LeetCode 1146, Snapshot Array 접근 length 로 2차원 배열(arr)을 초기화한다. snap_id 를 기억하는 변수를 지정한다. 차지하게 되는 총 메모리는 length + S (number of calls of set()) 이다. set 마다 해당 index 에 현재 snap_id 와 value 를 추가한다. 모든 range 내의 i에 대하여 arr[i] 는 오름차순으로 정렬되어있기에 get() 에서 bisect 로 적절한 snap_id 를 찾아 해당하는 value 를 리턴한다. 사고 처음에 이 코드로 냈는데 get과 set 모두 엉성하다.. bisect에 대한 예쁜 이해가 없어서 그렇다. ...

접근 dictionary 에 키에 해당하는 리스트를 만들고 오름차순의 input 을 받는다. get 부를때 해당 키의 리스트에서 binary search 로 최댓값을 찾는다. 사고 평범한 binary search 문제이다. 문제 조건에서 들어오는 timestamp 는 오름차순으로 찍힌다고 하는게 큰 길잡이이다. from collections import defaultdict class TimeMap: dic = None def __init__(self): self.dic = defaultdict(list) def set(self, key: str, value: str, timestamp: int) -> None: self.dic[key].append([timestamp, value]) def get(self, key: str, timestamp: int) -> str: lo, hi = 0, len(self.dic) - 1 ans = "" while lo <= hi: mid = (lo + hi) // 2 if self.dic[key][mid][0] > timestamp: hi = mid - 1 else: ans = self.dic[key][mid][1] lo = mid + 1 return ans

접근 가능한 속도 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

접근 기본적인 배경은 이분 탐색이다. 현재 pivot 기준으로 왼쪽을 봐야할지, 오른쪽을 봐야할지 조건을 생각하는 것이 관건이다. 만약 nums[low] <= nums[mid] 라면, 왼쪽 subarray 는 정렬되어있다. target 이 해당 range 를 벗어나면 오른쪽을 본다. 만약 nums[low] > nums[mid] 라면, 오른쪽 subarray 가 정렬되어있다. target 이 오른쪽 subarray 의 range 를 벗어나면 왼쪽을 본다. 사고 binary search 를 필요한 만큼 수정해서 직접 이용할 수 있는지 묻는 문제이다. 직접 sorting algorithm 을 구현하는 것보다는 개인적으로 쉽고 또 자주 직접 customizing 해야한다. 다양한 정렬 문제들을 Comparator 를 이용해서 접근하는 것처럼 binary search 또한 다른 상황에서 직접 필요한 부분을 수정해서 쓸 수 있도록 연습하자. ...