잡블로그 :: 잡블로그

336x280(권장), 300x250(권장), 250x250, 200x200 크기의 광고 코드만 넣을 수 있습니다.

비교정렬로서 이진트리구조를 이용한 정렬방법이다.

가장 위에 위치한 루트 값이 정렬조건에서 가장 우선순위가 높은 값이 위치한다.
항상 부모의 값은 자식의 값보다 정렬조건에서 우선순위가 높다.

이렇게 되면

위와 같이 힙에 값이 들어있다고 하자. 그러면 1에 위치한 값은 정렬조건에서 우선순위가 가장 높은 값이 있어야 한다.

그리고 2의 값은 아래 위치한 노드들의 값(4)보다 우선순위가 높은 값이 위치해있어야 한다.

3의 값 또한 서브트리 값들(5)보다 우선순위가 높은 값이 위치해있어야 한다.

여기서 만들어야 하는 것은 2가지 경우이다.

힙에 값을 넣었을 때
힙에서 값을 빼내었을 때

1번의 경우, 힙에 값을 넣게 되면 위 그림에서 6번 노드가 새로 추가 되었다. 가장 마지막에 값을 위치시키고, 바로 위의 부모와 비교를 하여 6번의 값이 우선순위가 높은 경우에 부모의 값과 바꿔주고, 과정을 반복한다. 아닌 경우 과정을 멈춘다.

2번의 경우, 힙에서 값을 꺼낸다. 그러면 1번 노드(루트)를 꺼내게 된다. 그리고 루트와 마지막에 위치한 노드를 변경한다.

그리고 6번 노드의 자식인 2번과 3번노드를 비교하여 우선순위가 높은 노드와 변경해준다. 이때 2번과 3번을 비교하여 더 우선순위가 높은 값을 올려준다.

만약 값이 더이상 없는 경우 과정을 멈춘다.

이렇게 정렬하고 싶은 데이터를 모두 넣고 차례대로 꺼내어 배열에 순서대로 넣어주게 되면 정렬을 할 수 있다.

최소힙구현 코드를 참고하면 된다.

http://wondy1128.tistory.com/211?category=679868

저작자표시

'PSNote > 알고리즘정리해봊' 카테고리의 다른 글

기수정렬(Radix sort) (0)	2017.12.05
삽입정렬(Insertion sort) (0)	2017.12.02
선택정렬(Selection Sort) (0)	2017.11.19
버블정렬(Bubble Sort) (0)	2017.11.18
네트워크플로우, 에드몬드 카프(Edmonds-Karp) 알고리즘 (0)	2017.11.15

336x280(권장), 300x250(권장), 250x250, 200x200 크기의 광고 코드만 넣을 수 있습니다.

벡터 내에

full
empty
size
clear
push_back
operator []

6가지를 코드로 작성해보았다. 아래는 코드이다.

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
template<class T>
struct my_vector {
    T* d;
    int sz;
    int cap;
    my_vector(int init_size = 32) {
        sz = 0;
        cap = init_size;
        d = new T[cap];
    }
    bool full() { return sz == cap; }
    bool empty() { return !sz; }
    int size() { return sz; }
    void clear() { sz = 0; }
    T operator [] (int i) { return d[i]; }
    void push_back(T input) {
        if (full()) {
            T* tmp = T[cap << 1];
            for (register int i = 0; i < sz; ++i) {
                tmp[i] = d[i];
            }
            delete[] d;
            d = tmp;
            cap <<= 1;
        }
        d[sz++] = input;
    }
};
Colored by Color Scripter
cs

저작자표시

'PSNote > C++STL' 카테고리의 다른 글

[C++STL]binary_search (0)	2017.07.20

336x280(권장), 300x250(권장), 250x250, 200x200 크기의 광고 코드만 넣을 수 있습니다.

https://www.acmicpc.net/problem/11286

[문제설명]

cmd 입력으로 0이 아닌 입력이 들어오면 원소를 넣는다.

cmd 입력이 0 인 경우 힙의 가장 위에 있는 원소를 출력한다.

이때 힙에 가장 위에 위치는 원소는 절대값으로 가장 작고, 동일한 절대값이 있는 경우 가장 작은 값을 출력한다.

이때 힙이 비어있는 경우 0을 출력한다.

[문제풀이]

힙을 구현하면 된다.

