이진 탐색 알고리즘이란?
이진 검색 알고리즘(binary search algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다. - 위키백과
알고리즘의 작동원리 및 구현 방법은 다른 블로그에서 더 잘 설명해줄거니까 생략한다.
def binarySearch(lst,value):
low = 0
high = len(lst)-1
while low < high:
c = int((low+high)/2)
if lst[c] < value:
low = c + 1
elif lst[c] == value:
return c
else:
high = c -1
return False
백준 문제를 풀던 중 시간초과가 발생했을 때 첫번째로 확인할 부분은 코드에 시간복잡도를 잡아먹는 부분이 있는가를 찾아봤는데
주로 나왔던 실수는
1. 반복문 안에서 배열을 초기화했을 때 배열을 매번 새로 만들면서 시간초과
2. 배열을 순차탐색하는 코드의 존재였다.
2번 같은 문제를 해결하는데 가장 유용한 해결책으로 이진 탐색을 자주 사용했다.
이진탐색의 응용인 upper_bound, lower_bound를 사용하면 문제가 효과적으로 풀리는 경우도 많이 존재했다.
def lower_bound(lst,value): # value 보다 크거나 같은 숫자가 처음으로 나타나는 위치 반환
low = 0
high = len(lst)
while low < high:
c = int((low+high)/2)
if lst[c] < value:
low = c + 1
else:
high = c
return low
def upper_bound(lst,value): # value 보다 큰 숫자가 처음으로 나타나는 위치 반환
low = 0
high = len(lst)
while low < high:
c = int((low+high)/2)
if lst[c] <= value:
low = c + 1
else:
high = c
return low
upper_bound, lower_bound 함수는 배열 안에서 특정 수의 위치를 찾아야하는 상황에서 사용되는데
그냥 이진탐색과 다르게 배열 안에 같은 숫자가 여러개 존재하거나 찾는 숫자가 배열에 존재하지 않을 수도 있을때
즉 여러가지 조건이 붙은 상황에서 탐색할때 굉장히 효과적으로 사용된다.
또 하나의 배열안에 특정한 숫자가 몇개나 있는지 알아야 할 때
upper_bound() - lower_bound() 를 이용하면 빠르게 알아낼 수 있다.
1. 이분탐색
2. 중간에서 만나기, 투포인터
3. GCD, 유클리드 호제법
4. 세그먼트 트리
5. CCW
6. 우선순위큐
7. 유니온파인드, 최소 스패닝 트리, 위상정렬
8. LIS
'백준 플레를 향해서' 카테고리의 다른 글
플레찍었으니 정리해보는 알고리즘 노트 3- GCD, 유클리드 호제법,오일러 피 함수 (0) | 2023.02.06 |
---|---|
플레찍었으니 정리해보는 알고리즘 노트 2 - 중간에서 만나기, 투 포인터 (0) | 2023.02.06 |
백준 플레를 향해서 - 12월 넷,다섯째주(12.19~12.31) (1) | 2023.01.01 |
백준 플레를 향해서 - 12월 셋째주(12.12~12.18) (0) | 2022.12.18 |
백준 플레를 향해서 - 12월 둘째주(12.5~12.11) (2) | 2022.12.11 |