코딩테스트 공부를 하다보니 자주 나오는 두 개념을 복습하고자 정리하려고 한다.
보통 완전탐색 (이중for문)을 이용한다면 시간초과가 종종 나오는 경우가 있다.
이때 유용하게 쓸 수 있는것이 바로 위 두가지다.
| 투포인터 | 이분탐색 | |
|---|---|---|
| 시간복잡도 | O(N) | O(log N) |
| 정렬 유무 | 문제 요구 사항에 따라 다름 ! | 필수 ! |
| 방법 | 첫번째 인덱스에 start,end를 시작으로 한 칸씩 이동하면서 값 찾기 |
시작(left), 끝(right)의 가운데(mid)를 시작으로 mid > 찾으려는 값 ? right = mid-1 : left = mid+1 |
투포인터는 주로 특정한 합을 가지는 부분 연속 수열 찾기와 같은 문제에 사용된다.
이분탐색은 주로 브루트포스와 같은 완전탐색에서 시간효율성을 중요시 할 때 사용된다.
