[알고리즘] 이분 탐색

이분 탐색은 내부 원소들이 정렬되어 있는 배열에서 특정 원소를 빠르게 찾을 수 있는 탐색 방법이다.

탐색 범위를 절반씩 줄여나간다는 특징이 있는데, 이 때문에 시간복잡도가 O(log n)으로, 순차 탐색보다 효율적이다.

예를 들면, 아래의 배열에서 숫자 3을 탐색하는 과정은 다음과 같다.

이분 탐색(Binary Search) 헷갈리지 않게 구현하기

(구현에 있어 위 글이 매우 도움이 되었다)

이분 탐색의 구현 방법은 다음과 같다.

1. 탐색 범위를 지정하고 하한(lo)와 상한(hi)를 지정한다.

2. while(lo <= hi) 동안 mid = (lo+hi)/2 에 대해 탐색한다.

3. 탐색하는 대상이 mid보다 작은 인덱스에 있다면 hi = mid-1, 반대로 mid보다 큰 인덱스에 있다면 lo = mid + 1

4. 경계에 이를 때까지 2~3을 계속 반복

5. 경계에 이르렀을 때, lo, hi, mid 중 어느 것이 답인지 생각한다. 가장 큰 조건을 찾는다면 lo가 답이 되며, 가장 작은 조건을 찾을 때는 hi가 답이 된다.

---

백준의 '단계별로 풀어보기'에서 이분 탐색 문제를 풀어보았다.

이분 탐색을 응용한 문제들의 풀이를 조금 끄적여 본다.

1654번: 랜선 자르기

[ Silver 2 ]

이 문제처럼 탐색해야 하는 배열이 주어지지 않은 경우가 많다.

이럴 때, 탐색해야 하는 범위를 자연수의 배열로 생각하고 종결조건을 설정해 이분적으로 탐색하면 된다.

랜선 길이를 mid로 두고, mid의 길이로 주어진 랜선들을 잘랐을 때 필요한 랜선 개수보다 많다면 자르는 길이를 계속 증가시키면서 탐색하면 된다. 반대로, 잘랐을 때 랜선 개수가 부족하다면 자르는 길이를 감소시킨다.

2110번: 공유기 설치

[ Gold 4 ]

이 문제 또한 탐색하는 배열이 주어지지 않았다.

mid를 설정하고, (집들 사이의 거리 > mid)를 만족하는 경우의 수가 (공유기의 개수 - 1)보다 많다면 mid를 증가시키며 탐색하고, 반대의 경우 mid를 감소시킨다.

1300번: K번째 수

[ Gold 2 ]

이 문제는 탐색하는 배열이 주어지지 않았을 뿐더러, 탐색 범위도 명확하지 않아서 고민할 필요가 있다.

배열의 원소의 값이 열 번호 * 행 번호라는 것을 사용한다면,

∑mid / 열 번호(행 번호) > k 를 만족하는 mid를 탐색할 수 있을 것이다.

 

 

P.S. 12015번은 풀지 않는 것을 추천한다. DP를 쓰면 이분 탐색으로 풀 수 있지만 시간초과가 많이 난다고 하며, LIS(가장 긴 증가하는 부분 수열) 알고리즘을 사용하는 것이 효과적이다. 솔직히 왜 이분 탐색 단계에 있는지도 이해가 되지 않는다...