C++/ 우선순위 큐 + 구조체를 이용한 벡터 정렬 (3개 이상의 값)

인프런 73,74 강의 

 

1. 우선순위 큐

 

앞서 bfs에서 많이 활용한 큐 자료구조는 First in First out 구조로, rear로 데이터가 삽입되고 front로 삭제되는 구조였다.

우선순위 큐란 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 구조이다.

 

우선순위 큐는 최대 힙, 최소 힙을 구현하고자 할 때 쓰이는 자료구조이다.

힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)로서 다음과 같은 힙 속성(property)을 만족한다. 

 

여기서 최대 힙은 내림차순으로 정렬된 이진 트리라고 생각하면 되기 때문에, root에 가장 큰 원소가 들어있는 구조이다

 

#include <stdio.h>
#include <queue>

using namespace std;

int main(){
    int a;
    priority_queue<int> pQ;
    while(true){
        scanf("%d", &a);
        if(a==-1) break;
        if(a==0){
            if(pQ.empty()) printf("-1");
            else{
                printf("%d",pQ.top()); //pQ의 root 값을 출럭
                pQ.pop();
            }
        }
        else pQ.push(a); //알아서 정렬을 해주는듯
    }
    return 0;
}

코드에서는 최대 힙을 구성하는 우선순위 큐를 만들고있다.

a라는 값을 받았을 때, -1 일때 break, 0 일때 top의 원소를 pop 하는 조건.

그 외의 값이 들어왔을 시에는 pQ에 push 해준다.

 

 

반대로 최소 힙은 root에 가장 작은 원소가 들어있기 때문에, 구현을 하려면 push, pop 할 때 원소의 부호를 달리하여 저장하고 삭제하면 된다.

 

#include <stdio.h>
#include <queue>

using namespace std;

//Min heap
int main(){
    int a;
    priority_queue<int> pQ;
    while(true){
        scanf("%d", &a);
        if(a==-1) break;
        if(a==0){
            if(pQ.empty()) printf("-1");
            else{
                printf("%d",-pQ.top()); //pQ의 root 값을 출럭
                pQ.pop();
            }
        }
        else pQ.push(-a); //알아서 정렬을 해주는듯
    }
    return 0;
}

 

 

2. Struct를 이용한 벡터의 정렬

 

struct를 이용한 벡터의 정렬을 이해하기 위해서는 연산자 오버로딩, 생성자에 대한 개념을 이해해야한다.

2학년때 배웠으나 C++, Java를 멀리했기 때문에 당근 기억이 나지 않고 이번 기회에 정리를 해야겠다!!

 

연산자 오버로딩이란 ?

오버로딩은 메서드의 이름을 동일시한 채로 매개변수를 다르게 함으로써 메서드 여러개를 사용할 수 있게 하는 것을 말한다.

따라서 연산자 오버로딩을 이용하면 기존에 C++에서 제공하고 있는 연산자를 재정의하여 사용자 정의 클래스로 사용할 수 있게된다. 대부분의 기본 제공 연산자 함수는 전역 함수 또는 클래스, Struct로 재정의가 가능하다.

 

연산자 오버로딩은 함수로써 작동하기 때문에 함수로 정의해주어야한다.

 

int operator+(Edge &edge1, Edge &edge2){
    return edge1.distance + edge2.distance;
}

+ 오버로딩을 한 모습

 

그렇다면 벡터 내에 저장되어있는 원소들을 정렬하려면?! 

sort 함수는 원소가 두 개인 경우에만 가능하기 때문에, 3개 이상의 원소를 가진 벡터를 정렬하려면 연산자 오버로딩이 필요하다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//  구조체를 이용해서 벡터를 정렬하는 방법
struct Loc{
    int x, y, z;
    Loc(int a, int b, int c){
        x=a;
        y=b;
        z=c;
    }//constructor
    bool operator<(const Loc &b)const{ //상수 멤버함수. x,y,z 값을 바꿀 수가 없음
        //return x<b.x; //오름차순으로 정렬
        if(x!=b.x) return x<b.x;
        if(y!=b.y) return y<b.y; // x=b.x
        if(z!=b.z) return z<b.z; // x=b.x, y=b.y
    }//연산자 오버로딩
};
int main(){
    vector<Loc> XY;
    XY.push_back(Loc(2,3,5));
    XY.push_back(Loc(3,6,7));
    XY.push_back(Loc(2,3,1));
    XY.push_back(Loc(5,2,3));
    XY.push_back(Loc(3,1,6));
    sort(XY.begin(), XY.end());
    for(auto pos: XY) cout<<pos.x<<" "<<pos.y<<" "<<pos.z<<endl;


    return 0;
}

이런식으로,,

이렇게 해주면 멤버가 여러개 일 때도 필요한 원소들의 정렬을 통해 문제를 쉽게 가져갈 수 있다

 

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

struct Data{
    int money;
    int when;
    Data(int a, int b){
        money=a;
        when=b;
    }
    bool operator<(Data &b){
        return when>b.when; //시간 기준으로 내림차순으로 정렬
    }
};
int main(){
    int n, i, j, a, b, res=0, max=-2147000000;
    vector<Data> T; //구조체. 벡터형으로 넣는다.
    priority_queue<int> pQ;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d %d", &a,&b);
        T.push_back(Data(a,b)); //생성자 호출!!
        if(b>max) max=b; //max는 마지막 강연할 날짜.
    }
    sort(T.begin(),T.end());
    j=0;
    for(i=max;i>=1;i--){
        for( ;j<n;j++){
            if(T[j].when<i) break;
            pQ.push(T[j].money);
        }
        if(!pQ.empty()){
            res+=pQ.top();
            pQ.pop();
        }
    }
    printf("%d",res);
    return 0;
}

 

75번의 코드이다.

오버로딩부터 대충 봐서 머리에 남지를 않았네

복습을 하러 가야겠다