이것 저것 &

upper_bound 와 lower_bound 함수는 정렬된 배열에서 원하는 값의 위치의 인덱스를 반환하는 함수 입니다.

#include <algorithm> 라이브러리에 존재합니다. 

사용 예시입니다. 선행조건은 꼭 정렬되어있는 배열을 넣어야합니다.

int val = lower_bound(arr, arr + n, num ) - arr ;
int val = upper_bound(arr, arr + n, num ) - arr ;

위처럼 사용하고 lower_bound는 arr배열의 0~n까지중  num값인덱스 중 제일 작은 값을 반환 합니다. 

upper_bound는 arr배열의 0~n까지중 num보다 큰 가장작은 값의 인덱스 값을 반환합니다.

즉 1 2 3 3 3 3 4 배열에서 num=2인 lowerbound는 1을 반환, upperbound는 2를 반환하는 형태입니다. (2값의 인덱스 1, 3값의 인덱스 2)

연습문제 링크:https://www.acmicpc.net/problem/3020

직접 이분탐색을 구현해서 풀어도 되지만 upper_bound, lower_bound 을 사용하는데 좋은 예제이기 때문에 가져왔습니다. 

문제 해설:https://gusdnr69.tistory.com/59

화이팅입니다! :)

아래 그림처럼 사용을 한다.

cmath는 c++에서의 표준라이브러리로 각종 수학함수들을 가지고 있다. (math.h 를 사용해서 구현해도 괜찮다.)

특이하게 min, max는 algorithm 라이브러리에 존재하는 것을 주의 하자.

1. 헤더 선언 #include <algorithm>

2. sort( start, end) or sort( start, end, compare)

ex) sort(arr, arr+n)  sort(arr, arr+n,cmp)

시작주소와 끝주소 그리고 cmp함수가 필요합니다.

sort( start, end) -> 이형태는 단순 오름차순으로 정렬해줍니다.

sort함수를 퀵정렬법을 사용하기 때문에 O(nlgn) 입니다.

cmp 구현방법입니다.

left<right return true; -> 오름차순

left>right return true; -> 내림차순

사용예제입니다.

bool cmp(info a, info b) {
	if (a.korean > b.korean)  //1
		return true;
	else if(a.korean == b.korean){
		if (a.english < b.english) return true; //2
		else if(a.english == b.english){
			if (a.math > b.math) return true; //3
			else if(a.math == b.math) {
				if (a.name < b.name)return true; //4
			}
		}
	}

	return false;
}

문제 링크:https://www.acmicpc.net/problem/10825

저렇게 사용하는 방법은 단순한 규칙입니다. 퀵정렬방법을 아시는 분들이 왜 저렇게 사용하는지 이해하시겠지만, 이해가 안된다면 방식으로 외워서 사용하는 것도 우선은 괜찮습니다..

정답코드입니다.

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
struct info {
	string name;
	int korean;
	int english;
	int math;
};

info arr[100001];
int n = 0;

/*
국어 점수가 감소하는 순서로
국어 점수가 같으면 영어 점수가 증가하는 순서로
국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로
모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키 코드에서 대문자는 소문자보다 작으므로 사전순으로 앞에 온다.)
*/
bool cmp(info a, info b) {
	if (a.korean > b.korean)  //1
		return true;
	else if(a.korean == b.korean){
		if (a.english < b.english) return true; //2
		else if(a.english == b.english){
			if (a.math > b.math) return true; //3
			else if(a.math == b.math) {
				if (a.name < b.name)return true; //4
			}
		}
	}

	return false;
}
int main() {

	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> arr[i].name >> arr[i].korean >> arr[i].english >> arr[i].math;

	sort(arr, arr + n, cmp);

	for (int i = 0; i < n; i++)
		cout << arr[i].name <<'\n';

}