3. heap, priority_queue, set, map

 

3.md

0.01MB

 

0. 복습

boj.kr/10989 (counting sort), boj.kr/1427

1. 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';
    }
}

2. 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]

3. 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);
  }
}

4. 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]

99. 부록 : 참고 문제 풀이

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';
        }
    }
}