이때 minheap을 구현하기 위해서 node라는 구조체를 선언하고 operator < 로 비교하게 하여 조건을 처리하여 풀이할 수 있다.

[C++ source code]

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
100
101
102
103
104
105
106
107
#include<iostream>
#define din(a) scanf("%d", &a)
 
inline int my_abs(int a) {
    return (a > 0) ? a : -a;
}
 
struct node {
    int d;
    node() { d = 0; }
    node(int i):d(i){}
    bool operator < (node t) {
        if (my_abs(d) == my_abs(t.d)) {
            if (d < t.d) return true;
            return false;
        }
        else if (my_abs(d) < my_abs(t.d)) {
            return true;
        }
        return false;
    }
};
 
template<typename T>
struct heap {
    T d[1 << 18];
    int e;
    heap() {
        e = 0;
    }
    bool empty() {     return !e; }
    bool full() { return (e + 1) == (1 << 18); }
    void push(T input) {
        if (full()) return;
        d[++e] = input;
        int cur = e;
        while ((cur / 2) > 0) {
            if (d[cur] < d[cur / 2]) {
                swap(d[cur], d[cur / 2]);
            }
            else {
                break;
            }
            cur /= 2;
        }
    }
    void pop() {
        if (empty()) return;
        d[1] = d[e];
        e--;
        //d[e--].clear();
        int cur = 1;
        while (cur * 2 <= e) {
            int child;
            if (cur * 2 + 1 > e) {
                child = cur * 2;
            }
            else {
                if (d[cur * 2] < d[cur * 2 + 1]) {
                    child = 2 * cur;
                }
                else {
                    child = 2 * cur + 1;
                }
            }
 
            if (d[cur] < d[child]) {
                break;
            }
            swap(d[cur], d[child]);
            cur = child;
        }
    }
    T top() {
        T ret;
        if (empty()) return ret;
        return d[1];
    }
    void swap(T& a, T& b) {
        T t = a;
        a = b;
        b = t;
    }
};
 
heap<node> PQ;
int main() {
    int OP;
    din(OP);
    for (register int i = 0; i < OP; ++i) {
        int cmd;
        din(cmd);
         if (cmd == 0) {
            if (PQ.empty()) {
                puts("0");
            }
            else {
                printf("%d\n", PQ.top().d);
                PQ.pop();
            }
        }
        else {
            PQ.push(node(cmd));
        }
    }
    return 0;
}
Colored by Color Scripter
cs

저작자표시

'PSNote > Problem Solving' 카테고리의 다른 글

[BOJ-10825]국영수 (0)	2019.01.20
[BOJ-11048]이동하기 (0)	2018.07.08
[BOJ-1325]효율적인해킹 (0)	2018.05.26
[BOJ-6603]로또 (0)	2018.05.25
[BOJ-2470]두용액 (0)	2018.05.25

336x280(권장), 300x250(권장), 250x250, 200x200 크기의 광고 코드만 넣을 수 있습니다.

https://www.acmicpc.net/problem/1325

컴퓨터 대수 그리고 컴퓨터들의 관계 수가 주어지고

관계 수 만큼 A B 가 주어진다.

A가 B를 신뢰하면 B를 해킹할 때, A도 해킹이 가능하다.

이때 최대로 해킹이 가능한 컴퓨터를 보여주면 된다.

여러 대일 경우 오름차순으로 보여준다.

[문제풀이]

[C++ source code]

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include<iostream>
 
struct mvector {
    int *data;
    int capacity, sz;
 
    mvector(int init_size = 64) {
        data = new int[init_size];
        capacity = init_size;
        sz = 0;
        for (int i = 0; i < init_size; ++i) data[i] = 0;
    }
    void push_back(int input) {
        if (full()) {
            int *temp = new int[capacity];
            for (int i = 0; i < sz; ++i) {
                temp[i] = data[i];
            }
            delete[] data;
            capacity <<= 1;
            data = new int[capacity];
            for (int i = 0; i < sz; ++i) {
                data[i] = temp[i];
            }
            delete[] temp;
        }
        data[sz++] = input;
    }
    int operator[](int i) { return data[i]; }
    int size() { return sz; }
    bool empty() { return !sz; }
    bool full() { return capacity == sz; }
};
 
