글 읽기 - lower_bound 동작 원리를 정확하게 모르겠네요 ㅠㅠ

pops1915 1년 전 0

당연히 binary search 기반으로 작동하는 것은 알고 있습니다.

근데 저번에도 compare 함수를 커스텀 하는 과정에서 어떠한 오류가 뜨는데 구글링을 많이 해도 자세하게 나오는 게 잘 없네요 ㅠㅠ

이번에도 compare 함수를 커스텀 하는데 오류가 뜹니다.

완전히 작성된 코드는 아니고 작성하고 있는 중간입니다.

문제가 생기는 부분이 41번 줄 lower_bound 입니다.

cf 함수가 커스텀 compare 함수입니다.

compare 함수의 두번째 인자에 찾을 수가 들어가고 첫번째 인자는 배열에서 돌려가면서 찾는거로 알고 있습니다 물론 틀릴수 있습니다...자세히 나와있는 글을 아직 못찾았습니다.

아래 코드를 적으면

lower_bound 아래에 빨간 밑줄이 쳐지면서 std::pari<int,int>* 형식의 값을 사용하여 int형식의 엔터티를 초기화 할 수 없습니다 라고 나옵니다.

혹시 자세히 아시면 가르쳐 주시면 감사하겠습니다 ㅠㅠ

#include<iostream>
#include<cmath>
#include<vector>
#include<string>
#include<algorithm>
#include<utility>
#include<cstdlib>
#include<set>
#include<cstring>
using namespace std; 

int n, q;
bool compf(pair<int, int> a, pair<int, int> b) {
	if (a.first == b.first) return a.second < b.second;
	return a.first < b.first;
}
bool comps(pair<int, int> a, pair<int, int> b) {
	if (a.second == b.second)return a.first < b.first;
	return a.second < b.second;
}
bool cf( pair<int, int> a,  int b) { return a.first < b; }

int main() { 
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	pair<int,int>* af = new pair<int, int>[n];
	pair<int, int>* as = new pair<int, int>[n];
	int a, b;
	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		af[i].first = a;
		af[i].second = b;
		as[i].first = a;
		as[i].second = b;
	}
	sort(af, af + n, compf);
	sort(as, as + n, comps);
	cin >> q;
	for (int x = 0; x < q; x++) {
		cin >> a >> b;
		int f = lower_bound(af, af + n,a,cf);
	}

	delete[]af;
	delete[]as;
	return 0;
}

pill27211 1년 전 1

af의 요소들은 아시다시피 pair<int, int>로 이루어져 있습니다. 그리고 lower_bound는 반복자를 반환 하지요.

따라서,

의도하신 게 인덱스를 찾고자 하신 거라면

int f = lower_bound(af, af + n,a,cf) - af;

와 같이 바꿔주셔야 하고,

요소를 뽑아내고자 하신거라면

pair <int, int> f = *lower_bound(af, af + n, a, cf);

와 같이 바꿔주셔야 합니다.

( = 형을 맞춰 주어야 함.)

그리고 팁으로 auto 키워드가 있습니다.(타입 추론)

auto f = lower_bound(af, af + n,a,cf);

-> (타겟의 반복자를 f에 담음)

pops1915 1년 전 0

앗 반복자를 반환하는 것을 생각을 못하고 compare 함수에 문제가 있다고 생각을 했네요.

뒤에 af 를 빼주니 정상적으로 작동을 합니다.

compare 함수를 저렇게 커스텀 해도 괜찮겠죠?

좋은 답변 감사합니다.

pill27211 1년 전 2

네 compare 함수에는 문제가 없어 보입니다.

c++에서 bool compare 함수 디자인 시 주의할 점은 아래 글에 남긴 답변을 참고 하시면 됩니다.

https://www.acmicpc.net/board/...

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

lower_bound 동작 원리를 정확하게 모르겠네요 ㅠㅠ

pops1915 1년 전 0

pill27211 1년 전 1

pops1915 1년 전 0

pill27211 1년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말