[코테] 알고리즘 공부 Cheat sheet - II (search)

이진 탐색

이진 탐색하여 찾는 범위를 매 회 절반 씩 날릴 수 있다 

여러번 탐색해야 하는경우 선형탐색보다 유리

다만, 정렬된 상태이어야 함

$ O(N log N) $

 

 

bisect

이진탐색으로 이미 구현된 bisect 를 사용한 예

from bisect import bisect_left, bisect_right

v = [0, 1, 2, 2, 3, 4, 5, 6]

def find_bisect_num(arr, num):
    return bisect_right(arr, num) - bisect_left(arr, num)
# bisect_right 해당 값 초과 index
# bisect_left 해당 값이 최초 나오는 index
# bisect_right - bisect_left = 해당 값 개수

print(find_bisect_num(v, 2))
# 2

 

 

이와 같이 정렬이 되어 있다면 일반적인 선형탐색으로 특정 값이 있는지 ('in' 구문을 사용하거나 루프로 찾기) 확인하는 것이 아니라 

bisect_left 단독 혹은 bisect_left, right 둘 다를 이용하여 리스트에 특정 값이 있는지 확인할 수 있다

 

비슷한 예제

# bisect_left 만 사용

l = bisect_left(arr, val)
if l != len(arr) and arr[l] == val:
	# ...

# bisect_left, bisect_right 사용
l = bisect_left(arr, val)
r = bisect_right(arr, val)
if r - l > 0:
	# ...

 

 

파라메트릭 서치

파라메트릭 서치(Parametric Search)는 이진 탐색(Binary Search) 을 활용하여 최적의 파라미터 값을 찾는 알고리즘 디자인 패턴입니다. 이 알고리즘은 주어진 조건을 만족하는 특정 값을 찾는 문제를 해결하는 데 사용됩니다. 주로 최적화 문제나 결정 문제(Yes/No 문제)를 해결하는 데 유용합니다.

 

먼저 탐색 범위를 초기화합니다. 보통 이진 탐색을 위해 시작과 끝을 설정합니다.
중간 값(파라미터)을 계산하고, 해당 값으로 주어진 조건을 만족하는지 확인합니다.
주어진 조건에 따라서 중간 값이 조절되는 방향을 결정하고 범위를 축소합니다. 즉, 이진 탐색과 유사하게 범위를 절반씩 줄여나갑니다.
최적의 파라미터 값을 찾을 때까지 위 단계를 반복합니다. 종료 조건은 주어진 조건을 만족하는 파라미터를 찾는 것이며, 보통 정확한 값을 찾지 않더라도 충분히 가까운 값으로 수렴하도록 설정됩니다.