이코테 - 이진탐색 2문제

부품찾기

• 사이트/난이도: 이코테 / 1.5
• 코드

n = int(input())
items = list(map(int, input().split()))
m = int(input())
requests =list(map(int, input().split()))

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if array[mid] == target:
            return True
        elif array[mid] > target:
            end = mid-1
        else:
            start = mid + 1
    return False

items.sort()

for request in requests:
    if binary_search(items, request, 0, len(items)-1):
        print("yes", end=' ')
    else:
        print("no", end=' ')

• 느낀점
  이진탐색은 코테에도 자주나오니 구현하는 방법 알아놓자!
  기본적인 이진탐색 문제. 이진탐색을 구현할수있다면 풀수 있음

떡볶이 떡 만들기

• 사이트/난이도: 이코테 / 2
• 코드

n, m = map(int, input().split())
heights = list(map(int, input().split()))

start = 0
end = max(heights)
result = 0

while start <= end:
    total = 0
    mid = (start + end) // 2
    for h in heights:
        if h > mid:
            total += h - mid

    if total < m:
        end = mid - 1
    else:
        start = mid + 1
        result = mid

print(mid)

• 느낀점
  이진탐색이라고 생각하기 좀 힘든 문제였음 ⇒ 하지만 높이 제한이 10억이나 되므로 이렇게 큰 수를 보면 이진탐색을 먼저 떠올리자! (이진탐색 시간복잡도: logN)
  무조건 M 만큼의 떡 길이는 보장하므로 total이 m 이상일때만 result에 결과 저장하기