'Tech Stack/data structures'에 해당되는 글 11건

 [ 1 ]  [ 2 ] 
Tech Stack/data structures

세그먼트 트리 ( 구간 최소값 preprocessing )

세그먼트 트리는 모든 부분 구간에서의 값을 미리 계산해둔 트리이다. 따라서 어느 특정 구간의 계산값을 구하고자 할 때, 트리의 높이 정도의 값들만 가지고 최종 값을 도출할 수 있을 때 쓴다.


여기서는 최솟값 세그먼트 트리여서 트리에 최솟값만 저장하면 되지만, 필요하면 pair 등을 사용해서 최소값 2개의 값이나 그 구간의 최대반복수 등을 기록해서 재귀단계별로 프로세싱 해도 되겠다.


init 재귀의 시간 복잡도 : 2*n+2 번의 init을 호출하고 각각은 O(1) 이므로 전체는 O(N)

findmin의 시간 복잡도 : 바이너리 서치와 같은 O(logN)



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
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
int init(vector<int> & data, vector<int> & segtree, int high, int low, int node) {
    // base case
    if (low == high) {
        segtree[node] = data[low];
        return data[low];
    }
    // general case
    int mid = (low + high) / 2;
    int left = init(data, segtree, mid, low, 2 * node + 1);
    int right = init(data, segtree, high, mid + 1, 2 * node + 2);
    segtree[node] = min(left, right);
    return segtree[node];
}
 
void preprocess(vector<int> & data, vector<int> & segtree) {
    segtree.resize(data.size() * 4);
    for (int i = 0; i < segtree.size(); i++) {
        segtree[i] = INT_MAX;
    }
    init(data, segtree, data.size()-1,0, 0);
}
 
int findmin(vector<int> & segtree, int low, int high, int clow, int chigh, int curr) {
    // base case
    if (low == clow && high == chigh) return segtree[curr];
    // general case
    int mid = (clow + chigh) / 2;
    if (low <= mid&& high >= mid + 1) {
        return min(findmin(segtree, low, mid, clow, mid, curr * 2 + 1), findmin(segtree, mid + 1, high, mid + 1, chigh, curr * 2 + 2));
    }
    else if (high <= mid) {
        return findmin(segtree, low, high, clow, mid, curr * 2 + 1);
    }
    else {
        return findmin(segtree, low, high, mid + 1, chigh, curr * 2 + 2);
    }
}
 
int findmin2(vector<int> & segtree, int low, int high, int m) {
    return findmin(segtree, low, high, 0, m-1, 0);
}
 
int main() {
    vector<int> v1 = { 1,3,2,7,9,11 };
    vector<int> segtree;
    preprocess(v1, segtree);
    for (int x : segtree) cout << x << " ";
    cout << endl;
    cout << findmin2(segtree, 1, 5, v1.size()) << endl;
    while(1){}
    return 0;
}
cs


'Tech Stack > data structures' 카테고리의 다른 글

세그먼트 트리 ( 구간 최소값 preprocessing )  (0) 2018.04.17
Heap 구현  (0) 2018.04.15
Binary Heaps  (0) 2018.04.15
priority queue(max heap)  (0) 2018.03.25
when to use STL data structures(multimap)  (0) 2018.03.25
data structures  (0) 2018.03.24
Tech Stack/data structures

Heap 구현

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
#include "stdafx.h"
#include <vector>
#include <iostream>
 
using namespace std;
 
void swap(int & a, int & b) {
    int tmp = a;
    a = b;
    b = tmp;
}
 
int hleft(vector<int>&heap, int i) {
    return (i * 2 + 1 < heap.size()) ? 2 * i+1 : -1;
}
 
int hright(vector<int>&heap, int i) {
    return (i * 2 + 2 < heap.size()) ? 2 * i + 2 : -1;
}
 
int parent(vector<int>&heap, int i) {
    return i / 2;
}
 
void maxheapify(vector<int>&heap,int i) {
    cout << "hpfy at " << i << endl;
    if (i > heap.size() - 1) return;
    int left = hleft(heap, i);
    int right = hright(heap, i);
    int change = i;
    if (left != -1 && heap[left] > heap[i]) {
        change = left;
    }
    if (right != -1 && heap[right] > heap[change]) {
        change = right;
    }
    if (change != i) {
        swap(heap[i], heap[change]);
        maxheapify(heap, change);
    }
}
 
