[11강] 이분 탐색 알고리즘

---

안녕하세요 Gliver 입니다.

이번 글에서는 이분 탐색 알고리즘에 대해 알아보겠습니다.

 

목차

1. 이분 탐색 알고리즘
2. 파라매트릭 서치 알고리즘
3. 실제 문제에서 이분 탐색 알고리즘

 

 

1. 이분 탐색 알고리즘

이분 탐색 알고리즘은 정렬된 배열에서 특정한 원소를 찾는 알고리즘이다.

정렬된 배열이 아니라면 이분 탐색을 시행할 수 없음.

 

이분 탐색(binary search)은 범위를 반으로 줄여가며 특정 원소를 찾는 알고리즘으로

예시를 통해서 어떻게 동작하는지 살펴보자.

 

 

아래와 같이 정렬된 배열이 있을 때 이분 탐색 알고리즘을 통하여 10을 찾아보자.

 

방법1

[1단계]
left = 0, right = 11
처음에는 배열의 첫 인덱스를 left(0), 끝 인덱스를 right(11)로 지정하고 시작한다.

mid = (left + right) / 2 로 계산하므로 mid는 5이 된다.
인덱스가 mid(5)인 원소 7이 우리가 찾고자 하는 원소 10보다 작으므로 left = mid+1 을 수행한다.


[2단계]
left = 6, right = 11

mid = (left + right) / 2 로 계산하므로 mid는 8이 된다.
인덱스가 mid(8)인 원소 11이 우리가 찾고자 하는 원소 10보다 크므로 right = mid-1 을 수행한다.


[3단계]
left = 6, right = 7

mid = (left + right) / 2 로 계산하므로 mid는 6이 된다.
인덱스가 mid(6)인 원소 9가 찾고자 하는 원소 10보다 작으므로 left = mid+1 을 수행한다.


[4단계]
left = 7, right = 7

mid = (left + right) / 2 로 계산하므로 mid는 7이 된다.
인덱스가 mid(7)인 원소 10이 찾고자 하는 원소 10과 일치하므로 인덱스 7을 반환하고 알고리즘을 종료한다.

즉, 이분 탐색 알고리즘을 통해 정렬된 배열에서 인덱스가 7인 원소가 10임을 알아낸 것이다.

 

 

위 예시(방법1)에서 시행한 방법이 가장 보편적으로 알려진 이분탐색이며 코드로 구현하면 아래와 같다.

 

	#include <bits/stdc++.h>
	using namespace std;
	int binary_search(vector<int> arr, int num) {
	int left = 0;
	int right = arr.size()-1;
	while (left <= right) {
	int mid = (left + right) / 2;
	if (arr[mid] < num) left = mid+1;
	if (arr[mid] > num) right = mid-1;
	if (arr[mid] == num) return mid;
	}
	return -1;
	}
	int main()
	{
	cout << binary_search({1, 3, 3, 4, 5, 7, 9, 10, 11, 13, 13, 16}, 10);
	return 0;
	}

view raw Binary Search1.cpp hosted with ❤ by GitHub

 

	def binary_search(arr, num):
	left = 0
	right = len(arr) - 1
	while left <= right:
	mid = (left + right) // 2
	if arr[mid] < num:
	left = mid + 1
	if arr[mid] > num:
	right = mid - 1
	if arr[mid] == num:
	return mid
	return -1
	print(binary_search([1, 3, 3, 4, 5, 7, 9, 10, 11, 13, 13, 16], 10))

view raw Binary Search1.py hosted with ❤ by GitHub

 

 

 

방법2

[1단계]
cur = -1, step=12
처음에는 현재 위치 cur을 -1, 보폭 step을 배열의 크기(12)로 지정하고 시작한다.

현재 위치 cur(-1)에서 step(12)만큼 이동했을 때 원소는 16이며 10보다 크므로 이동하지 않는다.
10보다 큰 원소가 나왔으므로 step을 절반으로 줄인다.


[2단계]
cur = -1, step = 6

현재 위치 cur(-1)에서 step(6)만큼 이동했을 때 원소는 7이며 10이하이므로 이동한다. (cur = 5)
현재 위치 cur(5)에서 step(6)만큼 이동했을 때 원소는 16이며 10보다 크므로 이동하지 않는다.
10보다 큰 원소가 나왔으므로 step을 절반으로 줄인다.


[3단계]
cur = 5, step = 3

현재 위치 cur(5)에서 step(3)만큼 이동했을 때 원소는 11이며 10보다 크므로 이동하지 않는다.
10보다 큰 원소가 나왔으므로 step을 절반으로 줄인다.


[4단계]
cur = 5, step = 1

