코딩테스트에 자주 나오는 개념인데, 갑자기 둘 간의 차이가 뭐지 하는 의문이 들어서 정리하게 됐다.
완전탐색 시 시간초과가 나는 경우, 이분탐색이나 투포인터 알고리즘을 시도해보자.
*이분탐색 vs 투포인터 알고리즘
이분탐색(이진탐색): mid를 활용해 매 연산마다 탐색하는 범위를 절반으로 좁혀 나감
투포인터: left, right 두 개의 포인터를 한 칸씩 이동하면서 알맞은 값을 찾음
| 이분탐색(이진탐색, Binary Search) | 투 포인터(Two Pointer) | |
| 시간복잡도 | O(log N) | O(N) |
| 가정 | 데이터가 정렬되어 있어야 함 | X |
| 방식 | mid를 활용해서 매 연산마다 탐색하는 범위를 절반으로 좁혀 나감 | 양끝단에서 한칸씩 이동하면서 알맞는 값을 찾음 |
-참고문헌
'Computer Science > Datastructure & Algorithm' 카테고리의 다른 글
| adjacency matrix로 구현된 graph를 DFS할 때 time complexity (0) | 2021.02.14 |
|---|---|
| Q. 문자열을 뒤집는 모든 방법 (0) | 2021.02.01 |
| 최단경로 알고리즘 (1) - 다익스트라 알고리즘 (0) | 2021.01.16 |
