Binary Search, Min heap

BS를 사용하면 정렬된 상황이라 자주 사용하지 않을 것 같지만 매우 자주 사용한다.

 

연료 게이지 상태를 확인(재귀로 작성)

100%는 예외로 처리

#include <iostream>
using namespace std;
char full[11] = "##########";

void bs(int s, int e)
{
    int mid = (s+e) / 2;
    if(s > e)
    {
        cout << "연료 없음";
        return;
    }
    if(full[mid] == '_' && full[mid-1] =='#')
    {
        cout << mid * 10 << '%';
        return;
    }
    if(full[mid] == '#')
        bs(mid+1, e);
    else
        bs(s, mid-1);
}
int main()
{
    if(full[9] == '#')
        cout << "100%";
    else
        bs(0, 9);
    return 0;
}

 

만약 전체 크기에서

"___###____" 와 같은 경우 시작 지점을 O(n) 탐색으로 찾고 그 곳부터 BS를 하여서 마지막 위치를 알아내야한다. 

 

Minheap 직접 구현

push, top, pop 함수로 구성

#include <iostream>
using namespace std;
int vect[10], hn;

void push(int value)
{
    vect[++hn] = value;
    int now = hn, parent;
    while(1)
    {
        parent = now / 2;
        if(vect[parent] <= vect[now]) break;
        swap(vect[parent], vect[now]);
        now = parent;
    }
}
int top()
{
    return vect[1];
};

void pop()
{
    vect[1] = vect[hn--];
    int now = 1;
    int son;
    while(1)
    {
        son = now * 2;
        if(son+1 <= hn && vect[son] > vect[son+1]) son++;
        if(son > hn || vect[son] > vect[now]) break;
        swap(vect[son], vect[now]);
        now = son;
    }
}
int main()
{
    push(1);
    push(7);
    push(5);
    push(2);
    push(9);
    
    cout << top();
    pop();
    cout << top();
    pop();
    cout << top();
    pop();
    return 0;
}

 

Heap 

STL 사용해보기

#include <iostream>
#include <queue>
using namespace std;
priority_queue<int> q; // max heap
priority_queue<int, vector<int>, greater<int>> q2; // min heap

int main()
{
    q.push(1);
    q.push(2);
    q.push(6);
    q.push(3);
    q.push(4);
    
    for(int i=0; i<5; i++)
    {
        cout << q.top();
        q.pop();
    }
    return 0;
}

오름차순 힙, 내림차순 힙

#include <iostream>
#include <queue>
using namespace std;

priority_queue<int> q1;
priority_queue<int, vector<int>, greater<int>> q2;
int main()
{
    int vect[6] = {4, 3, 5, 1, 6, 4};
    
    // 내림차순 출력
    for(int i=0; i<6; i++)
        q1.push(vect[i]);
    for(int i=0; i<6; i++)
    {
        cout << q1.top() << ' ';
        q1.pop();
    }
    cout << '\n';
    // 오름차순 출력
    for(int i=0; i<6; i++)
        q2.push(vect[i]);
    for(int i=0; i<6; i++)
    {
        cout << q2.top() << ' ';
        q2.pop();
    }
    
    return 0;
}

두개씩 더한 값을 계속해서 더해갈 때 가장 큰 수

ex)

1, 2, 3, 4가 있을 때 4+3 = 7 

7+2 = 9

9+1 = 10

7+9+10 = 26으로 가장 크다

#include <iostream>
#include <queue>
using namespace std;

priority_queue<int> q;
int main()
{
    int num;
    for(int i=0; i<4; i++)
    {
        cin >> num;
        q.push(num);
    }
    int real_sum = 0, sum = 0;
    while(q.size() > 1)
    {
        sum = 0;
        for(int i=0; i<2; i++)
        {
            sum += q.top();
            q.pop();
        }
        q.push(sum);
        real_sum += sum;
    }
    cout << real_sum;
    return 0;
}

다중 조건에서 힙 사용법

operator< 활용하기

#include <iostream>
#include <queue>
using namespace std;
struct Node
{
    int n;
    char a;
};
priority_queue<Node> q;

bool operator<(Node p1, Node p2)
{
    if(p2.n < p1.n) return true;
    if(p2.n > p1.n) return false;
    
    return p2.a < p1.a;
};
int main()
{
    q.push({3, 'A'});
    q.push({4, 'B'});
    q.push({2, 'C'});
    q.push({2, 'A'});
    q.push({3, 'Q'});
    
    for(int i=0; i<5; i++)
    {
        cout << q.top().a << ' ' << q.top().n << '\n';
        q.pop();
    }
    return 0;
}