[8/23] 이코테 이진탐색

2. 부품 찾기

너무 쉬워서 생략

3. 떡볶이 떡 만들기

202

내 코드

def dduck(array, target, start, end):
    
    while (start <= end):
        mid = (start + end) // 2
        
        ssum = 0
        for i in array:
            if ( i > mid ):
                temp = i - mid
                ssum += temp
        
        # 떡이 m 미만일 경우
        if ( ssum < target ):
            end = mid - 1
        
        # 떡이 m과 같거나 초과
        else:
            result = mid
            start = mid + 1
            
    return result
            
n, m = map(int, input().split())
arr = list(map(int, input().split()))

answer = dduck(arr, m, 0, max(arr))
print(answer)

로직

• 어려웠다.
• 절단기 높이를 0부터 가장 긴 떡의 길이 사이로 잡는 것이 중요한 포인트

<27> 정렬된 배열에서 특정 수의 개수 구하기

367

내 코드

from bisect import bisect_left, bisect_right

n, x = map(int, input().split())
arr = list(map(int, input().split()))

right = bisect_right(arr, x)
left = bisect_left(arr, x)

answer = right - left

if (answer == 0):
    print(-1)
else:
    print(answer)

로직

• 해당 수의 마지막 인덱스에서 첫번째 인덱스를 빼준다.

<28> 고정점 찾기

368

내 코드

n = int(input())
arr = list(map(int, input().split()))

left = 0
right = len(arr)-1

while True:
    
    if (left > right):
        print(-1)
        break
    
    pivot = (left + right)//2
    
    if ( arr[pivot] == pivot ):
        print(arr[pivot])
        break
    
    # 중간값보다 인덱스가 크면
    elif ( arr[pivot] < pivot ):
        left = pivot + 1
        
    # 중간값보다 인덱스가 작으면
    else:
        right = pivot - 1

로직

중간값 == index
끝

중간값 < index
범위 바꾸기

중간값 > index
범위 바꾸기

<29> 공유기 설치

369 (실버1) 문제

내 코드