struct queue {
    int d[1 << 18];
    int s, e;
    queue() { s = e = 0; }
    bool empty() { return s == e; }
    bool full() { return (e + 1) % (1 << 18) == s; }
    void push(int i) {
        if (full()) return;
        d[e++] = i;
        e %= (1 << 18);
    }
    void pop() {
        if (empty()) return;
        s = (s + 1) % (1 << 18);
    }
    int front() {
        if (empty()) return -1;
        return d[s];
    }
};
 
struct minheap {
    int d[1 << 18];
    int e;
    minheap() { e = 0; }
    bool empty() { return e == 0; }
    bool full() { return (e + 1) == (1 << 18); }
    void push(int i) {
        if (full()) return;
        d[++e] = i;
        int cur = e;
        while (cur / 2 > 0) {
            if (d[cur] < d[cur / 2]) swap(d[cur], d[cur / 2]);
            else break;
            cur = cur / 2;
        }
    }
    void pop() {
        if (empty()) return;
        d[1] = d[e];
        e--;
        int cur = 1;
        while (2 * cur <= e) {
            int child;
            if (2 * cur + 1 > e) {
                child = 2 * cur;
            }
            else {
                child = (d[2 * cur] < d[2 * cur + 1]) ? 2 * cur : 2 * cur + 1;
            }
 
            if (d[cur] < d[child]) break;
            swap(d[cur], d[child]);
            cur = child;
        }
    }
    int top() {
        if (empty()) return -1;
        return d[1];
    }
    void swap(int& a, int& b) {
        int t = a;
        a = b;
        b = t;
    }
    void clear() { e = 0; }
};
 
mvector com[10101];
int vis[10101];
queue Q;
minheap ansPQ;
int main() {
    int N, M;
    scanf("%d%d", &N, &M);
    for (int i = 0; i < M; ++i) {
        int a, b;
        scanf("%d%d", &a, &b);
        // if b is hacking, a-hacking is possible;
        com[b].push_back(a);
    }
    int mx = 0;
    for (int i = 1; i <= N; ++i) {
        for (int vi = 1; vi <= N; ++vi) vis[vi] = false; // init
        int tmp_mx = 0;
        Q.push(i);
        vis[i] = true;
        while (!Q.empty()) {
            int h = Q.front();
            Q.pop();
            tmp_mx++;
            for (int hi = 0; hi < com[h].sz; ++hi) {
                int t = com[h][hi];
                if (vis[t]) continue;
                vis[t] = true;
                Q.push(t);
            }
        }
        if (mx < tmp_mx) {
            mx = tmp_mx;
            ansPQ.clear();
            ansPQ.push(i);
        }
        else if (mx == tmp_mx) {
            ansPQ.push(i);
        }
    }
 
    while (!ansPQ.empty()) {
        printf("%d ", ansPQ.top());
        ansPQ.pop();
    }
    puts("");
    return 0;
}
Colored by Color Scripter
cs

저작자표시

'PSNote > Problem Solving' 카테고리의 다른 글

[BOJ-11048]이동하기 (0)	2018.07.08
[BOJ-11286]절대값 힙 (0)	2018.06.07
[BOJ-6603]로또 (0)	2018.05.25
[BOJ-2470]두용액 (0)	2018.05.25
[BOJ-10974]모든순열 (0)	2017.11.22

336x280(권장), 300x250(권장), 250x250, 200x200 크기의 광고 코드만 넣을 수 있습니다.

https://www.acmicpc.net/problem/6603

입력된 수의 갯수 중 6개의 집합들을 출력하는 문제

[문제풀이]

[C++ source code]

저작자표시

'PSNote > Problem Solving' 카테고리의 다른 글

[BOJ-11286]절대값 힙 (0)	2018.06.07
[BOJ-1325]효율적인해킹 (0)	2018.05.26
[BOJ-2470]두용액 (0)	2018.05.25
[BOJ-10974]모든순열 (0)	2017.11.22
[BOJ-6086]최대유량 (0)	2017.11.18

잡블로그

힙 정렬(Heap sort)

'PSNote > 알고리즘정리해봊' 카테고리의 다른 글

[C++]vector구현

'PSNote > C++STL' 카테고리의 다른 글

[BOJ-11286]절대값 힙

'PSNote > Problem Solving' 카테고리의 다른 글

[BOJ-1325]효율적인해킹

'PSNote > Problem Solving' 카테고리의 다른 글

[BOJ-6603]로또

'PSNote > Problem Solving' 카테고리의 다른 글

+ Recent posts

티스토리툴바