이분탐색_ 이분탐색,랜선자르기,뮤직비디오,마구간 정하기

 

 

 

이분탐색 ! 

시간 복잡도 : O(log n) 

 

 

무조건 정렬이 되어있어야한다. 

start와 end 라는 포인터 변수를 만든다 .

mid 라는 중간 지점 변수를 만들어서 (start + end ) // 2 로 설정한다. 

 

 

 

 

 

이분탐색 코드 : 

if __name__=="__main__" :
    n,m = map(int,input().split())
    num = list(map(int,input().split()))
    num.sort()
    
    start,end = 0,n-1
    
    while start <= end :
        mid = (start + end) // 2 
        
        # 내가 찾으려는 숫자인가..?
        if num[mid] == m :
            print(mid+1)
            break
        # 내가 찾으려는 숫자보다 작다
        elif num[mid] < m :
            start = mid + 1 
        # 내가 찾으려는 숫자보다 크다 
        else :
            end = mid -1

 

 

 

랜선자르기 코드 : 

if __name__=="__main__" :
    k,n = map(int,input().split())
    num = list(int(input()) for _ in range(k))
    
    answer = 0
    start,end = 1,max(num)
    
    while start <= end :
        mid = (end+ start) //2 
        ans = 0
        for i in num :
            ans += (i // mid)        
        if ans >=n :
            answer = max(answer,mid)
            start = mid +1 
        else : 
            end = mid -1 
    print(answer )

 

 

뮤직비디오 코드 : 

def Count(capacity) :
    # cd의 개수 
    cnt = 1 
    sum = 0
    for x in music :
        if sum + x > capacity :
            # cd 추가 
            cnt +=1 
            sum = x 
        else : sum += x 
    return cnt 
    
    
if __name__=="__main__" :
    n,m = map(int,input().split())
    music = list(map(int,input().split()))
    longMusic = max(music)
    start,end = 1,sum(music)
    ans = 0
    while start <= end :
        mid = (start+end)//2
        
        # cd의 개수가 m보다 작거나 같다면 
        #  가장 긴 노래보다는 DVD용량이 크거나 같아야한다.
        if mid >= longMusic and  Count(mid) <=m :
            ans = mid
            # 용량을 더 줄인다. 
            end = mid -1 
        else :
            start = mid +1 
    print(ans)

 

 

마구간 정하기 코드 : 

def Count(len) :
    cnt = 1 
    ep = line[0]
    for i in range(1,n) :
        if line[i] -ep >= len :
            cnt +=1 
            ep = line[i]
    return cnt 


if __name__=="__main__" :
    n,c = map(int,input().split())
    line = [int(input()) for _ in range(n)]

    line.sort()
    start, end = 1, line[-1]
    while start <= end :
        mid = (start + end) //2 
        if Count(mid) >= c :
            res = mid 
            start = mid +1 
        else :
            end = mid -1 
    print(res)