'Data Structure' 카테고리의 글 목록

검색결과 리스트

Data Structure에 해당되는 글 4건

2019.02.13 Linked List 5
2019.02.10 Merge Sort
2019.01.22 Hash 3
2019.01.11 Heap 6

글

Linked List

Data Structure 2019. 2. 13. 23:00

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

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

#include <stdio.h>
#include <algorithm>
#include <list>
#include "Windows.h"
using namespace std;
 
struct NODE {
    int prev;
    int next;
    int val;
};
 
const int NODE_SIZE = 30000;
 
//TEST CMD
const int PUSH_BACK = 0;
const int PUSH_FRONT = 1;
const int INSERT = 2;
const int POP_BACK = 3;
const int POP_FRONT = 4;
const int ERASE = 5;
 
int test_cmd[NODE_SIZE][3];
 
struct MY_LIST {
    int HEAD = NODE_SIZE;
    int TAIL = NODE_SIZE + 1;
    int pos;
    NODE node[NODE_SIZE + 2];
 
    MY_LIST() {
        pos = 0;
        node[HEAD].next = TAIL;
        node[TAIL].prev = HEAD;
    }
 
    void push_back(int data) {
        int prev = node[TAIL].prev;
        int next = node[prev].next; // TAIL;
 
        node[pos].val = data;
 
        node[pos].prev = prev;
        node[prev].next = pos;
 
        node[pos].next = next;
        node[next].prev = pos;
        ++pos;
    }
 
    void push_front(int data) {
        int next = node[HEAD].next;
        int prev = node[next].prev; // HEAD
         
        node[pos].val = data;
 
        node[pos].prev = prev;
        node[prev].next = pos;
 
        node[pos].next = next;
        node[next].prev = pos;
        ++pos;
    }
 
    void insert(int p, int data) {
        int next = node[HEAD].next;
        for(int i = 0; i < p; ++i) {
            next = node[next].next;
        }
        int prev = node[next].prev;
     
        node[pos].val = data;
 
        node[pos].prev = prev;
        node[prev].next = pos;
 
        node[pos].next = next;
        node[next].prev = pos;
        ++pos;
    }
 
    void pop_back() {
        int target = node[TAIL].prev;
 
        int prev = node[target].prev;
        int next = node[target].next;
 
        node[prev].next = next;
        node[next].prev = prev;
    }
 
    void pop_front() {
        int target = node[HEAD].next;
 
        int prev = node[target].prev;
        int next = node[target].next;
 
        node[prev].next = next;
        node[next].prev = prev;
    }
 
    void erase(int p) {
        int target = node[HEAD].next;
        for (int i = 0; i < p; ++i) {
            target = node[target].next;
        }
        int prev = node[target].prev;
        int next = node[target].next;
 
        node[prev].next = next;
        node[next].prev = prev;
    }
};
 
MY_LIST my_list;
list<int> stl_list;
 
