[acmicpc] upper bound (feat. 이진 검색 알고리즘) / C++

출처 => [알고리즘 해결을 위한 창의적 알고리즘 해결 (중급)]

 

문제

두 번째 예시에서의 출력은 6아닌 7이다 (오타)

문제 분석

문제의 의도 : k를 초과하는 가장 첫 번째 원소의 위치를 구하는 것

① 먼저 구간을 설정한다. ([s, e])

② 이 구간의 중간위치의 값을 m이라고 하면, A[m-1]<=k 이면서 A[m]>k 인 최소 m을 찾아야 한다.

 

풀이

=> 예시로 주어진 배열 A는 1,2,7,7,7,7,11,15이다. k의 값은 7이다. 따라서 출력값은 7이 나와야 한다.

 

=> 주어진 배열은 [0,8]이고 이에 따라 중간값의 위치인 m은 4이다. 우리가 원하는 것은 찾으려는 값의 위치가 아니라 k값보다 큰 수가 처음으로 등장하는 위치이다. A[4]=7이므로 우리의 위치와 일치하지 않다. 

=> A[6]>7 이므로 그보다 아래로 범위를 설정하여 재탐색

=>A[5]=7이므로 범위를 재설정하여 탐색

=> 범위가 6에서 6으로 좁혀졌으므로 A[6]이 k보다 큰 수가 처음으로 등장하는 위치의 숫자이다.

 

소스 코드 & 결과

#include<iostream>
using namespace std;

int n, k, A[10000001];
//배열의 수, 찾고자 하는 수, 배열을 선언해줌 (public)

int solve(int s, int e) {
	while (e - s > 0) {
		int m;
		m = (e + s) / 2;
		if (A[m] <= k) s = m + 1;
		else e = m;
	}
	return e + 1;
//이런식으로 가다보면 A[m]<=k, A[m+1]>k인 경우가 나올 것이다. 
//이 때는 m=e이므로 출력값은 e+1이 된다.
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> A[i];
	}
	cin >> k;
	cout << solve(0, n) << endl;
}

▶ 결과는 다음과 같게 나온다. 

 

추가사항(about upper_bound)

▶ algorithm 해더함수를 include하여 STL을 활용할 수 있다. 

S라는 배열의 처음부터 n-1까지의 원소들 중, k의 upper bound에 해당하는 원소의 주소를 반환하는 std::upper_bound()를 이용할 수 있다.

std::upper_bound(S,S+n,k,[compare]);

compare을 생략할 경우에는 오름차순이라고 가정한다. 

upper_bound를 이용하면 k의 lower bound위치의 주소를 알려준다. 

따라서 그 주소에서 A를 빼면 k가 존재하는 배열 A의 인덱스가 되며, 배열의  인덱스는 0부터 시작하므로 1을 더해주면 우리가 원하는 해를 구할 수 있다. 

#include<iostream>
#include<algorithm>
//upper_bound를 활용
using namespace std;

int n, k, A[100001];
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> A[i];
	}
	cin >> k;
	cout << upper_bound(A, A + n, k) - A + 1 << endl;
}