이진 탐색이란?
순차 탐색
리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 하나씩 확인하는 방법
이진 탐색
정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
이진 탐색의 시간 복잡도
단계마다 탐색 범위를 2로 나누는 것과 동일하므로 log2(N)이다.
즉, 시간 복잡도 O(logN)을 보장한다.
이진 탐색의 구현
# 이진 탐색 구현 (재귀 함수)
def binary_search(array, target, start, end):
# start가 end보다 크면 탐색 실패
if start > end:
return None
# 중간 위치 계산
mid = (start + end) // 2
# 중간 값과 타겟이 같으면 종료
if array[mid] == target:
return mid
# 중간 값이 타겟보다 크면
elif array[mid] > target:
# end 값을 중간보다 작게 설정
return binary_search(array, target, start, mid - 1)
# 중간 값이 타겟보다 작으면
else:
# start 값을 중간보다 크게 설정
return binary_search(array, target, mid + 1, end)
# 배열 입력
array = list(map(int, input().split()))
# 타겟 입력
target = int(input())
result = binary_search(array, target, 0, len(array))
if result == None:
print(f"{target} 원소는 존재하지 않습니다.")
else:
print(result + 1)1 3 5 7 9 11 13 15 17 19
7
4
1 3 5 7 9 11 13 15 17 19
8
8 원소는 존재하지 않습니다.
이진 탐색 라이브러리
bisect_left(a, x) : 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환
bisect_right(a, x) : 배열 a에 x를 삽입할 가장 오른쪽 인덱스를 반환
from bisect import bisect_left, bisect_right
a = [1, 2, 4, 4, 8]
x = 4
print(bisect_left(a, x))
print(bisect_right(a, x))2
4
이진 탐색의 활용
데이터 개수 구하기
from bisect import bisect_left, bisect_right
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
a = [1, 2, 3, 3, 3, 3, 4, 4, 8, 9]
# 4의 값을 가지는 데이터 개수는?
print(count_by_range(a, 4, 4))
# -1 ~ 3사이의 데이터 개수는?
print(count_by_range(a, -1, 3))2
6
파라메트릭 서치
최적화 문제를 결정 문제로 바꾸어 해결하는 기법이다.
ex) 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제
활용 문제
1. 떡볶이 떡 만들기
절단기에 높이(H)를 지정하면 줄지어진 떡을 한번에 절단한다.
예를 들어, 19, 14, 10, 17cm의 떡이 나란히 있고 H를 15cm로 지정하면
자른 뒤의 떡의 길이는 15, 14, 10 , 15cm이고 잘린 떡의 길이는 4, 0, 0, 2cm이다.
이 경우, 손님은 4 + 0 + 0 + 2 = 6cm의 길이를 가져가게 된다.
손님의 요청 길이가 M일 때, 적어도 M만큼의 떡을 얻기 위해서 설정할 수 있는 절단기의 최대 설정 높이를 구하라.
(조건 : 1 <= N <= 1,000,000 / 1 <= M <= 2,000,000,000 / 2초 / 높이 <= 10억)
풀이)
절단 높이를 찾기 위해서는 가장 긴 떡의 길이를 리스트로 보고 이진 탐색을 통해서 적절한 값을 찾으면 된다.
절단 높이를 찾으면서 떡의 양을 계산해야하므로 총 연산은 log2(N) X log2(H)로 시간은 충분하다.
나의 풀이
# 이진 탐색 구현
def binary_search(array, target, start, end):
# start가 end보다 크면 start 반환
if start > end:
return start
# 중간 위치 계산
mid = (start + end) // 2
# 중간 값과 타겟이 같으면 종료
if array[mid] == target:
return mid
# 중간 값이 타겟보다 크면
elif array[mid] > target:
# end 값을 중간보다 작게 설정
return binary_search(array, target, start, mid - 1)
# 중간 값이 타겟보다 작으면
else:
# start 값을 중간보다 크게 설정
return binary_search(array, target, mid + 1, end)
n, m = map(int, input().split())
array = list(map(int, input().split()))
# 이진 탐색을 위한 정렬
array.sort()
end = array[-1] # 리스트의 최댓값
start = 0
sum = 0
cut_list = [] # 절단 높이 후보 리스트
while True:
# 종료 조건
if start > end:
break
# 절단 높이 설정
cut = (start + end) // 2
# 절단 높이보다 높은 떡의 위치 (절단되어야 할 가장 작은 떡의 위치)
index = binary_search(array, cut, 0, n-1)
# 절단된 떡들의 양 계산
for i in range(index, len(array)):
sum += (array[i] - cut)
# 떡의 양이 충분할 경우
if sum > m:
# 절단 높이 후보에 등록
cut_list.append(cut)
# 떡의 양을 줄이기 위해서 start 증가 => cut 증가 => 절단된 떡 감소
start = cut + 1
sum = 0
# 떡의 양이 불충분한 경우
elif sum < m:
# 떡의 양을 늘리기 위해서 end 감소 => cut 감소 => 절단된 떡 증가
end = cut - 1
sum = 0
# 정확히 맞춘 경우 => 이 경우가 정답이므로 종료
else:
cut_list.append(cut)
break
# 정답 출력
print(max(cut_list))
나는 위와 같이 이진 탐색을 통해서 절단 높이보다 큰 가장 작은 떡을 찾기 위해서 이진 탐색을 사용하였지만 N X logH도 충분히 4000만 이하의 연산이므로 아래와 같이 간단하게 구현해도 된다!
모범 답안
# 떡의 개수(N)와 요청한 떡의 길이(M)을 입력
n, m = list(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 # 최대한 덜 잘랐을 때가 정답이므로, 여기에서 result에 기록
start = mid + 1
# 정답 출력
print(result)4 6
19 15 10 17
15
2. 정렬된 배열에서 특정 수의 개수 구하기
N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있을 때,
이 수열에서 x가 등장하는 횟수를 계산하라.
만약 x인 값이 없다면 -1을 출력하라.
(조건 : 1 <= N <= 1,000,000,00 / -10^9 <= x, 원소 <= 10^9 / 1초)
풀이)
이 경우 N이 1억으로 선형 탐색으로는 시간 초과가 발생한다.
수열이 정렬되어 있고 log2(N)으로 시간이 충분하므로 이진 탐색을 이용한다.
from bisect import bisect_left, bisect_right
n, x = map(int, input().split())
array = list(map(int, input().split()))
# x의 가장 작은 인덱스
left_index = bisect_left(array, x)
# x의 가장 큰 인덱스
right_index = bisect_right(array, x)
# 가장 큰 인덱스에서 가장 작은 인덱스를 뺀다. => 데이터의 개수
count = right_index - left_index
# x인 원소가 존재하지 않는 경우
if count == 0:
print(-1)
else:
print(count)7 2
1 1 2 2 2 2 3
4
참고 자료
이코테 2021 강의 5편
이것이 코딩 테스트다 교재