int main()
{
    // make test case..
    int cur_size = 0;
    for (int i = 0; i < NODE_SIZE; ++i) {
        if (i < NODE_SIZE / 3) {
            test_cmd[i][0] = rand() % 2;
        }
        else {
            test_cmd[i][0] = rand() % 6;
        }
 
        switch (test_cmd[i][0]) {
        case PUSH_BACK:
        case PUSH_FRONT: {
            test_cmd[i][1] = rand();
            ++cur_size;
            break;
        }
        case INSERT: {
            test_cmd[i][1] = rand() % cur_size;
            test_cmd[i][2] = rand();
            ++cur_size;
            break;
        }
        case POP_BACK:
        case POP_FRONT: {
            --cur_size;
            break;
        }
        case ERASE: {
            test_cmd[i][1] = rand() % cur_size;
            --cur_size;
            break;
        }
        }
    }
 
    // test my list
    int my_list_begin = GetTickCount();
    for (int i = 0; i < NODE_SIZE; ++i) {
        switch (test_cmd[i][0]) {
        case PUSH_BACK: {
            my_list.push_back(test_cmd[i][1]);
            break;
        }
        case PUSH_FRONT: {
            my_list.push_front(test_cmd[i][1]);
            break;
        }
        case INSERT: {
            my_list.insert(test_cmd[i][1], test_cmd[i][2]);
            break;
        }
 
        case POP_BACK: {
            my_list.pop_back();
            break;
        }
        case POP_FRONT: {
            my_list.pop_front();
            break;
        }
        case ERASE: {
            my_list.erase(test_cmd[i][1]);
            break;
        }
        }
    }
    int my_list_end = GetTickCount();
 
    // test stl list
    int stl_list_begin = GetTickCount();
    for (int i = 0; i < NODE_SIZE; ++i) {
        switch (test_cmd[i][0]) {
        case PUSH_BACK: {
            stl_list.push_back(test_cmd[i][1]);
            break;
        }
        case PUSH_FRONT: {
            stl_list.push_front(test_cmd[i][1]);
            break;
        }
        case INSERT: {
            list<int>::iterator it = stl_list.begin();
            for (int k = 0; k < test_cmd[i][1]; ++k) {
                ++it;
            }
            stl_list.insert(it, test_cmd[i][2]);
            break;
        }
 
        case POP_BACK: {
            stl_list.pop_back();
            break;
        }
        case POP_FRONT: {
            stl_list.pop_front();
            break;
        }
        case ERASE: {
            list<int>::iterator it = stl_list.begin();
            for (int k = 0; k < test_cmd[i][1]; ++k) {
                ++it;
            }
            stl_list.erase(it);
            break;
        }
        }
    }
    int stl_list_end = GetTickCount();
 
    //time compare
    printf("my list : %d\n", (my_list_end - my_list_begin));
    printf("stl list : %d\n", (stl_list_end - stl_list_begin));
 
    //result test
    list<int>::iterator it = stl_list.begin();
    int cur = my_list.node[my_list.HEAD].next;
    while (it != stl_list.end()) {
        if (*it != my_list.node[cur].val) {
            printf("Error\n");
        }
        ++it;
        cur = my_list.node[cur].next;
    }
 
    return 0;
}

저작자표시 비영리 변경금지

설정

트랙백

na982 삼성 SW 역량 테스트 준비에 도움이 되고자 만든 블로그 입니다. 동영상 강의 PDF 소스코드를 한페이지에서 보실수 있습니다. 주인장은 ACM-ICPC 에 중국, 태국, 국내 대회 본선에 참가 한 경험이 있습니다.

글

Merge Sort

Data Structure 2019. 2. 10. 23:43

100

101

102

103

104

105

106

107

108

109

110

#include <stdio.h>
#include "Windows.h"
#include <algorithm>
using namespace std;
 
const int MAX_SIZE = 500000;
 
int arr_size;
int ms[MAX_SIZE], qs[MAX_SIZE], stls[MAX_SIZE], buf[MAX_SIZE];
 
void merge_sort(int* p, int len) {
    if (len < 2) return;
    int i, j, k, mid;
    mid = (len / 2);
    i = 0, j = mid, k = 0;
 
    merge_sort(p, mid);
    merge_sort((p + mid), (len - mid));
 
    while (i < mid && j < len) {
        if (p[i] < p[j]) {
            buf[k++] = p[i++];
        }
        else {
            buf[k++] = p[j++];
        }
    }
 
    while (i < mid) {
        buf[k++] = p[i++];
    }
 
    while (j < len) {
        buf[k++] = p[j++];
    }
 
    for (int i = 0; i < len; ++i) {
        p[i] = buf[i];
    }
}
 
