[알고리즘] 백준 10816번: 숫자 카드 2 (C++), 이분 탐색(binary search) 개념, (upper_bound, lower_bound)

이 문제를 보았을 때, 너무 쉬운 문제인데 CLASS 2에 왜 있을까라는 생각을 했다.

어떤 수 N이 있다고 가정하자.

'N이 카드 패에 있는지 없는지는 그냥 for문 돌려서 확인하면 끝나는 거 아닐까?'라고 생각할 수 있었다.

하지만, 문제에서의 N과 M의 주어진 범위를 보고, 시간제한을 보면 떠올랐던 생각으로 풀었을 때 '시간 초과'라는 오류를 초래할 수 있다.

 

왜냐하면 N의 범위가 1~500,000 M의 범위가 1~500,000이면 for문을 돌렸을 때 시간 복잡도가 O(N*M) 일 것이고, 최댓값이 250,000,000,000 즉, 2500억을 넘어가기 때문이다. 시간제한은 1초로 약 1억번 안에 끝내라는 암묵적인 조건을 주기 때문에 for문으로는 처리할 수가 없었다.

 

---

해결법

어떠한 배열 안에 특정한 값이 있는지 없는지의 여부를 빠르게 판별하기 위해서는 '이분탐색(Binary Search)'를 사용하면 된다.

이분탐색과 항상 같이 따라오는 것이 정렬(sort)인데 이는 원리를 설명하면서 말하겠다.

 

이분 탐색의 예로 우리 생활 속의 대화에서도 쉽게 찾아볼 수 있었다.

"나이가 어떻게 되세요?"
"20 업이요"
"23?"
"25 업이요"

이런 식의 대화가 이분 탐색의 이론을 전부 설명하지는 못 하지만 전체적인 느낌에서 많이 비슷함을 느꼈다.

---

원리

[기존의 방법]

 

예를 들어 1~10까지 숫자가 있다고 가정해보자.

이 중에 7이라는 숫자를 찾고 싶다.

(사람이 아닌 코드를 짤 때의 관점에서 생각해보자.)

 

원래는 1부터 '이게 7인가? 아니네' 그다음 2로 넘어가면서 '이게 7인가? 아니네'를 7이 나올 때까지 반복하며 비교한다.

 

[예시 코드]

//num 배열 안에는 1~10까지의 숫자가 들어있다.
//들어있다면 return 1, 없다면 return 0;
bool find7(vector<int> num, int n) {
	for (int i = 0; i < num.size(); i++) {
		if (num[i] == 7) {
			return 1;
		}
	}
	return 0;
}

---

[이분탐색]

 

하지만, 이는 효율적이지 못 하다. (시간 복잡도 O(N)을 초래함.)

1~100,000,000까지의 숫자가 주어진다고 가정하면 1부터 끝까지 다 반복했다가 1초를 넘기는 일이 발생할 것이기 때문이다.

 

이분 탐색은 이러한 방법을 사용하지 않는다.

위의 원리에서 사용된 것처럼 1~10까지 숫자가 있다고 가정해보자.

마찬가지로 7을 찾고 싶다.

 

위의 대화 예에서 처럼 중간값(mid)을 정한다. 중간값을 기준으로 7이 중간값 미만인가 초과인가 혹은 중간값인가를 따진다.

중간값이 5이므로 5~10의 배열에서 다시 중간값 7로 나누어 이것이 미만인가 초과인가 혹은 중간값인가를 따져서 7을 찾아낸다.

중간값(mid)를 기준으로 두 개로 나누어서 탐색하기 때문에 이를 이분 탐색(Binary Search)이라고 한다.

 

[예시 코드]

//num 배열 안에는 1~10까지의 숫자가 들어있다.
//들어있다면 return 1, 없다면 return 0;
bool find7_binarySearch(vector<int> num, int n, int start, int end) {
	while (start <= end) {
		int mid = (end + start) / 2;

		if (num[mid] == n) {
			return 1;
		}
		else if (num[mid] < n) {
			start = mid + 1;
		}
		else if (num[mid] > n) {
			end = mid;
		}
	}

	return 0;
}

코드는 다소 반복해가면서 하나하나 비교해가는 것보다는 복잡해 보이지만 엄청 큰 값(예를 들어 1000 이상) 정도 되면 이분 탐색이 훨씬 수월하다.

 

[예시 코드를 쓰기 위해 사용한 코드 파일]

#include <iostream>
#include <vector>
using namespace std;

bool find7_binarySearch(vector<int> num, int n, int start, int end) {
	while (start <= end) {
		int mid = (end + start) / 2;

		if (num[mid] == n) {
			return 1;
		}
		else if (num[mid] < n) {
			start = mid + 1;
		}
		else if (num[mid] > n) {
			end = mid;
		}
	}

	return 0;
}

