[Algorithm] 27강 : 이진 탐색 기초 문제 풀이

 

<문제> 떡볶이 떡 만들기

 

 

 

#문제 해결 아이디어

적절한 높이를 찾을 떄까지 이진 탐색 수행하여 높이 H를 반복 조정

 

 

가장 긴 떡의 끝점을 end 로 잡고 중간 지점을 찾아서 자른다. 이때 떡의 크기를 보고 더 크면 오른쪽으로 작으면 왼쪽으로 이동한다.

 

이 과정을 반복한다..

 

 

# 답안 

# 떡의 개수 N 과 요청한 떡의 길이 M을 입력
n,m = list(map(int,input().split(' ')))
# 각 떡의 개별 높이 정보를 입력
array = list(map(int,input().split()))

start = 0
end = max(array)

result = 0
end = max(array)

restult = 0

while(start <= end):
	totla = 0
    mid = (start+end) // 2
    for x in array:
    # 잘랐을때 떡의 양의 계산
    	if x > mid:
        	totla += x - mid
    #떡의 양이 부족한 경우 덜 자르기
    if total < m:
    	end = mid -1
    #떡의 양이 충분한 경우 더 자르기
    else:
    	result = mid # 최대한 덜 잘랐을 때가 정답이므로 , 여기에 result에 기록
        start = mid + 1

print(result)

 

---

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

 

 

 

# 문제 해결 아이디어

시간 복잡도 O(log N)으로 동작하는 알고리즘을 요구하고 있다.

-일반적인 선형탐색으로는 시간 초과 판정을 받는다.

-하지만 데이터가 정렬되어 있어서 이진탐색이 가능하다,

특정값이 등장하는 첫 번째 위치와 마지막 위치를 찾아 위치 차이를 계산해 문제를 해결 할 수 있다.

 

 

 

# 답안

from bisect import bisect_left , bisect_right


# 값을 찾아 데이터의 개수를 반환하는 함수
def count_by_range(array, left_value, right_value):
	right_index = bisect_right(array, right_value)
    left_index = bisect_left(array, left_value)
    return right_index - left_index
    
n , x = map(int,input().split()) # 데이터의 개수 N, 찾고자하는 값 x
array = list(map(int,inpit().split())) # 전체 데이터 입력받기

count = count_by_range(array, x ,x)

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

 

---

www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC

이 자료는 동빈 나 님의 이코 테 유튜브 영상을 보고 정리한 자료입니다.