void qsort(int* p, int left, int right) {
    if (left >= right)   return;
    int l = left - 1;
    int r = right + 1;
    int mid = p[(l + r) / 2];
    while (1) {
        while (p[++l] < mid);
        while (p[--r] > mid);
        if (l >= r)  break;
        int temp = p[l];
        p[l] = p[r];
        p[r] = temp;
    }
    qsort(p, left, l - 1);
    qsort(p, r + 1, right);
}
 
 
int main()
{
    arr_size = MAX_SIZE;
 
    for (int i = 0; i < arr_size; ++i) {
        ms[i] = rand();
        qs[i] = stls[i] = ms[i];
    }
 
    int quick_sort_begin = GetTickCount();
    qsort(qs, 0, arr_size - 1);
    int quick_sort_end = GetTickCount();
 
    int merge_sort_begin = GetTickCount();
    merge_sort(ms, arr_size);
    int merge_sort_end = GetTickCount();
 
    int stl_sort_begin = GetTickCount();
    sort(stls, stls + arr_size);
    int stl_sort_end = GetTickCount();
 
    printf("my quick sort : %d\n", (quick_sort_end - quick_sort_begin));
    printf("my merge sort : %d\n", (merge_sort_end - merge_sort_begin));
    printf("stl sort : %d\n", (stl_sort_end - stl_sort_begin));
    printf("=====================================\n");
 
    quick_sort_begin = GetTickCount();
    qsort(qs, 0, arr_size - 1);
    quick_sort_end = GetTickCount();
 
    merge_sort_begin = GetTickCount();
    merge_sort(ms, arr_size);
    merge_sort_end = GetTickCount();
 
    stl_sort_begin = GetTickCount();
    sort(stls, stls + arr_size);
    stl_sort_end = GetTickCount();
 
    printf("my quick sort : %d\n", (quick_sort_end - quick_sort_begin));
    printf("my merge sort : %d\n", (merge_sort_end - merge_sort_begin));
    printf("stl sort : %d\n", (stl_sort_end - stl_sort_begin));
    printf("=====================================\n");
 
    for (int i = 0; i < arr_size; ++i) {
        if (qs[i] != stls[i] || ms[i] != stls[i]) {
            printf("Error\n");
        }
    }
 
    return 0;
}

저작자표시 비영리 변경금지

설정

트랙백

글

Hash

Data Structure 2019. 1. 22. 22:59

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

#include <stdio.h>
#include <map>
#include <algorithm>
#include "Windows.h"
using namespace std;
 
const int PN = 23;
const int HASH_SIZE = 10000;
 
int table[HASH_SIZE][50];
int hash_size = 0;
char hash_raw[30000][100];
 
char input[30000][100];
map<char*, int> test;
 
unsigned int get_key(char str[]) {
    unsigned int key = 0, p = 1;
 
    for (int i = 0; str[i] != 0; ++i) {
        key += (str[i] * p);
        p *= PN;
    }
 
    return (key % HASH_SIZE);
}
 
int my_strcamp(char a[], char b[]) {
    int i = 0, j = 0;
    while (a[i]) {
        if (a[i++] != b[j++]) {
            --i, --j;
            break;
        }
    }
    return (a[i] - b[j]);
}
 
int contain(char str[]) {
    unsigned int key = get_key(str);
    int size = table[key][0];
    for (int i = 1; i <= size; ++i) {
        int pos = table[key][i];
        if (my_strcamp(hash_raw[pos], str) == 0) {
            return pos;
        }
    }
    return -1;
}
 
void add(char str[]) {
    int len = 0;
    for (len = 0; str[len] != 0; ++len) {
        hash_raw[hash_size][len] = str[len];
    }
    hash_raw[hash_size][len] = 0;
 
    unsigned int key = get_key(str);
    int& size = table[key][0];
    table[key][++size] = hash_size;
 
    ++hash_size;
}
 