현재 위치 cur(5)에서 step(1)만큼 이동했을 때 원소는 9이며 10이하이므로 이동한다. (cur = 6)
현재 위치 cur(6)에서 step(1)만큼 이동했을 때 원소는 10이며 10이하이므로 이동한다. (cur = 7)
현재 위치 cur(7)에서 step(1)만큼 이동했을 때 원소는 11이며 10보다 크므로 이동하지 않는다.
10보다 큰 원소가 나왔으므로 step을 절반으로 줄인다.

step = 0이 됐으므로 현재 인덱스 cur을 반환하고 알고리즘을 종료한다.

참고로, 이 방법은 10이하인 원소라면 계속 이동하므로 10이하인 수 중에서 맨 오른쪽 인덱스를 구하게 된다.

 

 

위 예시(방법2)에서 시행한 방법은 파라매트릭 서치에서 사용하기 좋으며 코드로 구현하면 아래와 같다.

 

	#include <bits/stdc++.h>
	using namespace std;
	int binary_search(vector<int> arr, int num) {
	int cur = -1;
	int step = (int)arr.size() - 1;
	while (step != 0) {
	while (cur+step < int(arr.size()) && arr[cur+step] <= num) {
	cur += step;
	}
	step /= 2;
	}
	return cur;
	}
	int main()
	{
	cout << binary_search({1, 3, 3, 4, 5, 7, 9, 10, 11, 13, 13, 16}, 10);
	return 0;
	}

view raw Binary Search2.cpp hosted with ❤ by GitHub

 

	def binary_search(arr, num):
	cur = -1
	step = len(arr)
	while step != 0:
	while (cur + step < len(arr) and arr[cur + step] <= num):
	cur += step
	step //= 2
	return cur
	print(binary_search([1, 3, 3, 4, 5, 7, 9, 10, 11, 13, 13, 16], 10))

view raw Binary Search2.py hosted with ❤ by GitHub

 

 

 

위에서 살펴본 두 알고리즘(방법1, 방법2) 모두 단계마다 절반씩 크기가 줄어들기 때문에 시간 복잡도는 $O(log \ n)$을 만족한다.

여기서 n은 살펴보는 전체 범위의 크기(보통은 배열의 크기와 동일)를 의미한다.

 

 

2. 파라매트릭 서치 알고리즘

위에서 살펴본 이분 탐색 방법2에 대해서 다시 생각해보자.

결과가 조건(10이하인 수)을 만족하는 원소 중에서 맨 오른쪽 인덱스를 반환하는 알고리즘이었다.

참고로 반환된 인덱스에 +1을 하게 되면 조건을 만족하지 않는 맨 왼쪽 인덱스가 된다.

 

좀 더 자세히 말하자면 위에서 살펴본 배열에 대해서

원소가 조건(10이하인가?)을 만족하면 α, 그렇지 않으면 β로 바꿔 보자.

이렇게 하면 10이하인 가장 오른쪽 인덱스를 찾는 과정은 가장 오른쪽 α를 찾는 문제와 동일해진다.

 

만약, 어떤 문제에서 '어떤 숫자 $x$가 답이 될 수 있나?'에 대한 상황이 위와 같이 나타난다면

우리는 이를 이분탐색을 통해서 답의 최댓값 또는 최솟값을 구할 수 있게 되는 것이다.

그리고 이러한 방식의 이분 탐색을 우리는 파라매트릭 서치(parametric search)라고 부른다.

 

 

파라매트릭 서치가 적용되는 과정을 아래의 문제를 통해서 살펴보자.

[문제] (백준 2805번)
나무의 개수 N과 가져가야하는 나무의 길이 M이 주어지며, 이어서 나무들의 높이가 주어진다.
절단기의 높이를 설정하면 절단기 높이 이상의 나무들이 잘리며, 이때 절단기의 최대 높이를 구하는 것이다.
(N ≤ 1,000,000) (M ≤ 2,000,000,000) (각 나무의 높이 ≤ 1,000,000,000)

[먼저, 이 문제를 푸는 가장 기본적인 방법을 살펴보자. (브루트 포스 알고리즘)]
N이 최대 100만이고 각 나무의 높이는 최대 10억이다.
따라서, 10억 이하의 높이가 답의 후보가 될 수 있으며 이를 하나씩 살펴보며 답을 구할 수 있다.
이렇게 했을 때 후보 1개당 N개의 나무들을 살펴봐야 하므로 시간 복잡도는 $O(10^9 \cdot N)$이 나오게 된다.
하지만, 이는 문제에서 요구한 시간 복잡도를 만족하지 못하므로 다른 풀이를 떠올려야 한다.

[더 효율적으로 살펴보는 방법을 찾아보자. (파라매트릭 서치)]
위의 브루트 포스 알고리즘에서 살펴 봤듯이 답은 0이상 10억 이하의 수라는 것이다.
그리고 우리가 구해야 하는 것은 답의 최대 값(높이) $k$을 구하는 것이다.
10억 이하의 자연수에 대해서 답이 될 수 있으면 α, 그렇지 않으면 β로 나타내면 다음과 같은 형태이다.

