인프런 영문 브랜드 로고
인프런 영문 브랜드 로고

인프런 커뮤니티 질문&답변

다람님의 프로필 이미지
다람

작성한 질문수

it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비

79. 원더랜드 : Prim MST(최소스패닝트리) 알고리즘 : priority_queue 활용

질문있습니다.

해결된 질문

작성

·

388

1

bool operator<( Edge &b){

    return val > b.val;

}

이렇게 작성하면 priority_queue에서는 최소 힙으로 된다고 하셨는데요.

 

sort( ~.begin(), end())는 큰 순서대로 내림차순으로 배열되던데요. 

 

혹시, 이해하기 쉬운 방법이 있을까요?

제 기준에는 완전히 서로 반대로 정렬이 되어버리는 것 같습니다. 

 

항상 쉽게 설명해주셔서 감사드립니다! 

답변 2

1

김태원님의 프로필 이미지
김태원
지식공유자

▣ 구조체형의 벡터를 잡고 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;  //최대힙

}

저는 이렇게 외우고 메뉴얼 처럼 사용합니다.

0

다람님의 프로필 이미지
다람
질문자

감사합니다! 이해가 쉽게 되었습니다.

다람님의 프로필 이미지
다람

작성한 질문수

질문하기