반응형
이진탐색 : 절반씩 탐색범위를 줄여가는 것
절반씩 떨쳐내려면 정렬이 되어있어야 한다
선형탐색(완전탐색)이 O(N)인데 그럼 이진탐색보다 선형탐색이 더 유리한거 아니냐?
1번만 찾을 경우에는 선형탐색이 유리하고 (N x N => N^2)
여러번 찾을 경우에는 이진탐색이 유리하다 (NlogN[정렬] + NlogN[이진탐색xN번 반복] = NlogN)
파이썬에서의 이진탐색 라이브러리
left : 3보다 같거나 큰 숫자를 발견하면 해당 숫자 인덱스를 반환 ( >= 3이상)
right : 3보다 큰 숫자를 발견하면 해당 숫자 인덱스를 반환 ( > 3초과)
파라메트릭 서치는 이진탐색과 똑같은데 다만 경계선을 찾는다는 느낌이라고 보면 됨
ppt 출처 및 강의
https://www.udemy.com/course/comgong_codingtest/
반응형
'알고리즘(algorithm)' 카테고리의 다른 글
| 동적 계획법, DP, 피보나치 수열, 이항계수 (컴공선배 강의) (0) | 2023.08.26 |
|---|---|
| DFS, BFS, 백트래킹의 개념 (유데미 강의, 컴공선배) (0) | 2023.08.22 |
| 트리, 인접행렬, 인접리스트 (그래프를 코드로 그리는법 feat.컴공선배) (0) | 2023.08.22 |
| 그래프의 개념 (컴공선배) (0) | 2023.08.22 |
| 탐욕법 Greedy Algorithm (feat.컴공선배) (0) | 2023.08.21 |