알고리즘교안 p121 구조체를 담은 우선순위큐 질문
안녕하세요 교안공부중에 모르는 부분이 있어 질문드립니다.
교안 p121을 보면 구조체를 담은 우선순위큐에서 따로 sort()등의 함수를 사용하지 않고 데이터를 .push() 만 했을 뿐인데 출력하니 구조체 안에 선언된 연산자 오버로딩에 따라 정렬된 값을 출력하더라구요
어떤 방식으로 이게 가능한건가요? 우선순위 큐 자료구조만의 특징인가요? 이해가 잘 되지 않아서 vector를 이용하여 같은 방식으로 해보니 따로 정렬이 되지 않더라구요
교안 P121에 나온 '구조체를 담은 우선순위큐' 코드
#include <bits/stdc++.h>
using namespace std;
struct Point{
int y, x;
Point(int y, int x) : y(y), x(x){}
Point(){y = -1; x = -1; }
bool operator < (const Point & a) const{
return x > a.x;
}
};
priority_queue<Point> pq;
int main(){
pq.push({1, 1});
pq.push({2, 2});
pq.push({3, 3});
pq.push({4, 4});
pq.push({5, 5});
pq.push({6, 6});
cout << pq.top().x << "\n";
return 0;
}
제가 작성한 vector를 이용한 코드는 다음과 같습니다
#include <bits/stdc++.h>
using namespace std;
struct Point {
int y, x;
Point(int y, int x) : y(y), x(x) {}
Point() { y = -1; x = -1; }
bool operator < (const Point & a) const {
return x > a.x; // x 멤버변수를 기준으로 내림차순 정렬
}
};
vector<Point> v;
int main() {
v.push_back({1, 1});
v.push_back({2, 2});
v.push_back({3, 3});
v.push_back({4, 4});
v.push_back({5, 5});
v.push_back({6, 6});
for(auto a : v) cout << a.y << " : " << a.x << '\n';
return 0;
}
앞쪽에 보면 operator 연산자 오버로딩을 구조체안에 선언하지 않고 따로 cmp함수로 만들어 sort() 함수에 3번째 인자로 넣어서 정렬하는것은 이해하였습니다.
위의 코드에서 제가 잘못 작성한 부분이 있어서 정렬이 안되는건지, 아니면 우선순위큐 자료구조만 가능한 코드인것인지 아니면 아예 제가 뭔가를 잘못 이해하고 있는건지 잘 모르겠습니다.ㅠ
답변 1
1
안녕하세요 명운님 ㅎㅎ
vector는 기본적으로 자동정렬을 하지 않습니다. 그저 어떠한 요소를 넣는 바구니인 것이죠.
그러나 priority_queue, 즉 우선순위는 자동정렬을 합니다. 어떤 요소를 넣는다고 했을 때 해당 operator를 기반으로 자동정렬하는 자료구조입니다.
자료구조가 다르기 때문에 이러한 현상이 일어나는 것입니다.
감사합니다.
5-B
0
16
2
4 - A
0
33
2
코딩살구클럽 입장이 안됩니다
0
82
2
4-F 경우의 수 질문입니다.
0
35
2
코딩살구클럽 가입이 안됩니다.
0
85
2
살구 클럽에 대한 질문있습ㄴ디ㅏ
0
63
1
교안 158페이지 문의드립니다
0
46
2
코딩살구클럽 관련 건의사항
0
119
1
코살에 19942 다이어트 문제에 N의 범위가 빠져있슴니다
0
45
1
진행 방법 질문드립니다!
0
83
2
2-I) 왜 이 문제가 그래프이론 카테고리에 있는지 잘 모르겠습니다.
0
64
2
2주차 개념#12 트리 순회
0
33
2
백준사이트가 종료된다고 합니다.
0
318
2
백준 서비스 종료
9
953
1
sk 하이닉스 코테 대비
0
388
2
3-G 최댓값 질문
0
54
1
모듈러 연산 값이 10이 아닌 경우도 있지 않나요?
0
84
2
3-I 코드 질문드립니다.
0
66
2
3-N 질문 있습니다.
0
68
2
학습방법
0
105
2
4-H 질문 있습니다 (코드 리뷰)
0
69
2
코딩테스트 어디까지 준비해야 하는지 질문이 있습니다.
0
186
2
2-O 반례가 무엇일지 어떤 부분이 틀렸는지 잘 모르겠습니다.
0
74
2
2주차 개념 #4-2. 인접행렬 질문있습니다.
0
66
2





