알고리즘(Python)이분탐색, dfs/bfs

이진탐색 강의

def solution(L, x):
    lower = 0
    upper = len(L)-1
    
    while lower <= upper:
        middle = (lower + upper)//2
        if L[middle] == x:
            return middle
        elif L[middle] > x:
            upper = middle-1
        elif L[middle] < x:
            lower = middle+1
    return -1

• 리스트 L 자체를 바꾸는 코드는 시간이 오래걸린다.
  upper, middle, lower의 인덱스만 바꾸면 된다.

• 계속 자르고 자르다 길이가 1인 리스트가 되어 upper와 lower가 같아지면
  upper가 lower보다 작아진다.

입국심사

def solution(n, times):
    lower = 1
    upper = max(times)*n
    while lower <= upper:
        mid = (lower+upper)//2
        
        pnum = 0
        for i in times:
            pnum += mid//i # mid시간 동안 i time 심사대에서 입국할 수 있는 사람수
            # if pnum > n: break
                
        if pnum == n:
            return mid
        
        elif pnum > n:
            answer = mid
            upper = mid-1
        
        elif pnum < n:
            lower = mid+1
    
    return answer

• pnum이 n과 같다면 mid가 최소의 시간이 되는 것이 아닌가??

def solution(n, times):
    lower = 1
    upper = max(times)*n
    # upper = (len(times)+1) * max(times)
    while lower <= upper:
        mid = (lower+upper)//2
        
        pnum = 0
        for i in times:
            pnum += mid//i # mid시간 동안 i time 심사대에서 입국할 수 있는 사람수
            if pnum > n: break
                
        if pnum >= n:
            answer = mid
            upper = mid-1
        
        elif pnum < n:
            lower = mid+1
    
    return answer

• pnum과 n이 같아질 때 바로 리턴하는 거 제거했더니 맞음
• 드는 시간의 최댓값이 왜 (len(times)+1) * max(times) 가 가능한것인가??
• 이런 문제보고 이분 탐색이라고 생각 어떻게 하지...??

참고

단어변환