Searching Algorithm
순열 내에서 특정한 값 x를 찾는 형태의 문제가 있을 때 어떻게 해결할 수 있을까?
Linear Search
가장 Naive한 방법으로는 모든 원소를 하나씩 살펴보는 것이다.
시간 복잡도는 O(N)이다.
Binary Search
Linear Search보다 조금 더 빠르게 푸는 방법이다.
1. 배열을 정렬 한다.
2. mid index를 살펴본다.
2-a. 목표를 찾으면 끝낸다
2-b. 목표 값을 찾지 못했다면, mid를 기준으로 왼쪽 또는 오른쪽 중 존재할 수 있는 파트만 조사한다.
매 단계에서 절반을 버리므로, 시간 복잡도는 O(logN)이다.
Two pointer
two sum, three sum, four sum 등에 사용할 수 있다.
예를 들어, 임의의 target이 순열 내의 두 개의 원소의 합으로 만들어질 수 있는지는 어떻게 확인할 수 있을까?
Naive
nC2 의 경우를 모두 살펴보아 확인할 수 있다.
이 경우 시간 복잡도는 O(N^2)이다.
Two pointer
- 배열을 정렬한다.
- l, r을 정의한다.(양 끝에 or 한 쪽으로 몰기. 상황에 따라. 각 요소는 한쪽 방향으로만 이동하면 됨)
- loop마다, l을 오른쪽으로 이동하거나 r을 왼쪽으로 이동하여 상황에 N가지를 살펴본다.
시간 복잡도는 O(N)이다.
cf) three sum의 경우, a, b, c 세가지 index를 사용하면 된다. 시간 복잡도는 O(N^2)이다.
ex) three sum
Binary Search vs Two pointer
ex1) 부분합
