06 이진 탐색 (문제)
in Coding Test
이것이 코딩 테스트다. with 파이썬 - 06 이진 탐색 문제
⭐ 문제는 나동빈님의 유튜브를 통해 확인해 주세요!!
유튜브에 있는 문제들만 풀이하여 이 블로그에 포스트 했습니다.
문제를 안적은 이유는 나동빈님의 유튜브에서 한 번 보시고 공부 해보시라고 문제는 따로 적지 않았습니다.
책에 있는 문제들은 이 블로그에는 없습니다.
떡볶이 떡 만들기
n= 떡의 개수m= 요청한 떡의 길이array= 각 떡의 개별 높이 배열start= 시작 지점end= 제일 큰 떡의 길이result= 결과totla= 자른 떡의 길이 합mid= 제일 큰 떡의 길이 중간 길이
n, m = map(int, input().split())
array = list(map(int, input().split()))
start = 0
end = max(array)
result = 0
while start <= end:
total = 0
mid = (start + end) // 2
for x in array:
if x > mid:
total += x - mid
if total < m:
end = mid - 1
else:
result = mid
start = mid + 1
print(result)
떡의 길이 시작 지점과 끝 지점을 정해준다. 시작 지점이 끝 지점과 같거나 커질때 까지 계속 반복해준다.
중간 지점을 구해준다.
그리고 자른 떡의 총 길이를 구해준다.
자른 떡의 총 길이가 제일 긴 떡의 길이보다 작으면
end를mid에서 1을 빼준고 다시 반복한다.
3.1 아니면 결과를 저장하고 mid를 1을 더해주고 반복한다.
- 시작 지점이 끝 지점보다 크거나 같을 때까지 반복한다.
책이나 유튜브 영상에서는 더 자세히 나와있으니 한 번 보는 것을 꼭 추천한다.
정렬된 배열에서 특정 수의 개수 구하기
n= 데이터의 개수x= 찾고자 하는 값array= 전체 데이터count= 데이터의 개수 계산right_index= 특정 값의 마지막 위치left_index= 특정 값의 첫 번째 위치
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())
array = list(map(int, input().split()))
count = count_by_range(array, x, x)
if count == 0:
print(-1)
else:
print(count)
파이썬에서 제공해주는 이진 탐색을 사용한 문제이다.
bisect_left,bisect_right
특정 값이 등장하는 첫 번째 위치 bisect_left 와 마지막 위치 bisect_right를 구해서 계산한다.