void buildheap(vector<int>&heap) {
    for (int i = heap.size() / 2; i >= 0; i--) {
        for (int x : heap) cout << x << " ";
        cout << endl;
        maxheapify(heap, i);
    }
}
 
void insert(vector<int> & heap, int k) {
    heap.push_back(k);
    int curr = heap.size() - 1;
    while (curr != 0 && heap[parent(heap, curr)] < heap[curr]) {
        swap(heap[parent(heap, curr)], heap[curr]);
        curr = parent(heap, curr);
    }
}
 
int pop(vector<int> & heap) {
    if (heap.size() == 0) return -9999;
    int ret = heap[0];
    heap[0] = heap[heap.size() - 1];
    heap.pop_back();
    maxheapify(heap, 0);
    return ret;
}
 
int main() {
    vector<int> sam = { 5,4,7,18,4,7,6,4,2,13,14,1 };
    buildheap(sam);
    for (int x : sam) cout << x << " ";
    cout <<endl << pop(sam) << endl;
    for (int x : sam) cout << x << " ";
    cout << endl;
    insert(sam, 9);
    for (int x : sam) cout << x << " ";
    cout << endl;
    while(1){}
    return 0;
}
cs


'Tech Stack > data structures' 카테고리의 다른 글

세그먼트 트리 ( 구간 최소값 preprocessing )  (0) 2018.04.17
Heap 구현  (0) 2018.04.15
Binary Heaps  (0) 2018.04.15
priority queue(max heap)  (0) 2018.03.25
when to use STL data structures(multimap)  (0) 2018.03.25
data structures  (0) 2018.03.24
Tech Stack/data structures

Binary Heaps

Min / Max heap : binary tree인데, 제약조건은 Min heap의 경우 부모가 더 작아야 하고, Max heap의 경우 부모가 더 커야 한다.


어레이 표현 방법

0에 최대/최소가 있고

층별 순회를 한다고 생각하면 편하다.


i 에 대해

부모 : i/2

자식1 : 2i+1

자식2 : 2i+2



'Tech Stack > data structures' 카테고리의 다른 글

세그먼트 트리 ( 구간 최소값 preprocessing )  (0) 2018.04.17
Heap 구현  (0) 2018.04.15
Binary Heaps  (0) 2018.04.15
priority queue(max heap)  (0) 2018.03.25
when to use STL data structures(multimap)  (0) 2018.03.25
data structures  (0) 2018.03.24
Tech Stack/data structures

priority queue(max heap)

