SCCC - Soongsil Computing Contest Club/2020 Winter-Study
3. heap, priority_queue, set, map
Mosu(정종인)
2020. 1. 9. 20:49
반응형
0. 복습
boj.kr/10989 (counting sort), boj.kr/1427
- heap
자료구조. push, pop이 있음.
heap의 push는 스택과 동일하지만, pop은 가장 큰 값(max heap), 또는 가장 작은 값(min heap)을 뺀다.
구현은 트리로 한다. min heap은 부모보다 자식이 더 크고, max heap은 부모가 자식보다 더 크다.
기본적으로 push는 O(N)의 시간복잡도를 가지고 있지만, 힙의 push는 O(logN)만에 가능하다.
트리의 가장 끝에 원소를 넣고, 자신의 부모와 비교한 후 필요하면 swap한다.
pop도 O(logN)이다.
트리의 루트를 pop하고, 자식들과 값을 비교 한 후 트리에 값을 메운다.
- 힙 구현
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
int arr[10000];
int len;
void push(int n) {
arr[++len]=n;
int t=len;
while(t>1){
if(t%2==0 && t+1<=len && arr[t]>arr[t+1]) t=t+1;
if(arr[t]<arr[t/2]) swap(arr[t], arr[t/2]);
else break;
t/=2;
}
}
int pop(){
if(!len) return -1;
int res=arr[1];
int t=1;
arr[1]=arr[len];
len--;
while(1){
if(t*2>len) break;
if(t*2==len && arr[t]>arr[t*2]){
swap(arr[t], arr[t*2]);
t=t*2;
}
else if(arr[t]<arr[t*2] && arr[t]<arr[t*2+1]) break;
else if(arr[t*2]<arr[t*2+1]) {
swap(arr[t], arr[t*2]);
t=t*2;
}
else {
swap(arr[t], arr[t*2+1]);
t=t*2+1;
}
}
return res;
}
int main(){
int c;
while(1){
printf("choose : ");
cin >> c;
if(c==-1) break;
if(c==1) {
int n;
cin >> n;
push(n);
}
if(c==2) {
cout << pop() << '\n';
}
}
cout << '\n';
for(int i=1; i<=len; ++i){
cout << arr[i] << '\n';
}
}
- priority_queue
heap의 모양이 queue와 유사하다. 그래서 priority_queue의 이름이 붙여졌다.
queue와 동일하게 push와 pop을 이용하면 된다. 대신, front 대신 top으로 값을 가져와야 한다.
#include <queue>
#include <iostream>
#include <ctime>
using namespace std;
int main(){
srand(time(NULL));
priority_queue<int> pq;
for(int i=0; i<5; ++i){
pq.push(rand()%20);
}
while(!pq.empty()) {
cout << pq.top() << '\n';
pq.pop();
}
}default가 max heap이다.
min heap으로 바꾸려면 두가지 방법이 있다.
#include <queue>
#include <iostream>
#include <ctime>
#include <functional>
using namespace std;
int main(){
srand(time(NULL));
priority_queue<int, vector<int>, greater<int> > pq;
for(int i=0; i<5; ++i){
pq.push(rand()%20);
}
while(!pq.empty()) {
cout << pq.top() << '\n';
pq.pop();
}
}이렇게 복잡하게 pq를 선언할 수도 있고
#include <queue>
#include <iostream>
#include <ctime>
#include <functional>
using namespace std;
int main(){
srand(time(NULL));
priority_queue<int> pq;
for(int i=0; i<5; ++i){
pq.push(-(rand()%20));
}
while(!pq.empty()) {
cout << -pq.top() << '\n';
pq.pop();
}
}이렇게 꼼수를 쓸 수도 있다.
참고 문제 : [boj.kr/11279, boj.kr/1927, boj.kr/11286, boj.kr/2841]
- set
binary search tree : 왼쪽 자식 < 부모 < 오른쪽 자식
이게 최악일때 O(N)이 걸린다 => 개선한게 balanced binary search tree : 적절히 트리를 이쁘게 만들어준다
대표적인 balanced binary search tree : 레드블랙트리, AVL, ...
이것의 구현체가 바로 set, map이다.
- 특징erase : O(logN)
- find : P(logN)
- insert : O(logN)
#include <set>
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
int main(){
srand(time(NULL));
set<int> S;
for(int i=0; i<10; ++i){
S.insert(rand()%5);
}
//1. 값 출력
for(int i : S) {
cout << i << ' ';
}
cout << '\n';
// ------------
set<int>::iterator it;
for(it = S.begin(); it != S.end(); ++it) {
cout << *it << ' ';
}
cout << '\n';
// ------------
for(auto it = S.begin(); it != S.end(); ++it) {
cout << *it << ' ';
}
cout << '\n';
//2. find
set<int>::iterator pos = S.find(3); // iterator을 리턴하는 find()
if(pos == S.end()) {
cout << "값 없음" << '\n';
}
if(pos != S.end()) {
cout << "값 있음" << '\n';
S.erase(3);
}
}- map
set의 일종이지만 파이썬의 dictionary라고 생각하면 된다.
따라서 중복된 값을 넣으면 값이 갱신이 된다.
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main(){
srand(time(NULL));
map<string, int> id;
id["Minsu"] = 3;
id["Yeong-hui"] = 4;
cout << id["Minsu"] << '\n';
map<string, string> name2bojid;
name2bojid["민석"] = "cake_monotone";
}참고 문제 : [boj.kr/7785, boj.kr/7662, boj.kr/1620]
- 부록 : 참고 문제 풀이
boj.kr/10989
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
int arr[10001];
int len;
int main(){
int N;
cin >> N;
for(int i=0; i<N; ++i){
int a;
scanf("%d", &a);
arr[a]++;
}
for(int i=1; i<10001; ++i){
for(int j=0; j<arr[i]; ++j) {
printf("%d\n", i);
}
}
}boj.kr/1427
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
bool cmp(char a, char b){
return a>b;
}
int main(){
string s;
cin >> s;
sort(s.begin(), s.end(), cmp);
cout << s << '\n';
}boj.kr/11279
#include <iostream>
#include <queue>
using namespace std;
priority_queue<int> pq;
int main(){
int N;
cin >> N;
while(N--){
int c;
scanf("%d", &c);
if(c==0) {
if(pq.empty()) printf("0\n");
else {
cout << pq.top() << '\n';
pq.pop();
}
}
else {
pq.push(c);
}
}
}boj.kr/1927
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
priority_queue<int, vector<int>, greater<int> > pq;
int main(){
int N;
cin >> N;
while(N--){
int c;
scanf("%d", &c);
if(c==0) {
if(pq.empty()) printf("0\n");
else {
cout << pq.top() << '\n';
pq.pop();
}
}
else {
pq.push(c);
}
}
}boj.kr/11286
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
priority_queue<int, vector<int>, greater<int> > pqyang;
priority_queue<int> pqemm;
int main(){
int N;
cin >> N;
while(N--){
int c;
scanf("%d", &c);
if(c==0) {
if(pqyang.empty() && pqemm.empty()) printf("0\n");
else {
if(pqemm.empty()){
cout << pqyang.top() << '\n';
pqyang.pop();
}
else if(pqyang.empty()){
cout << pqemm.top() << '\n';
pqemm.pop();
}
else{
if(pqyang.top() < -pqemm.top()) {
cout << pqyang.top() << '\n';
pqyang.pop();
}
else {
cout << pqemm.top() << '\n';
pqemm.pop();
}
}
}
}
else {
if(c>=0) pqyang.push(c);
else pqemm.push(c);
}
}
}boj.kr/2841
#include <iostream>
#include <queue>
using namespace std;
priority_queue<int> pq[7];
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
int N, P;
cin >> N >> P;
int cnt = 0;
for(int i=0; i<N; ++i){
int a, b;
cin >> a >> b;
while(1){
if(pq[a].empty()) {
pq[a].push(b);
cnt++;
break;
}
else if(pq[a].top() == b) {
break;
}
else if(pq[a].top() < b) {
pq[a].push(b);
cnt++;
break;
}
else {
pq[a].pop();
cnt++;
}
}
}
cout << cnt << '\n';
}boj.kr/7785
#include <set>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
set<string> s;
vector<string> v;
int main(){
int N;
cin >> N;
for(int i=0; i<N; ++i){
string a, b;
cin >> a >> b;
if(b == "enter") {
s.insert(a);
}
else{
s.erase(a);
}
}
for(set<string>::iterator it=s.begin(); it!=s.end(); ++it){
v.push_back(*it);
}
for(int i=v.size()-1; i>=0; --i){
cout << v[i] << '\n';
}
}boj.kr/7662
#include <iostream>
#include <queue>
#include <vector>
#include <map>
using namespace std;
int main(){
ios_base::sync_with_stdio(false); cin.tie();
int T;
cin >> T;
while(T--){
map<int, int> m;
int N;
cin >> N;
for(int i=0; i<N; ++i){
char c;
int a;
cin >> c >> a;
if(c=='I') {
auto pos=m.find(a);
if(pos==m.end()) {
m[a]=1;
}
else{
m[a]++;
}
}
else if(c =='D'){
if(m.empty()) continue;
if(a==1){
auto it=--m.end();
it->second--;
if(it->second == 0)
m.erase(it);
}
else {
auto it=m.begin();
it->second--;
if(it->second == 0)
m.erase(it);
}
}
}
if(m.empty()) cout << "EMPTY" << '\n';
else {
auto itb = m.begin();
auto it = --m.end();
cout << it->first << ' ' << itb->first << '\n';
}
}
}boj.kr/1620
#include <iostream>
#include <map>
#include <algorithm>
#include <string>
using namespace std;
string arr[100001];
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
map<string, int> m1; // string, int
int N,M;
cin >> N >> M;
for(int i=1; i<=N; ++i){
string s;
cin >> s;
m1[s] = i;
arr[i]=s;
}
for(int i=0; i<M; ++i){
string s;
cin >> s;
int k=atoi(s.c_str());
if(k) {
cout << arr[k] << '\n';
}
else{
cout << m1[s] << '\n';
}
}
}반응형