검색결과 리스트
백준에 해당되는 글 43건
- 2019.02.13 Linked List 5
- 2019.02.10 Merge Sort
- 2019.01.26 [KOI]전국본선 2014 중등부 세번째 문제
- 2019.01.26 [KOI]전국본선 2014 중등부 두번째 문제
- 2019.01.26 [KOI]전국본선 2013 중등부 두번째 문제
글
Linked List
Data Structure
2019. 2. 13. 23:00
#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;
}글
Merge Sort
Data Structure
2019. 2. 10. 23:43
#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;
}
글
[KOI]전국본선 2014 중등부 세번째 문제
KOI (정보올림피아드) 기출 풀이
2019. 1. 26. 21:14
#include <stdio.h>
#include <algorithm>
#include <deque>
using namespace std;
const int MAX_SIZE = 500000;
struct BUS{
int s, e, index;
};
bool comp(BUS a, BUS b) {
return (a.s == b.s) ? (a.e > b.e) : (a.s < b.s);
}
bool comp1(BUS a, BUS b) {
return (a.index < b.index);
}
BUS bus[MAX_SIZE];
int main()
{
int N, M, end_point = 0;
scanf("%d %d", &N, &M);
for(int i = 0; i < M; ++i){
scanf("%d %d", &bus[i].s, &bus[i].e);
bus[i].index = i + 1;
if (bus[i].s > bus[i].e) {
end_point = max(end_point, bus[i].e);
bus[i].e += N;
}
}
sort(bus, bus + M, comp);
deque<BUS> q;
for (int i = 0; i < M; ++i) {
if (q.empty() || q.back().e < bus[i].e) {
q.push_back(bus[i]);
}
}
while (!q.empty() && q.front().e <= end_point) {
q.pop_front();
}
sort(q.begin(), q.end(), comp1);
for (auto x : q) {
printf("%d ", x.index);
}
return 0;
}
글
[KOI]전국본선 2014 중등부 두번째 문제
KOI (정보올림피아드) 기출 풀이
2019. 1. 26. 21:08
#include <stdio.h>
int seat[2000][2001];
int gcd(int a, int b) {
return (b) ? gcd(b, a % b) : (a);
}
int main()
{
int ret = 0;
int from, to;
scanf("%d %d", &from, &to);
for (int i = from; i <= to; ++i) {
for (int j = 0; j < i; ++j) {
int g = gcd(i, j);
int up = j / g;
int down = i / g;
if (seat[up][down] == 0) {
seat[up][down] = 1;
++ret;
}
}
}
printf("%d\n", ret);
return 0;
}
글
[KOI]전국본선 2013 중등부 두번째 문제
KOI (정보올림피아드) 기출 풀이
2019. 1. 26. 15:05
#include <stdio.h>
int main()
{
int n;
int after[30] = { 0, }, before[30] = { 0, };
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", &after[i]);
}
int cur = 0, count = 0;
while (count < n) {
while (before[cur] != 0) {
cur = (cur + 1) % n;
}
before[cur] = after[count++];
cur = (before[cur] + cur) % n;
}
printf("%d\n", n);
for (int i = 0; i < n; ++i) {
printf("%d ", before[i]);
}
return 0;
}
