-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
해결됨
질문있습니다.
19.08.16 01:28 작성 조회수 300
1
bool operator<( Edge &b){
return val > b.val;
}
이렇게 작성하면 priority_queue에서는 최소 힙으로 된다고 하셨는데요.
sort( ~.begin(), end())는 큰 순서대로 내림차순으로 배열되던데요.
혹시, 이해하기 쉬운 방법이 있을까요?
제 기준에는 완전히 서로 반대로 정렬이 되어버리는 것 같습니다.
항상 쉽게 설명해주셔서 감사드립니다!
it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
79. 원더랜드 : Prim MST(최소스패닝트리) 알고리즘 : priority_queue 활용
강의실 바로가기
답변을 작성해보세요.
0
0
김태원
지식공유자2019.08.16
▣ 구조체형의 벡터를 잡고 sort()함수를 사용할 때
sort()함수는 선형 자료구조를 오름차순 또는 내림차순으로 일렬로 나열할 때 사용하는 함수입니다.
구조체형의 벡터를 정렬할 때 sort()함수를 쓴다면
bool operator<( Edge &b){
return val > b.val;
}
operator 함수의 return val > b.val;에서 val을 일렬로 나열할 때 앞에 자료, b.val은 뒤에 자료로 생각하고 기준을
잡으시면 됩니다.
return val > b.val; 은 "앞에 자료가 크고 뒤에 자료가 작은 형태로 정렬하라" 이렇게 생각하면
내림차순으로 정렬됩니다.
반면 return val < b.val; 은 "앞에 자료가 작고 뒤에 자료가 크게 정렬하라" 라고 생각하면 오름차순 정렬입니다.
저는 그냥 이렇게 생각하고 사용합니다. 저도 내부 구조를 본것은 아니고 그냥 메뉴얼 처럼 외워서 사용합니다.
▣ priority_queue에 구조체를 사용할 때
우선순위 큐에서 구조체의 operator함수가 작동할 때는 push()나 pop()이 사용될 때 입니다.
즉 우선순위 큐라는 자료구조에 자료를 넣거나 꺼낼 때 operator 함수가 작동하여 최대힙을 만들거나
최소힙을 만든다고 생각하시면 됩니다.
push()됬을 때와 pop()됬을 때 최대힙을 유지하는 과정은 73번 영상에 있습니다.
bool operator<( Edge &b){
return val > b.val; //최소힙
}
에서 매개변수로 넘어온 b.val 값이 기준값이 되어 이 값이 val보다 작으면 최소힙, val보다 크면 최대힙이 된다고 생각하고 사용하면 좋겠습니다.
bool operator<( Edge &b){
return val < b.val; //최대힙
}
저는 이렇게 외우고 메뉴얼 처럼 사용합니다.
답변 2