bool find7(vector<int> num, int n) {
	for (int i = 0; i < num.size(); i++) {
		if (num[i] == 7) {
			return 1;
		}
	}
	return 0;
}

int main() {
	vector<int> num;
	for (int i = 0; i < 6; i++) {
		num.push_back(i + 1);
	}

	cout << find7_binarySearch(num, 7, 0, num.size() - 1) << '\n';
	cout << find7(num, 7);
}

---

뒤따라오는 정렬(sort)

아까 위에서 이분 탐색을 쓸 땐 정렬이 대부분 뒤따라온다고 했다.

정렬이 필요한 이유는 이렇다.

위의 예시에서는 1~10까지의 자료가 주어졌지만

이런 배열에서는 이분 탐색은 어떻게 이용할까?

3, 6, 8, 4, 10, 5, 1, 2, 7, 9

 

여기다가 바로 이분 탐색을 쓰면 원하는 결과값을 얻지 못한다.

중간값의 기준이 없기 때문이다.

그래서 정렬이 필요하다.

 

선 정렬, 후 이분탐색

---

이진 탐색이 더 빠른 이유

하나하나 비교하면서 할 경우 시간 복잡도가 O(N)이지만 이진 탐색의 경우 O(log N)의 시간 복잡도를 갖는다.

 

[이진 탐색의 시간복잡도를 증명한 블로그]

https://jwoop.tistory.com/9

이진 탐색과 시간 복잡도 분석 (Binary Search and its Time Complexity Analysis)

---

문제 해결 in C++

예시 코드에서 사용된 binarySearch는 있느냐 없느냐를 판별해주는 bool형 함수라서 해당하는 자료가 몇 개 있는지 알 수가 없다.

+

C++ STL에 binary_search(arr.begin, arr.end, find_value)의 함수가 있지만 이 또한 bool형 함수라서 문제를 풀 땐 사용하지 않았다.

 

upper_bound(), lower_bound()

그래서 사용한 것이 이분 탐색을 기반으로 한 두 함수다.

 

upper_bound(arr_begin, arr_end, find_value);

upper_bound는 find_value를 초과하는 가장 작은 첫 번째 원소의 위치를 반환해준다.

ex) 1~10 중에 find_value가 7일 때, 8의 위치를 반환시켜준다.

 

lower_bound(arr_begin, arr_end, find_value);

upper_bound는 find_value와 같거나 큰 값이 언제 처음으로 등장하는지 찾아주는 함수이다.

find_value가 없을 경우 find_value보다 큰 값을 반환해준다.

ex) 1~10 중에 find_value가 7일 때, 7이 처음 등장하는 위치를 반환한다. 7이 없을 경우 8을 반환

 

+아직 이해가 안 간 부분

lower_bound의 반환형은 iterator라서

배열의 경우 배열의 주소에 해당하는 배열의 이름을 빼주고,

벡터 배열의 경우 배열의 시작점(arr.begin())을 빼주면 된다고 한다.

(upper_bound는 이런 설명이 없었지만 문제를 풀어본 결과 upper_bound도 똑같은 처리가 필요했다.)

 

문제에 적용시킨 방법

예를 들어 [7, 7, 7, 8]이라는 배열에서 7이 몇 개인지를 찾을 때

upper_bound(배열 시작, 배열 끝, 7)을 사용하여 8의 위치를 알아내고,

배열에 7이 있으므로 lower_bound(배열 시작, 배열 끝, 7)을 사용하여 7이 처음 등장하는 위치를 알아낸다.

(7이 없을 경우 8이 처음 등장하는 위치와 같다.)

 

그래서, 두 함수의 결괏값의 차로 7이 몇 개가 있는지 알 수 있게 된다.

 

해결 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> card;

	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		card.push_back(a);
	}

	int m;
	vector<int> gotWhat;
	cin >> m;
	for (int i = 0; i < m; i++) {
		int a;
		cin >> a;
		gotWhat.push_back(a);
	}

	sort(card.begin(), card.end());

	vector<int> gotThis;
	for (int i = 0; i < gotWhat.size(); i++) {
		int low = lower_bound(card.begin(), card.end(), gotWhat[i]) - card.begin();
		int upp = upper_bound(card.begin(), card.end(), gotWhat[i]) - card.begin();
		int a = upp - low;
		gotThis.push_back(a);
	}

	for (int i = 0; i < gotThis.size(); i++) {
		cout << gotThis[i] << ' ';
	}

	return 0;
}

---

이진 탐색에 관해 참고할 만한 Post

[이진 탐색에서 흔히 발생하는 오류들 정리]

https://blog.weirdx.io/post/3121

C++ 이진 탐색(Binary Search) 구현 및 흔히 발생하는 오류 - 이상한모임