2025년, 코딩은 선택이 아닌 필수!

2025년 모든 학교에서 코딩이 시작 됩니다. 먼저 준비하는 사람만이 기술을 선도해 갑니다~

강의자료/알고리즘

[자료구조] 우선순위큐(Priority Queue)

원당컴1 2020. 11. 17. 18:38
우선순위큐(Priority Queue) 란?

우선순위를 가진 항목들을 저장하는 큐 FIFO 순서가 아니라 우선순위가 높은 데이터가 먼저 나가게 된다.

 

응용분야

- 시뮬레이션 시스템
- 네트워크 트래픽 제어
- 운영체제에서의 작업 스케줄링

 

우선순위큐 STL 기본 형태

priority_queue<T,Container,Compare> : 원하는 자료형 및 클래스 T를 통해 생성, 여기서 Container는 Vector와 같은 컨테이너 이며 Compare 는 비교 함수 클래스(단,Compare 조건에서 참인 것이 후 순위로 밀린다.)

 

우선순위큐 함수

push(element) : 우선순위 큐에 추가
pop() : 원소 삭제
top() : top에 있는 원소를 반환
empty() : 비어있으면 true 아니면 false
size() : 우선 순위 큐에 포함되어 있는 원소들의 수를 반환

 

우선순위큐 구현 예

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
struct INT{
    public :
        int a;
        INT(){};
        INT(int x){a=x;};
};
struct cmp{
    bool operator()(INT a,INT b)
    {
        return a.a < b.a;
    }
} ;
 
int main()
{
    priority_queue<INT,vector<INT>,cmp>pq;
    pq.push(INT(2));
    pq.push(INT(5));
    pq.push(INT(8));
    while(!pq.empty())
    {
        INT imsi = pq.top();
        cout << imsi.a << endl;
        pq.pop();
    }
    return 0;
}
 
cs

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
struct INT{
    public :
    int a;
    INT(){};
    INT(int x){a=x;};
};
 
bool operator<(INT a,INT b)
{
        return a.a < b.a;
}
 
int main()
{
    priority_queue<INT>pq;
    pq.push(INT(2));
    pq.push(INT(5));
    pq.push(INT(8));
    while(!pq.empty())
    {
        INT imsi = pq.top();
        cout << imsi.a << endl;
        pq.pop();
    }
    return 0;
}
 
 
cs

 

 

문제풀이

www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2630&sca=9010

 

JUNGOL

 

www.jungol.co.kr

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <queue>
 
using namespace std;
 
typedef struct info
{
    int id;
    int w; //시간
    int num; //계산대번호
    bool operator < (const info &r) const{
        if(w>r.w)return true;
        else if(w==r.w)
        {
            if(num<r.num)return true//계산대 번호가 큰걸 뽑자
        }
        return false;
    }
}info;
 
priority_queue <info> pq1;//outq
 
typedef struct data
{
    int id;
    int t;
    int num;
    bool operator < (const data &r) const{
        if(t>r.t)return true;
        else if(t==r.t)
        {
            if(num>r.num)return true//계산대 번호가 작은걸 뽑자.
        }
        return false;
    }
}data;
 
priority_queue <data> pq2;//inq
 
int main()
{
    //freopen("input.txt","r",stdin);
    int n,k,i;
    int a,b;
    scanf("%d %d",&n,&k);
    data tmp;
    info imsi;
 
    for(i = 0;i < n;i++)
    {
 
        scanf("%d %d",&a,&b);
        if(i<k)
        {
            tmp.num = i+1;
            tmp.t = b;
            tmp.id = a;
           // pq2.pop();
            pq2.push(tmp);
 
            imsi.id = a;
            imsi.num = tmp.num;
            imsi.w = b;
            pq1.push(imsi);
        }
        else
        {
            tmp = pq2.top();
            pq2.pop();
 
            tmp.id = a;
            tmp.t += b;
 
            imsi.id = tmp.id;
            imsi.num = tmp.num;
            imsi.w = tmp.t;
            pq1.push(imsi);
            //printf("(%d,%d,%d)\n",imsi.id,imsi.num,imsi.w);
 
            pq2.push(tmp);
        }
 
    }
    int ind=1;
    long long int sum=0;
    while(!pq1.empty())
    {
        sum += (long long)ind*pq1.top().id;
        //printf("%d\n",pq1.front().id);
        ind++;
        pq1.pop();
    }
    printf("%lld",sum);
    return 0;
}
cs
사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 통신판매신고번호 : 호 | 사이버몰의 이용약관 바로가기