이와 같은 형태가 나오는 이유는 절단기의 높이를 낮추면 가져갈 수 있는 양은 더 많아지기 때문이다.

이제 우리는 가장 오른쪽 α의 인덱스를 구하면 되는 것이다.
이는 위에서 살펴봤듯이 이분 탐색(파라매트릭 서치)을 통해서 수행할 수 있다.
살펴 볼 범위의 크기는 최대 10억이고 한 번 살펴볼 때 N개의 나무를 살펴봐야 하므로 시간 복잡도는 $O(N \cdot log_2  10^9)$이다.
참고로, $log_2  10^9$은 약 30이므로 문제에서 요구하는 시간 복잡도를 만족한다.

 

위 문제에 대한 파라매트릭 서치 코드를 구현하면 아래와 같다.

이 문제는 배열을 탐색하는 것이 아닌 수의 범위를 배열처럼 취급하여 탐색한다는 점을 주의하자!

 

	#include <bits/stdc++.h>
	using namespace std;
	using ll = long long;
	ll N, M;
	vector<ll> arr;
	bool is_possible(ll x) {
	ll num = 0;
	for (auto &u : arr) num += max(0LL, u-x);
	return num >= M;
	}
	int main()
	{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> N >> M;
	arr.resize(N);
	for (int i=0; i<N; i++) cin >> arr[i];
	// parametric search
	ll cur = 0;
	ll step = 1e9; // 10억
	while (step != 0) {
	while (cur+step < int(1e9) && is_possible(cur+step)) {
	cur += step;
	}
	step /= 2;
	}
	cout << cur << '\n';
	return 0;
	}

view raw Parametric Search.cpp hosted with ❤ by GitHub

 

	def is_possible(k):
	global N, M, heights
	num = 0
	for h in heights:
	if h > k:
	num += (h - k)
	return (num >= M)
	N, M = map(int, input().split())
	heights = list(map(int, input().split()))
	# parametric search
	cur = -1
	step = int(1e9) + 1
	while step != 0:
	while (cur + step <= int(1e9)) and is_possible(cur + step):
	cur += step
	step //= 2
	print(cur)

view raw Parametric Search.py hosted with ❤ by GitHub

 

 

정리하면, 파라매트릭 서치는 답의 후보에 대해서 탐색하여 답의 최댓값 또는 최솟값을 구하는 알고리즘이다.

단, '답이 가능한가'에 대한 형태가 위에서 살펴봤듯이 어떤 수를 기준으로 명확히 나누어져야 사용할 수 있다.

최솟값(맨 왼쪽 β)을 구하는 것은 맨 오른쪽 α의 인덱스를 구한 후에 +1을 해주면 된다.

 

 

 

3. 실제 문제에서 이분 탐색 알고리즘

실제 문제에서 이분 탐색이 어떻게 쓰이는지 위에서 배운 내용을 토대로 살펴보자.

 

이분 탐색

이분 탐색은 정렬이 된 상태에서 사용할 수 있다.

참고로, 선형 자료구조여야 정렬이 가능하다. (이에 대한 자세한 내용은 여기를 참조)

 

따라서, 정렬이 가능한 상황(또는 정렬이 되어 있는 상태)이라면 이분 탐색을 고려하면 된다.

 

[관련 문제]

백준 : 숫자 카드 (10815번)

백준 : 수 찾기 (1920번)

파라매트릭 서치

파라매트릭 서치는 문제에서 배열이 주어지는 것이 아닌, 상황 자체를 일종의 정렬된 배열처럼 보는 것이다.

즉, 어떠한 답이 가능한가를 기준으로 명확히 (α, β로) 나뉜다면 사용할 수 있다.

 

이러한 상황이 나오려면 최댓값 또는 최솟값을 구하는 경우라는 것을 알 수 있다.

 

따라서, 문제에서 요구하는 것이 최댓값 또는 최솟값을 요구한다면 문제의 상황을 살펴보자.

만약, 답이 가능한가를 기준으로 명확히 (α, β로) 나뉜다면 파라매트릭 서치를 사용하면 된다.

그렇지 않으면, 이는 파라매트릭 서치를 사용할 수 있는 환경이 아니므로 다른 풀이를 떠올려야 한다.

 

[관련 문제]

백준 : 공유기 설치 (2110번)

백준 : k번째 수 (1300번)

 

 

 

 

---

궁금한 점이나 코멘트는 댓글로 남겨주세요!

 

• 알고리즘 공부법 : https://gliver.tistory.com/6
• 알고리즘 목차: https://gliver.tistory.com/7