1. 배경
ps 문제를 풀면서 해결 알고리즘을 떠올리지 못하는 유형이 공통적인 것을 깨달았는데 바로 이분 탐색 문제였다. 대체로 고난이도 레벨(4 이상)에 배정되어 있으면서 구현 후 효율성 검사에 번번이 실패하는 것으로 보아 한번 정확하게 짚고 넘어가야겠다는 생각을 했다.
사실 이분탐색 알고리즘 자체를 이해하지 못하는 경우는 거의 없을 것이다. 하지만 실전 문제에서 이걸 이분 탐색으로 풀어야 되었다니..!!! 하면서 온갖 삽질을 했던 기억이 있기 때문에 문제와 함께 실전적으로 파악하고자 한다.
2. 이분 탐색이란?
이분 탐색이란 검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘이다.
어떻게? 찾으려는 데이터 값을 정렬된 데이터에서 중간점의 위치와 반복 비교하여 위치를 찾는다.
시간 복잡도 : O(logN)
예시를 들어 설명하자면 업다운이라는 게임을 떠올려보면 된다. 출제자가 생각한 숫자를 맞추는 업다운 게임은 추측한 숫자를 말하면 그 숫자보다 큰지 작은지 힌트를 줘야 한다. 이때 가장 효율적으로 업다운 게임을 하는 방법은 전체 범위에서 가운데 값을 말해나가면서 업 혹은 다운으로 범위를 절반씩 배제해나가면서 푸는 것이다.
3. 이분 탐색 구현하기
def binary_search(array, target, start, end):
if start > end:
return None
mid = (start + end) // 2
# 해당 값이면 바로 반환
if array[mid] == target:
return mid
# 원하는 값이 중간점의 값보다 작은 경우 왼쪽 부분(절반의 왼쪽 부분) 확인
elif array[mid] > target:
return binary_search(array, target, start, mid - 1)
# 원하는 값이 중간점의 값보다 큰 경우 오른쪽 부분(절반의 오른쪽 부분) 확인
else:
return binary_search(array, target, mid + 1, end)
기본 코드는 위와 같다. 정렬된 리스트에서 이분 탐색을 구현하는 경우 어렵지 않게 구현할 수 있을 것이다.
실제 문제에서는 위 이분탐색을 응용한 파라메트릭 서치(parametric search)라는 알고리즘을 사용해 푸는 경우가 다수 출제된다. 파라메트릭 서치란
최적화문제를 결정 문제로 바꾸어 푸는 것이다.
최적화 문제를 결정 문제로 바꾼다는 것은 어떤 것일까?
나이순으로 정렬된 사람들의 리스트가 주어졌다고 생각해보자. 그 중 오토바이 면허를 취득할 수 있는 가장 나이가 어린 사람을 찾으라는 문제가 주어졌다면?
이 문제를 결정 문제로 바꾸는 방법은 "오토바이 면허를 취득할 수 있는가?" 이다.
주어진 리스트가 정렬되어 있으므로 해당 질문을 이분 탐색을 이용하여 계속 던지면 된다.
그렇다면 위의 예시 코드와 다른 점은 무엇일까? 위의 리스트에서는 구분되는 특정 값을 찾는 것이므로 해당 값을 만족하면 바로 탐색을 종료할 수 있다. 하지만 이번엔 "오토바이 면허를 취득할 수 있는가?"에서 예 라고 답하였어도 그 사람이 가장 나이가 어린 사람이라는 보장이 없다.
출처 : https://www.crocus.co.kr/1000
위와 같은 상황이 있다고 해보자. 5번째까지는 이미 오토바이 면허를 취득할 수 없다는 것이 확인된 상황이다. (5를 이미 확인)
이때 7번째 사람이 "오토바이 면허를 취득할 수 있는가?"에서 '예' 라고 답변한다면 탐색이 종료되는 것이 아니라 8, 9를 배제한 채 6이 오토바이 면허를 탈 수 있는 사람인지 검증해야한다. 그리고 6이 면허를 취득할 수 있다면 그 사람이 제일 어린 사람이 되고 아니라면 7이 제일 어린 사람이 된다.
세부 구현은 어떻게 해야할지 알아보자.
4. 문제 풀이
4.1 공유기 설치
https://www.acmicpc.net/problem/2110
2110번: 공유기 설치
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가
www.acmicpc.net
요약하자면 정해진 개수의 공유기를 최대한 멀리 설치해야 하는 문제이다. 이분 탐색의 개념만 접했다면 이 문제를 보고 접근 방법을 떠올리기 쉽지 않을 것이다. 하지만 이 문제는 대표적인 이분 탐색 문제이다.
기억해야할 것은 이분 탐색의 개념뿐만 아니라 파라메트릭 서치의 아이디어까지 가지고 가야 한다는 점이다.
우리가 찾아야 하는 것은 공유기 간의 "최대로 가질 수 있는 최소 거리"이다.
이 최소 거리에 따라 설치되는 공유기 대수가 바뀌게 되는데, 너무 크다면 설치 가능한 공유기의 수가 N개의 공유기보다 적어질 것이고 N보다 크거나 같다면 최소 거리가 너무 작거나 정답이라는 뜻이다.
즉 위에서 살펴본 오토바이 면허 문제에서의 결정 문제와 동일한 구조임을 알 수 있다.
세부 구현은 어렵지 않으므로 생략하겠다.
4.2 징검다리 문제
유사한 유형의 문제이다.
위에서는 집의 좌표가 주어지고 공유기 설치 대수가 주어졌다면 이 문제에서는 바위의 좌표가 주어지고 제거해야할 바위의 개수가 주어진다. 동일하게 파라메트릭 서치로 접근해보면
바위 간의 최소, 최대 거리를 지정한 후 그 가운데 값부터 바위가 얼마나 제거되는지 검증한다.
그 개수가 n보다 크다면 제거해야할 바위를 감소시켜야 한다. (너무 바위를 많이 제거해서 불가능한 케이스이다.)
그 개수가 n보다 작거나 같다면 정답이거나 바위를 더 줄여야 하는 경우이다.
4.3 입국 심사
전의 두 문제와 유형이 달라보이고, heapq로 접근하기 쉬운 문제이다. 하지만 heaq로 푼다면 효율성 검사를 통과할 수 없다.
파라메트릭 서치로 접근해보면 답이 보이는데 우리가 구해야할 것이 "최소 소요 시간"이라면 그 소요 시간의 min과 max를 잡고 중간값으로 계속 탐색해나가면 답을 구할 수 있을 것이다.
더 자세히 설명하자면
구한 mid으로 심사할 수 있는 사람의 수를 구하고
사람의 수가 주어진 n보다 크다면 : 너무 많은 시간이 할애된 것이므로 mid-1로 줄여준다.
사람의 수가 n보다 작다면 : 너무 적은 시간이 할애된 것이므로 mid+1로 높여주면 된다.
5. 구현 잘하기
구현이 어려운 편은 아니지만 파라메트릭 서치의 경우 경계값에 있어서 헷갈리는 경우가 많아 추가 정리하고자 한다.
우선 필요한 조건을 만족해야 하는데
1. 원소가 정렬되어 있으며
2. 원소의 Random Access가 가능해야 한다.
또한 경계값에 대해서는
1. [lo, hi]가 Check(lo) != Check(hi)가 되도록 구간을 설정
2. while (lo + 1 < hi)동안 mid = (lo + hi) / 2에서 Check(mid) = Check(lo)라면 lo = mid, 아니라면 hi = mid
3. 구한 경계에서 답이 lo인지 hi인지 생각해보고 출력
출처 : https://www.acmicpc.net/blog/view/109
그리고 주로 실수가 발생하는 경우는
- lo, hi는 항상 정답의 범위를 나타낼 수 있도록 해야합니다. 예를 들어 lo를 출력해야 하는 문제의 답이 최대 n일 때 hi = n으로 선언하거나, hi를 출력해야 하는 문제의 답이 최소 0일 때 lo = 0으로 선언하면 안됩니다. (hi = n + 1, lo = -1로 선언해야 합니다)
- 오버플로우에 주의해야 합니다. 이분 탐색을 사용하는 문제는 대부분 수의 범위가 크기 때문에 오버플로우가 발생할 수 있습니다.
- 결정 문제의 정의에 맞게 Check함수를 잘 구현해야 합니다. 예를 들어 lower_bound는 v[i] >= k인 i의 최솟값을 구하는 함수이고, upper_bound는 v[i] > k인 i의 최솟값을 구하는 함수인데, Check 함수의 부등호를 조금만 틀려도 전혀 엉뚱한 값이 튀어나올 수 있습니다.
출처 : https://www.acmicpc.net/blog/view/109
가 있다.
잘 정리해보면 어렵지 않게 구현해낼 수 있을 것이다!!