(5) 이진 탐색 알고리즘
이진 탐색 알고리즘이란 정렬된 데이터에서 특정한 데이터를 빠르게 탐색할 수 있는 탐색 알고리즘
순차 탐색과의 비교
- 순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법
- 이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀나가며 데이터를 탐색하는 방법
- 이진 탐색은 시작점, 끝점, 중간점을 이용해 탐색 범위 지정
- 단계마다 탐색 범위를 2로 나누는 것과 동일, 따라서 시간 복잡도 O(logN)
파이썬 이진 탐색 라이브러리
파이썬에 기본으로 내장된 라이브러리 메서드를 통해 쉽게 이진탐색을 구현할 수 있음
-
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
4bisect 라이브러리 활용 예시
bisect 라이브러리를 활용해 값이 특정 범위에 속하는 데이터의 개수를 구할 수 있음
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,3,4,4,8,9]
# 값이 4인 데이터 개수 출력
print(count_by_range(a,4,4))
# 값이 -1에서 3 범위에 있는 데이터 개수 출력
print(count_by_range(a,-1,3))# 실행 결과
2
7파라메트릭 서치(Parametric search)
파라메트릭 서치란 최적화 문제를 결정 문제(Yes or No)로 바꾸어 해결하는 기법
- 예시: 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제
일반적으로 코딩테스트에서 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결할 수 있음
이진 탐색 알고리즘 문제 예시(1)
떡볶이 떡 만들기 문제를 이진 탐색 알고리즘의 예시로 들 수 있음
-
원래의 떡 길이에서 절단기 만큼의 길이를 뺀 값만 손님이 가져갈 수 있음
-
만약 손님이 M만큼의 떡을 얻기 위한다면 절단기에 설정가능한 높이의 최댓값을 구하는 문제
➡️ 현재 이 길이로 자르면 조건을 만족할 수 있는가? 를 확인한 뒤에 조건의 만족 여부에 따라 탐색 범위를 좁혀 해결 가능
➡️ 또한 탐색 범위가 굉장히 크므로 시간초과 여부를 위해 이진탐색을 먼저 떠올려야 함
-
문제에서 가장 큰 떡의 길이의 19이므로 시작점은 0, 끝점은 19, 중간점은 (0+19)/2 인 9로 설정
-
문제에서 중간점을 자르고자하는 떡의 높이(구하고자 하는 최댓값)으로 이해
-
중간점 9에 대한 결과의 조건 충족 여부 확인: 조건 충족 O
- 결과 저장
-
시작점을 10, 중간점을 오른쪽인 14로 옮김. (14 = (10+19)/2): 조건 충족 O
- 결과 저장
-
시작점을 15, 중간점을 오른쪽인 17로 옮김. (17 = (15+19)/2): 조건 충족 x
- 결과 저장하지 않음
-
시작점을 15, 끝점을 16으로 옮김. 따라서 중간점을 15로 설정: 조건 충족 O
- 조건 충족하므로 결과 저장 및 출력
# 문제 정보 입력
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 # 시작점을 중간점 오른쪽으로 이동
# 만약 그 다음 for문이 충족하지 못할 경우 이전의 result값이 출력
print(result)# 결과 출력
15이진 탐색 알고리즘 문제 예시(2)
정렬된 배열에서 특정 수의 개수 구하기 문제를 예시로 들 수 있음
- N개의 원소를 포함하고 있는 수열이 오름차순 배열돼 있을 때, 수열에서 X가 등장하는 횟수 구하는 문제
➡️단, 이 문제는 이진 탐색으로 문제를 풀지 않을 경우 시간 초과 판정이 나므로, 무조건 O(logN)의 시간 복잡도 결과를 내야함
➡️파이썬의 bisect 라이브러리를 활용하여 문제 풀이가 가능함
from bisect import bisect_left, bisect_right
# 문제 정보 입력
n,x = list(map(int, input().split()))
array = list(map(int, input().split()))
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
count = count_by_range(array, x, x)
if count == 0 : # 만약 원소가 존재하지 않는다면
print(-1)
else:
print(count)# 결과 출력
4 