이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 11 번째 글 입니다.
목차
실버4 : 이분 탐색 문제이다.
생각
특정 숫자가 등장하는 lowerBound와 UpperBound를 잡아내면 끝나는 문제이다.
LowerBound
원하는 숫자가 처음으로 등장하는 곳의 번째
기본적인 이분 탐색은, 내가 탐색한 index를 포함하지 않은 상태로 다음 index를 탐색한다. 그리고 찾으면 return한다. 하지만, 이번에 우리가 할 것은, 해당 숫자의 범위를 탐색하는 것이기 때문에, 찾았다고 해서 탐색을 끝낼 수 없다. 다만, 내가 원하는 값과 같은 값이 있다면, 그 index는 답의 후보가 될 수 있다. 최종적인 답은 끝까지 탐색한 후에 도출되도록 만들어야 한다. 예시를 보자.
0 1 2 3 4 5 6 7 8 9 10
-10 -10 2 3 3 6 7 10 10 10 13
정렬이 된 상태에서 10의 lowerBound를 찾아보자.
#1
start : 0 end : 11 mid : 5 a[5] : 6
이 상황에서 답은 무조건 5보다 큰 index에서 나올 수 밖에 없다. 따라서 start = mid + 1 해준다.
#2
start : 6 end : 11 mid : 8 a[8] : 10
8의 index에서 찾는 값이 나왔다. 해당 index는 답의 후보이다. 그렇기 때문에 이것을 포함한 상태로 다음 값으로 넘어가야 한다. end = mid
#3
start : 6 end : 8 mid : 7 a[7] : 10
또 후보값이 나왔다. 이 때 index가 더 작으면서 10을 만족하기 때문에 end = mid해준다.
#4
start : 6 end : 7 mid : 6 a[6] : 7
7보다 큰곳에서 10은 나온다. 따라서 start = mid + 1 해준다.
#5
start : 7 end : 7 mid : 7 a[7] : 10
start와 end가 같아졌다. 원래 이분탐색과 다르게 이러한 조건 때문에 start = end인 상황에서 탐색을 계속할 수 없다. 같아지는 순간 종료한다.
기본적인 이 알고리즘의 핵심은,
- 원하는 수를 찾는다.
- 원하는 수를 찾았으면 그 수를 end에 박아두고 계속 탐색한다.
이렇게 압축할 수 있다. 만약 원하는 수가 없다면 어떻게 될까? 기본적으로 제시한 숫자의 value가 원하는 값보다 크거나 같을 경우, end = mid하기 때문에 없다면 원하는 값보다 큰 수중에서 가장 작은 수의 위치를 return할 것이다. 즉, 1 3 5 7에서 4를 찾는다면, 없기 때문에 lowerBound는 3(index = 2)를 리턴한다.
Code
int lowerBound(int num){
int start = 0, end = N, mid = 0;
while (start < end) {
mid = (start+end)/2;
if (a[mid] < num) {
start = mid + 1;
} else {
end = mid;
}
}
return end + 1;
}
UpperBound
원하는 숫자보다 처음으로 크게되는 위치
lowerBound와 다르게, 10을 찾는다면, 10보다 처음으로 크게되는 위치를 리턴하게 된다.
이분 탐색으로부터 생각해보자. 원래 같으면 같을 때, 탈출하여 답을 제시한다. 하지만, 내가 원하는 것은 찾은 뒤에 어떠한 조치가 필요하다. 찾은 값은, lowerBound에서와 다르게, 답의 후보가 될 수 없다. 예를 들어, 내가 10이라는 값을 찾았다. 하지만 위에 정한 정의는 10을 찾은 것이 중요한 것이 아니고, 10보다 언제 처음으로 커지냐가 궁금하다. 따라서 찾았다면, 해당 제시한 위치는 답이 될 수 없다. 따라서 이 값을 포함하지 않고 탐색해야 한다. 예시를 보자.
#1
start : 0 end : 11 mid : 5 a[5] : 6
6은 10보다 작으므로 이 곳에서 답이 나올 수는 없다. start = mid + 1
#2
start : 6 end : 11 mid : 8 a[8] : 10
8위치에서 10이 나왔지만, 이 10은 내가 원하는 답이 아니다. start = mid + 1
#3
start : 9 end : 11 mid : 10 a[10] : 13
10의 위치에서 13이 나왔고, 10의 upperBound는 이 값을 포함한 아래 영역에서 나온다. 따라서 해당 10 index는 포함한 상태로 탐색을 진행한다. end = mid
#4
start : 9 end : 10 mid : 9 a[9] : 10
9위치에서 10이 나왔지만, 이 10은 내가 원하는 답이 아니다. start = mid + 1
#5
start : 10 end : 10 mid : 10 a[10] : 13
start = end가 되어 종료한다. upperBound는 10이다.
결국, 어느 범위에서 답이 나타날 수 있는지를 명확하게 규명하는 것이 중요하다. upperBound도 lowerBound와 마찬가지로 탐색하는 값이 없다면 이 값보다 큰 수들 중 가장 작은 수의 위치를 리턴한다. 아, 잘 생각해야 하는 부분이 있는데, 탐색 범위를 0~N-1로 하면 안된다. 그렇게 될 경우, 맨 끝에 내가 찾고싶은 값이 있을 때, 원하는 index를 반환할 수 없다.
1 10 10 10
이런 경우에 10의 upperBound를 찾는다고 해보자. 정의에 의하면 답은 당연히 5이다. 하지만 내가 탐색을 진행할 때, start = 0, end = 3이라고 놓고 생각하면, 최종 탐색 결과는 3을 넘지 못하고 return 값은 1을 더한 4이다. 즉 절대로 4를 넘은 값이 나올 수가 없다. 위에 정의한 upperBound 정의의 일관성을 잃지 않기 위해서는 end의 index를 하나 늘려서 정해놓는 것이 바람직하다.
Code
int upperBound(int num){
int start = 0, end = N, mid = 0;
while (start < end) {
mid = (start+end)/2;
if (a[mid] <= num) { // 등호만 다르다.
start = mid + 1;
} else {
end = mid;
}
}
return end + 1;
}
이 문제 해설
이 문제는 해설할 것이 없다. 저 위에 설명한 것이 곧 답이다..
Code
#include<iostream>
#include<vector>
#include<algorithm>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<queue>
#include<functional>
using namespace std;
typedef long long ll;
int N, M;
int a[500001];
int lowerBound(int num){
int start = 0, end = N, mid = 0;
while (start < end) {
mid = (start+end)/2;
if (a[mid] < num) {
start = mid + 1;
} else {
end = mid;
}
}
return end + 1;
}
int upperBound(int num){
int start = 0, end = N, mid = 0;
while (start < end) {
mid = (start+end)/2;
if (a[mid] <= num) {
start = mid + 1;
} else {
end = mid;
}
}
return end + 1;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N;
for (int i = 0; i < N; i++) cin >> a[i];
sort(a, a+N);
cin >> M;
for (int i = 0; i < M; i++) {
int num, ans = 0;
cin >> num;
int low = lowerBound(num);
int high = upperBound(num);
if (low != high) ans = high-low;
cout << ans << " ";
}
return 0;
}
STL upperBound, lowerBound를 이용한 풀이
#include<iostream>
#include<vector>
#include<algorithm>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<queue>
#include<functional>
using namespace std;
typedef long long ll;
int N, M;
int a[500001];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N;
for (int i = 0; i < N; i++) cin >> a[i];
sort(a, a+N);
cin >> M;
for (int i = 0; i < M; i++) {
ll num, ans = 0;
cin >> num;
ll low = lower_bound(a, a+N, num)-a;
ll high = upper_bound(a, a+N, num)-a;
if (low != high) ans = high-low;
cout << ans << " ";
}
return 0;
}