알고리즘 - 이진 탐색 알고리즘 (Binary Search algorithm) 기초 문제 풀이

 

https://youtu.be/94RC-DsGMLo?list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&t=750

<문제: 떡볶이 떡 만들기>

 

<문제: 떡볶이 떡 만들기 문제해결 아이디어>

- 필요한 떡의 크기이상의 값을 얻을 땐 모두 결과를 저장.

# 떡볶이 떡 만들기 
n, m = map(int,input().split()) # n=떡의 개수 / m=떡의 길이

array = list(map(int,input().split()))

start = 0 
end = max(array) #젤 큰 값이 끝값

result = 0

while(start <= end):
    total = 0
    mid = (start+end)//2
    for i in array:
        #잘랐을 때의 떡의 양 계산 (현재의 떡이 자르고자하는 크기보다 클때만 자를 수 있다.)
        if i > mid:
            total += i-mid
            
    # 떡의 양이 부족한 경우 더 많이 짜르기(왼쪽 부분 탐색)
    if total < m:
        end = mid - 1
        
    # 떡의 양이 충분한 경우 덜 자르기(오른쪽 부분 탐색)
    else:
        result = mid #최대한 덜 잘랐을 때가 정답, 여기에 result를 기록
        start = mid + 1
        
print(result)

 

 

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

- 데이터가 정렬되어 있는 경우엔 이진탐색을 해주는 것이 최고다~이말이야~

from bisect import bisect_left, bisect_right

#값이 left_value, right_value인 데이터의 개수를 반환하는 함수
def count_by_range(a,left_value, right_value):
    right_index = bisect_right(a,right_value)
    left_index = bisect_left(a,left_value)
    return right_index - left_index


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

#값이 입력받은 x인 수를 n개 입력받은 리스트 array에서 찾기
count = count_by_range(array,x,x)


#찾고자 하는 수인 x가 array안에 없으면
if count == 0:
    print(-1)
#값이 x인 원소가 존재한다면
else:
    print(count)