bool remove(char str[]) {
    unsigned int key = get_key(str);
    int& size = table[key][0];
    for (int i = 1; i <= size; ++i) {
        int pos = table[key][i];
        if (my_strcamp(hash_raw[pos], str) == 0) {
            for (int j = i + 1; j <= size; ++j) {
                table[key][j - 1] = table[key][j];
            }
            --size;
            return true;
        }
    }
    return false;
}
 
int make_int(int min, int max) {
    return (rand() % (max - min)) + min;
}
 
char make_char() {
    int val = rand() % 52;
    if (val < 26) {
        return static_cast<char>('a' + val);
    }
    return static_cast<char>('A' + val - 26);
}
 
int main()
{
    for (int i = 0; i < 30000; ++i) {
        int len = make_int(10, 100);
        for (int j = 0; j < len; ++j) {
            input[i][j] = make_char();
        }
        input[i][len] = 0;
 
        if (contain(input[i]) == -1) {
            add(input[i]);
        }
        test[input[i]] = i;
 
 
        if (i > 20000) {
            int cmd = make_int(0, 5);
            int index = make_int(0, i);
            if (cmd == 0) {
                if (contain(input[index]) != -1) {
                    remove(input[index]);
                }
 
                test.erase(input[index]);
            }
            if (cmd == 1) {
                int my_pos = contain(input[index]);
                map<char*, int>::iterator iter = test.find(input[index]);
                int stl_pos = -1;
                if (iter != test.end()) {
                    stl_pos = iter->second;
                }
 
                if (my_pos != stl_pos) {
                    printf("find error!!!\n");
                }
            }
        }
    }
 
    int my_hash_size = 0;
    for (int i = 0; i < HASH_SIZE; ++i) {
        my_hash_size += table[i][0];
    }
 
    if (my_hash_size != test.size()) {
        printf("remove error!!!\n");
    }
 
    return 0;
}

저작자표시 비영리 변경금지

설정

트랙백

글

Heap

Data Structure 2019. 1. 11. 22:36

#include <stdio.h>
#include <algorithm>
#include "Windows.h"
using namespace std;
 
int heap_size;
int heap[10000];
 
void push(int data) {
    int target = heap_size + 1;
    while (target != 1 && heap[target / 2] < data) {
        heap[target] = heap[target / 2];
        target /= 2;
    }
    heap[target] = data;
    ++heap_size;
}
 
void pop() {
    int parent = 1, child = 2;
    int temp = heap[heap_size];
    while (child < heap_size) {
        if (child + 1 < heap_size && heap[child] < heap[child + 1]) {
            ++child;
        }
        if (temp >= heap[child]) {
            break;
        }
        heap[parent] = heap[child];
        parent = child;
        child *= 2;
    }
    heap[parent] = temp;
    --heap_size;
}
 
bool comp(int a, int b) {
    return (a > b);
}
 
int main()
{
    int a[10000], b[10000];
    for (int i = 0; i < 9999; ++i) {
        a[i] = rand() % 10000;
        b[i] = a[i];
    }
    sort(a, a + 9999, comp);
 
    for (int i = 0; i < 9999; ++i) {
        push(b[i]);
    }
 
    for (int i = 0; i < 9999; ++i) {
        if (a[i] != heap[1]) {
            printf("not heap!!!\n");
        }
        pop();
    }
 
    return 0;
}

저작자표시 비영리 변경금지

설정

트랙백

이전 1 다음

지역로그 : 태그 : 방명록 : 관리자 : 글쓰기

ㄴ ㅏ구팔이's Blog is powered by Daum & Tattertools / Designed by Tistory

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

na982

검색결과 리스트

Data Structure에 해당되는 글 4건

글

Linked List

설정

트랙백

댓글

글

Merge Sort

설정

트랙백

댓글

글

Hash

설정

트랙백

댓글

글

Heap

설정

트랙백

댓글

사이드 메뉴

CATEGORY

COUNTER

TAG

RECENT POSTS

CALENDAR

티스토리툴바

개인정보

단축키

내 블로그

블로그 게시글

모든 영역