max heap의 전체 원소를 최종적으로 순회할 필요가 있을때 사용


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
    vector<int> v1 = { 5,4,3,6,7,6,5,4,65,76,12 };
    make_heap(v1.begin(), v1.end());
    cout << v1.front() << endl;
    v1.push_back(99);
    push_heap(v1.begin(), v1.end());
    cout << v1[0<< endl;
    for (int i : v1) {
        cout << i << " ";
    }
    cout << endl;
    pop_heap(v1.begin(), v1.end());
    pop_heap(v1.begin(), v1.end()-1);
    pop_heap(v1.begin(), v1.end()-2);
    cout << v1.front() << endl;
    for (int i : v1) {
        cout << i << " ";
    }
    cout << endl;
cs


min/max heap with priority queue ( 전체 원소 순회 불가능, 하려면 하나씩 pop 해가면서

nlogn

) >> 진짜push,pop,peek만 필요한 경우에 적절


// 헤더 functional에 있다.

// priority queue는 queue 헤더에 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
priority_queue<pair<doubleint>,vector<pair<double,int>>,greater<pair<double,int>>> given;
// 위의 방법이 min heap   
 priority_queue<intvector<int>, greater<int>>q2;
    // priority queue는 모든 변수 iterator 불가능.. 애초에 iterator가 없음.. 문젠데
    given.push(pair<doubleint>(1.343));
    given.push(pair<doubleint>(4.432));
    given.push(pair<doubleint>(0.931));
    cout << given.top().first <<" " << given.top().second << endl;
    while (1) {}

cs




minheap with priority queue ( 비교자를 operator overloading )

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
#include <bits/stdc++.h>
using namespace std;
 
// User defined class, Point
class Point
{
   int x;
   int y;
public:
   Point(int _x, int _y)
   {
      x = _x;
      y = _y;
   }
   int getX() const { return x; }
   int getY() const { return y; }
};
 
// To compare two points
class myComparator
{
public:
    int operator() (const Point& p1, const Point& p2)
    {
        return p1.getX() > p2.getX();
    }
};
 
// Driver code
int main ()
{
    // Creates a Min heap of points (order by x coordinate)
    priority_queue <Point, vector<Point>, myComparator > pq;
 
    // Insert points into the min heap
    pq.push(Point(10, 2));
    pq.push(Point(2, 1));
    pq.push(Point(1, 5));
 
    // One by one extract items from min heap
    while (pq.empty() == false)
    {
        Point p = pq.top();
        cout << "(" << p.getX() << ", " << p.getY() << ")";
        cout << endl;
        pq.pop();
    }
 
    return 0;
}
cs


'Tech Stack > data structures' 카테고리의 다른 글

Heap 구현  (0) 2018.04.15
Binary Heaps  (0) 2018.04.15
priority queue(max heap)  (0) 2018.03.25
when to use STL data structures(multimap)  (0) 2018.03.25
data structures  (0) 2018.03.24
Binary Search Tree  (0) 2018.03.24
Tech Stack/data structures

when to use STL data structures(multimap)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int main() {
    multimap<intint> test;
    test.insert(pair<intint>(34));
    test.insert(pair<intint>(24));
    test.insert(pair<intint>(14));
    test.insert(pair<intint>(11));
    test.insert(pair<intint>(12));
    // 두번째 인자로는 정렬안함
    for (multimap<intint>::iterator it = test.begin(); it != test.end(); it++) {
        cout << (*it).first << " " << (*it).second << endl;
    }
    while(1){ }
    map<intint> namemap;
    namemap.insert(pair<intint>(23));
    namemap.insert(map<intint>::value_type(43));
    namemap[5= 3;
    namemap[5= 2// 후자로 바꿔버리네.
    for (map<intint>::iterator it = namemap.begin(); it != namemap.end(); it++) {
        cout << (*it).first << " " << it->second << endl;
    }
    while (1) {}
    return 0;
}
 
cs



Array, vector : 

insert : O(n), delete : O(n) search O(1)

push_back : O(1)

vector을 만들고 sort까지 하려면 N^2logN


사용처 : read가 많은 경우


list :

insert : O(1), delete :  O(1), search O(n)

find min : O(N)


사용처 : I/O가 많은 경우


tree(BST):

insert: O(logN), delete : O(logN), search : O(logN)

make : O(N)

N개의 입력을 BST로 만들려면 NlogN


사용처 : I/O가 발생하면서 지속적으로 sort의 필요가 있는 경우

STL : map, set, multimap, multiset


heap

insert : O(logN), delete: O(logN), search : O(logN)

make : O(N)

find min/max : O(1)


사용처 : I/O가 발생하면서 지속적으로 최대/최소값을 트래킹할 필요가 있는 경우(sort는 안된다), 변형되어도 자동으로 최대최소값이 로딩됨

STL : priority_queue(max_heap)


hash table:

insert O(1) delete O(1) search O(1)

find min/max : O(N)


사용처 : 빠르게 I/O를 하고싶은 경우, 중복검사, 존재성검사

STL : unordered_map, unordered_set



있는 array를 sort하는 경우 >> NlogN

힙 build >> O(N) but unsorted. 하나씩 제거해가며 최대값을 하나씩 넣는 경우

여기서 하나씩 제거해가며 뺴야 되므로 logN 평균.

total : 실익 없음

BST build >> O(NlogN) 근데 결국 그 BST를 쓰려면 최소값부터 쭉 불러내야 하는데

그게 또 O(N) 뭐 전체 복잡도는 O(NlogN) 이지만..

사실상 정렬된 리스트를 유지하면서 움직이는거랑 무슨 차인지 모르겠지만

구현의 편의성이라고 하자 STL에 있으니까 ㅋㅋ



'Tech Stack > data structures' 카테고리의 다른 글

Binary Heaps  (0) 2018.04.15
priority queue(max heap)  (0) 2018.03.25
when to use STL data structures(multimap)  (0) 2018.03.25
data structures  (0) 2018.03.24
Binary Search Tree  (0) 2018.03.24
doubly linked list  (0) 2018.03.24
Tech Stack/data structures

data structures

array

linked list

queue, stack


tree

BST

balanced BST(red black tree)

heap

min heap, max heap

priority queue

trie


hash tables


graphs

'Tech Stack > data structures' 카테고리의 다른 글

priority queue(max heap)  (0) 2018.03.25
when to use STL data structures(multimap)  (0) 2018.03.25
data structures  (0) 2018.03.24
Binary Search Tree  (0) 2018.03.24
doubly linked list  (0) 2018.03.24
delete duplicate letters in list  (0) 2018.03.23
Tech Stack/data structures

Binary Search Tree

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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
#include "stdafx.h"
#include <iostream>
 
using namespace std;
 
struct treenode {
    int data;
    treenode * parent;
    treenode * left;
    treenode * right;
};
 
class BST {
private:
    treenode *mocknode;
public:
    treenode * root;
    BST() {
        root = NULL;
    }
    void add(int d);
    void remove(int d);
    void preorder(treenode * root);
    void postorder(treenode * root);
    void inorder(treenode *root);
    void preorder(treenode * root, int count);
};
 
void BST::add(int d) {
    if (root == NULL) {
        root = new treenode;
        mocknode = new treenode;
        root->data = d;
        root->parent = mocknode;
        root->left = NULL;
        root->right = NULL;
        mocknode->data = d;
        mocknode->right = root;
        mocknode->left = NULL;
        cout << "successfully added " << d << endl;
        return;
    }
    treenode * tmp = root;
    treenode * tracker = root;
    while (tmp != NULL) {
        if (d >= tmp->data) {
            tracker = tmp;
            tmp = tmp->right;
        }else{
            tracker = tmp;
            tmp = tmp->left;
        }
    }
    tmp = new treenode;
    if (tracker->data <= d) {
        tmp->data = d;
        tmp->parent = tracker;
        tmp->right = NULL;
        tmp->left = NULL;
        tracker->right = tmp;
    }
    else {
        tmp->data = d;
        tmp->parent = tracker;
        tmp->right = NULL; tmp->left = NULL;
        tracker->left = tmp;
    }
    cout << "successfully added " << d << endl;
}
 
void BST::remove(int d) {
    treenode * tmp = root;
    while (tmp!=NULL && tmp->data != d) {
        if (tmp->data >= d) {
            tmp = tmp->left;
        }
        else {
            tmp = tmp->right;
        }
    }
    if (tmp == NULL) {
        cout << "no such element" << endl;
    }
    else {
        if (tmp->left == NULL && tmp->right == NULL) {
            if (tmp->parent->data > tmp->data) {
                tmp = tmp->parent;
                tmp->left = NULL;
            }
            else {
                tmp = tmp->parent;
                tmp->right = NULL;
            }
        }
        else if (tmp->left != NULL && tmp->right == NULL) {
            tmp->left->parent = tmp->parent;
            if (tmp->data >= tmp->parent->data) {
                tmp->parent->right = tmp->left;
            }
            else {
                tmp->parent->left = tmp->left;
            }
        }
        else if (tmp->left == NULL && tmp->right != NULL) {
            tmp->right->parent = tmp->parent;
            if (tmp->data >= tmp->parent->data) {
                tmp->parent->right = tmp->right;
            }
            else {
                tmp->parent->left = tmp->right;
            }
        }
        else {
            treenode *finder = tmp;
            while (!(finder->right == NULL)) {
                if (finder == tmp) {
                    finder = tmp->left;
                }
                else {
                    finder = finder->right;
                }
            }
            if (finder->left == NULL) {
                if (tmp->parent->data <= tmp->data) {
                    tmp->parent->right = finder;
                }
                else {
                    tmp->parent->left = finder;
                }
                finder->parent = tmp->parent;
                finder->left = tmp->left;
                tmp->left->parent = finder;
                finder->right = tmp->right;
                tmp->right->parent = finder;
            }
            else {
                if (tmp->left == finder) {
                    if (tmp->parent-> data <= tmp->data) {
                        tmp->parent->right = finder;
                    }
                    else {
                        tmp->parent->left = finder;
                    }
                    finder->parent = tmp->parent;
                    tmp->right->parent = finder;
                    finder->right = tmp->right;
                }
                else {
                    finder->parent->right = finder->left;
                    finder->left->parent = finder->parent;
                    if (tmp->parent->data <= tmp->data) {
                        tmp->parent->right = finder;
                    }
                    else {
                        tmp->parent->left = finder;
                    }
                    finder->parent = tmp->parent;
                    finder->left = tmp->left;
                    finder->right = tmp->right;
                    tmp->right->parent = finder;
                    tmp->left->parent = finder;
                }
            }
        }
        root = mocknode->right;
    }
}
 
void BST::inorder(treenode * root) {
    if (root == NULL) {
        return;
    }
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}
 
void BST::preorder(treenode * root) {
    if (root == NULL) {
        return;
    }
    cout << root->data << " ";
    preorder(root->left);
    preorder(root->right);
}
 
void BST::preorder(treenode * root,int count) {
    if (root == NULL) {
        return;
    }
    for (int i = 0; i < count; i++) {
        cout << " ";
    }
    cout << root->data << endl;
    preorder(root->left,count+1);
    preorder(root->right,count+1);
}
 
void BST::postorder(treenode * root) {
    if (root == NULL) {
        return;
    }
    postorder(root->left);
    postorder(root->right);
    cout << root->data << " " ;
}
 
int main() {
    BST tree;
    tree.add(5);
    tree.add(4);
    tree.add(8);
    tree.add(9);
    tree.add(1);
    tree.add(1);
    tree.add(1);
    tree.add(1);
    tree.add(7);
    tree.add(6);
    tree.add(10);
    tree.add(11);
    tree.remove(5);
    tree.inorder(tree.root); cout << endl;
    tree.preorder(tree.root, 0);
    while (1) {}
    return 0;
}
cs


'Tech Stack > data structures' 카테고리의 다른 글

when to use STL data structures(multimap)  (0) 2018.03.25
data structures  (0) 2018.03.24
Binary Search Tree  (0) 2018.03.24
doubly linked list  (0) 2018.03.24
delete duplicate letters in list  (0) 2018.03.23
linked list  (0) 2018.03.19
Tech Stack/data structures

doubly linked list

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
#include "stdafx.h"
#include <iostream>
 
using namespace std;
 
struct listnode {
    int data;
    listnode * prev;
    listnode * next;
};
 
class list {
private:
    listnode * head;
    listnode * tail;
public:
    list() {
        head = NULL;
        tail = NULL;
    }
    void append(int d);
    void remove();
    void print();
};
 
void list::append(int d) {
    if (head == NULL) {
        listnode * tmp2 = new listnode;
        tmp2->data = d;
        tmp2->prev = NULL;
        tmp2->next = NULL;
        head = tmp2;
        tail = tmp2;
        return;
    }
    listnode * tmp = new listnode;
    tmp->data = d;
    tmp->prev = tail;
    tmp->next = NULL;
    tail->next = tmp;
    tail = tail->next;
}
 
void list::remove() {
    if (tail == head) {
        return;
    }
    tail = tail->prev;
    tail->next = NULL;
}
 
void list::print() {
    listnode * tmp = head;
    while (tmp != NULL) {
        cout << tmp->data << " ";
        tmp = tmp->next;
    }
    cout << endl;
}
 
int main() {
    list test;
    test.append(1);
    test.append(2);
    test.append(3);
    test.remove();
    test.print();
    while(1){ }
    return 0;
}
cs


'Tech Stack > data structures' 카테고리의 다른 글

data structures  (0) 2018.03.24
Binary Search Tree  (0) 2018.03.24
doubly linked list  (0) 2018.03.24
delete duplicate letters in list  (0) 2018.03.23
linked list  (0) 2018.03.19
circular queue  (0) 2018.03.18
Tech Stack/data structures

delete duplicate letters in list

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
//임시 버퍼가 허용되면 set을 사용해서 해결할 수 있겠다.
 
#include "stdafx.h"
#include <iostream>
#include <list>
#include <unordered_set>
#include <cstdlib>
#include <ctime>
#include <set>
 
using namespace std;
 
int main() {
    srand(time(NULL));
    // 순서를 유지해야 하나요 ? >> 네
    // 첫 번째로 나타나는 원소만 남길까요? >> 네
    // 리스트의 데이터형은 char로 해도 괜찮나요? >> 네
    // 리스트가 STL list로 주어져 있다고 가정해도 되나요? >> 네
    list<char> data;
    for (int i = 0; i < 100; i++) {
        data.push_back(rand() % 26 + 'a');
    }
    list<char>::iterator it;
    for (it = data.begin(); it != data.end(); it++) {
        cout << *it << " ";
    }
    cout << endl<<endl;
    set<char> buffer;
/*    
    for (it = data.begin(); it != data.end(); it++) {
        if (buffer.find(*it) == buffer.end()) {
            buffer.insert(*it);
        }
        else {
            list<char>::iterator tmp = it;
            advance(tmp, -1);
            data.erase(it);
//data.erase(it--)으로 해결가능..
            it = tmp;
        }
    }
*/
    for (int i = 0; i < data.size(); i++) {
        it = data.begin();
        advance(it, i);
        if (buffer.find(*it) == buffer.end()) {
            buffer.insert(*it);
        }
        else {
            data.erase(it);
            i--;
        }
    }
    for (it = data.begin(); it != data.end(); it++) {
        cout << *it << " ";
    }
    cout << endl << endl;
    while(1){}
    return 0;
}

cs


without buffers
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
void removeduplicate(list<char> & data) {
    // 이중 search O(N^2) 알고리즘 가능하다.
    // 26 letters라는 사실을 이용할 수 있나? >> 일단 별 방법이 안 보인다
    // 오!! O(N) 방법이 있다.. a ~ z까지 돌면서 지우는 방법..
    // 버퍼를 쓸 수 없다는게 단일 변수도 사용 불가능한지?
    list<char>::iterator it;
    for (int i = 0; i < 26; i++) {
        bool done = false;
        for (int j = 0; j < data.size(); j++) {
            it = data.begin();
            advance(it, j);
            if (*it == ('a' + i)) {
                if (done == false) {
                    done = true;
                }
                else {
                    data.erase(it);
                    j--;
                }
            }
        }
    }
}
 
void removeduplicate2(list<char> & data) {
    list<char>::iterator it;
    for (it = data.begin(); it != data.end(); it++) {
        for (list<char>::iterator it2 = data.begin(); it2 != it; it2++) {
            if (*it2 == *it) {
                //list<char>::iterator tmp = it;
                //it--;
                data.erase(it--); // it 이터레이터를 삭제하기 전에 연산을 해주나?
                break;
            }
        }
    }
}
 
void removeseconds(list<char> &data) {
    bool tg = false;
    for (list<char>::iterator it = data.begin(); it != data.end(); it++) {
        if (tg == false) {
            tg = true;
        }
        else {
            data.erase(it--);
            tg = false;
        }
    }
}
cs


'Tech Stack > data structures' 카테고리의 다른 글

data structures  (0) 2018.03.24
Binary Search Tree  (0) 2018.03.24
doubly linked list  (0) 2018.03.24
delete duplicate letters in list  (0) 2018.03.23
linked list  (0) 2018.03.19
circular queue  (0) 2018.03.18
Tech Stack/data structures

linked list

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
#include "stdafx.h"
#include <cstdio>
#include <iostream>
 
using namespace std;
 
template<class T>
class node {
public:
    T data;
    node * next;
    node(T da);
};
 
template<class T>
node<T>::node(T da) {
    data = da;
    next = NULL;
}
 
template<class T>
class linkedlist {
private:
    node<T> * head;
    int size;
public:
    linkedlist();
    void append(T da);
    T remove();
    void print();
};
 
template<class T>
linkedlist<T>::linkedlist() {
    head = NULL;
    size = 0;
}
 
template<class T>
void linkedlist<T>::append(T da){
    if (size == 0) {
        node<T> * tmp = new node<T>(da);
        head = tmp;
        size++;
        return;
    }
    node<T> * curr = head;
    while (curr->next != NULL) {
        curr = curr->next;
    }
    node<T> *tmp = new node<T>(da);
    curr->next = tmp;
    size++;
    return;
}
 
template<class T>
T linkedlist<T>::remove() {
    if (size == 0) {
        printf("no elements to delete\n");
        return head->data;
    }
    if (size == 1) {
        head = NULL;
        size = 0;
    }
    node<T> * curr = head;
    for (int i = 0; i < size-2; i++) {
        curr = curr->next;
    }
    T ret = curr->next->data;
    curr->next = NULL;
    size--;
    return ret;
}
 
template<class T>
void linkedlist<T>::print() {
    if (size == 0) {
        printf("empty linkedlist\n");
        return;
    }
    else {
        node<T> * curr = head;
        while (1) {
            printf("%d ", curr->data);
            if (curr->next == NULL) {
                break;
            }
            curr = curr->next;
        }
        printf("\n");
    }
}
 
int main() {
    linkedlist<int> ll;
    ll.append(1);
    ll.append(2);
    ll.append(3);
    ll.remove();
    ll.print();
    while (1) {}
    return 0;
}
 
 
 
 
cs


'Tech Stack > data structures' 카테고리의 다른 글

data structures  (0) 2018.03.24
Binary Search Tree  (0) 2018.03.24
doubly linked list  (0) 2018.03.24
delete duplicate letters in list  (0) 2018.03.23
linked list  (0) 2018.03.19
circular queue  (0) 2018.03.18