Search Algorithm 정리

목차

Binary Search

일반적인 전체탐색(Brute Force)는 $O(N)$ 이라는 시간이 걸리지만, 이진탐색을 이용한다면 로그시간 내에 수행할 수 있다.

탐색 문제를 풀어야할때, $N$이 너무 크다면, 이진탐색을 떠올릴 수 있다. 이진탐색의 기본조건은 탐색하고자하는 자료가 정렬이 되어있어야한다.

general Binary Search

일반적인 이진탐색은 while 문을 이용하여 구할 수 있으며, 이는 이진탐색 구현 에서 확인 할 수 있다.

특히 이진탐색은 경계에서의 조건이 매우 중요하기에 잘 따져보아야한다.

Binary Jumping (Parametric Search)

Binary Jumping 이란 배열을 왼쪼에서 오른쪽으로 뛰어가며 살펴보는 것으로, n/2개씩 원소를 건너뛰다가 각 라운드마다 n/4, n/8 처럼 줄여나가 1이 될때까지 진행한다.

각 라운드에서는 원소를 건너뛰다가, 배열의 범위를 벗어나거나, 건넌 후 목표값이 벗어난다면 건너뛰면 안된다.

[l,r] 에 대한 구현은 다음처럼 할 수 있다.

int k = l -1;
for(int b = hi; b>=1;b>>=1){
    while(k+b < n && !valid(k+b)) k += b;
}

구하고자하는 것이 없다는것은 k가 l-1과 같다라는 뜻이다.

valid(k+b)는 k+b가 올바른 해라면 true를 내보낼텐데, !valid(k+b)라면 올바른 해가 아닐때 즉 false 가 나올때까지 k를 b만큼 더해준다는 것을 의미한다.

즉 000000000000..000111111…111111 이 있을때 마지막 false를 구하려면 최종적으로 k를 , 최소의 true는 k+1, 반대로 1111…111000…00000 이있을때, 마지막 true는 valid(k+b), 그리고 k, 첫번째 false는 k+1가 최종위치가 된다.

x보다 큰 수 중 가장 작은 수

간혹 문제풀이를 하다보면 배열에서 x보다 큰 수중 가장 작은 수를 찾는 문제가 있다.

기본적인 경우에는 upper_bound라는 c++ 함수를 이용하여 $O(lg N)$에 이분탐색으로 구현을 할 수 있다.

하지만 만약 해당 함수가 한번밖에 선택을 할수 없게 된다면, 배열에서 해당 원소를 삭제시켜야한다.

그렇게 되면 $O(lg N * N) 만큼의 time-complexity가 걸리게 된다.

다음 시간을 줄이기 위해 disjoint set을 사용할 수 있을 것이다.

1. upper_bound를 이용하여 x보다 큰 수의 위치를 얻고, find를 이용하여 par[x]를 구함
2. 해당 수를 사용후 x와 x+1을 union 연산

2번을 하는 이유는 x는 인덱스를 나타내기 때문에, 만약 또다시 x보다 큰 수를 찾게 된다면 기존에 사용한 수는 재사용이 불가능 하다. 그러므로 x보다 한칸 더 큰 x+1과 merge 시켜 최종적으로 par[x] 가 x+1를 가리키게 끔 한다.

이를 이용하면 충분히 시간을 줄여나갈 수 있다.