순차탐색이란?
리스트에서 특정 데이터를 찾기 위해 앞에서부터 순차적으로 데이터를 확인하는 탐색 방법
이진탐색이란?
정렬된 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 하나씩 확인하는 방법
- 시작점, 중간점, 끝점을 이용하여 탐색 범위를 설정
- 시간복잡도 log(2)N
파이썬 라이브러리 bisect
from bisect import bisect_left, bisect_right
a = [1, 2, 3, 4, 4, 6, 7, 8]
x = 4
bl = bisect_left(a, x) # 정렬을 유지하며 x를 삽입할 가장 왼쪽의 인덱스를 반환
br = bisect_right(a, x) # 정렬을 유지하며 x를 삽입할 가장 오른쪽의 인덱스를 반환
print(bl)
print(br)
# 값이 특정 범위에 속하는 데이터 개수 구하기
def counter(arr, left_value, right_value):
arr = sorted(arr)
return bisect_right(arr, right_value) - bisect_left(arr, left_value)
print(counter(a, 3, 5))
파라메트릭 서치란?
- 최적화 문제를 결정 문제(예 혹은 아니오)로 바꾸어 해결하는 기법
- 일반적으로 코딩테스트에서 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결 가능
참고
https://www.youtube.com/watch?v=94RC-DsGMLo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=5
'자료구조 & 알고리즘(Data Structure & Algorithm) > 알고리즘(Python)' 카테고리의 다른 글
동적계획법(Dynamic Programming) 문제풀이 (0) | 2022.02.23 |
---|---|
동적계획법(Dynamic Programming) (0) | 2022.02.23 |
깊이우선탐색(DFS)/너비우선탐색(BFS) (0) | 2022.02.14 |
스택(Stack), 큐(Queue), 재귀(Recursion) (0) | 2022.02.14 |
구현(Implementation) (0) | 2021.08.03 |