이분 탐색, 매개변수 탐색 정의
이분탐색(Binary Search) 정의
이분 탐색(Binary Search)은 순차 탐색의 시간복잡도 O(N)에서 O(logN)으로 탐색 시간을 줄여 탐색하는 방법으로, 정렬된 배열 안에서만 사용이 가능하다. 단순한 '탐색'은 코딩테스트에 출제되지 않는다. 이를 활용한 문제가 나온다.
mid == target이면 탐색을 종료해도 상관없다는 게 매개변수 탐색과 다른 특징이다.
매개변수 탐색(Parametric Search) 정의
조건에 맞는 최대/최소값을 찾을 때 파라미터를 주로 사용하며, 이 파라미터는 이분 탐색을 이용해서 left, right, mid(=parameter) 를 계산하여 구하는 문제이다.
파라미터를 변수로 값을 True/False를 리턴하는 어떠한 함수 bool F(parameter) {} 를 생성하여 문제의 조건에 맞는지를 탐색해야 한다.
아래 코드의 2번 유형과 같이, 함수 F의 리턴 값이 True인 지점에서 값을 저장해주어야 한다: 매개변수 탐색은 이분탐색과는 다르게, 배열의 모든 원소들을 탐색해서 최선(최대/최소)의 값을 찾아야 한다는 점이 특징이기 때문이다.
이분탐색, 매개변수 탐색 예시
left, right, mid와 같은 인덱스를 가지고, mid가 target보다 큰지 작은지를 바탕으로 탐색 범위를 이분화하므로 logN의 복잡도를 갖는다. 배열 내에서의 값을 바탕으로 아래와 같은 반복문을 수행한다.
// 1. 기본 형태 - 원하는 값 == TARGET 일 경우 리턴을 left or mid로 하면 된다.
while(left<=right){
... SOME FUNCTION
if(mid < TARGET)
left = mid + 1;
else
right = mid - 1;
}
// 2. 변형 형태(매개변수 탐색)
// -> 원하는 값이 최대, 최소인 경우 TARGET을 명확히 하기 어렵다.
// 이 경우 범위에 맞을 때마다(F(mid)가 True) 리턴 값(mid)를 저장해두어야 한다.
while(left<=right){
... SOME FUNCTION
if(F(mid)){
left = mid + 1;
answer = max or min(answer, mid);
}
else
right = mid - 1;
}
}
문제 풀이 유의 사항
- 문제 유형에 따라서 리턴 값을 left or mid가 아닌, 특정 조건에 맞았을 경우의 mid값을 요구하는 경우가 있으므로 주의해야 한다(이분 탐색이던, 매개변수 탐색이던 상관없이.)
- 매개변수 탐색 문제의 경우 '조건'에 맞는지를 판단하기 위한 Function 설계에 주의해야 한다.
예제 문제
문제 유형
좀 더 살펴봐야겠지만, 몇 문제 풀어본결과(~백준 골드 4까지밖에 안 풀어봄), 대개 매개변수 탐색으로 심화되서 출제되며, 일직선 상에서 특정 위치에 무엇인가 올려져 있고, 이 중에서 어떠한 값의 최대/최소를 탐색해야 한다. 값의 크기가 1억~10억 정도의 크기로 완전 탐색이 어려워 보이므로, 이분탐색을 떠올리면 대개 이 문제 유형에 해당한다.
대표 문제(풀면서 추가 예정)
- https://www.acmicpc.net/problem/1654
https://www.acmicpc.net/problem/2110
https://www.acmicpc.net/problem/1477 - https://school.programmers.co.kr/learn/courses/30/lessons/12979
참고한 링크