Binary Search Tree(이진 탐색 트리), UnionFind(유니온 파인드)

#include <iostream> #include <vector> #include <list> #include <string> #include <algorithm> #include <map> int bst[256] = { 0, }; void insert(int data) { int idx = 1; while (1) { if (bst[idx] == 0) { bst[idx] = data; break; } else if (bst[idx] > data) { idx = idx * 2; } else { idx = idx * 2 + 1; } } } int main() { insert(10); insert(5); insert(15); //insert(8); //insert(3); //insert(7); //insert(12); return 0; }

#include <iostream> #include <vector> #include <list> #include <string> #include <algorithm> #include <map> int bst[256] = { 0, }; void insertRescursive(int data, int now) { if (bst[now] == 0) { bst[now] = data; return; } if (bst[now] > data) { insertRescursive(data, now * 2); } else { insertRescursive(data, now * 2 + 1); } } nt main() { insertRescursive(10, 1); insertRescursive(5, 1); insertRescursive(15, 1); insertRescursive(8, 1); return 0; }

#include <iostream> #include <vector> #include <list> #include <string> #include <algorithm> #include <map> int bst[256] = { 0, }; void insert(int data) { int idx = 1; while (1) { if (bst[idx] == 0) { bst[idx] = data; break; } else if (bst[idx] > data) { idx = idx * 2; } else { idx = idx * 2 + 1; } } } void insertRescursive(int data, int now) { if (bst[now] == 0) { bst[now] = data; return; } if (bst[now] > data) { insertRescursive(data, now * 2); } else { insertRescursive(data, now * 2 + 1); } } void search(int data) { int idx = 1; while (1) { if (bst[idx] == 0) { printf("Not Found\n"); break; } if (bst[idx] == data) { printf("Found\n"); break; } if (bst[idx] > data) { idx = idx * 2; } else { idx = idx * 2 + 1; } } } void searchRecursive(int data, int now) { if (bst[now] == 0) { printf("Not Found\n"); return; } if (bst[now] == data) { printf("Found\n"); return; } if (bst[now] > data) { searchRecursive(data, now * 2); } else { searchRecursive(data, now * 2 + 1); } } int main() { // Binary Search Tree // 데이터를 탐색하는데 있어서 효율성 높다. // 3가지 동작을 기본으로 둔다. // 데이터를 저장하는 Insert // 데이터를 찾는 Search // 데이터를 삭제하는 Delete // insert, serach 위조루 보겠다. // 사용하는 제일 큰 이유는 데이터를 더 빨리 찾기위해 사용하는 자료구조이다. //insert(10); //insert(5); //insert(15); //insert(8); //insert(3); //insert(7); //insert(12); insertRescursive(3, 1); insertRescursive(5, 1); insertRescursive(1, 1); insertRescursive(2, 1); insertRescursive(4, 1); insertRescursive(7, 1); return 0; }

#include <iostream> #include <vector> #include <list> #include <string> #include <algorithm> #include <map> int name[256] = {}; int n = 0; int group[256] = {}; int gCnt = 0; void insert(char a, char b) { if (group[a] == 0) name[n++] = a; if (group[b] == 0) name[n++] = b; // a는 그룹에 있는데, b는 그룹에 없다. if (group[a] != 0 && group[b] == 0) group[b] = group[a]; // a그룹은 없고, b 그룹은 있다. else if (group[a] == 0 && group[b] != 0) group[a] = group[b]; //둘다 그룹이 없는경우는 새로운그룹을 만든다. else if (group[a] == 0 && group[b] == 0) { gCnt++; group[a] = gCnt; group[b] = gCnt; } else { // 둘다 그룹이 있는 경우, 그룹을 a로 통합시킨다. int g = group[b]; for (int i = 0; i < n; i++) { if (group[name[i]] == g) group[name[i]] = group[a]; } } } int main() { // 그룹으로 관리하는것은 분류하거나 검색하는데 있어서 유용하다. // 그룹끼리 통합을 시키면 큰데이터를 연산하지 않고 작은 데이터로 연산할 수 있다. // 그룹 1 insert('A', 'B'); insert('A', 'C'); // 그룹2 insert('E', 'Q'); insert('E', 'F'); // 통합 insert('F', 'A'); return 0; }

#include <iostream> #include <vector> #include <list> #include <string> #include <algorithm> #include <map> char parnet[1000001]; char getParent(char x) { if (parnet[x] == 0) return x; int ret = getParent(parnet[x]); parnet[x] = ret; return ret; } void insert(char ch1, char ch2) { int a = getParent(ch1); int b = getParent(ch2); if (a != b) parnet[b] = a; } int main() { // 그룹으로 관리하는것은 분류하거나 검색하는데 있어서 유용하다. // 그룹끼리 통합을 시키면 큰데이터를 연산하지 않고 작은 데이터로 연산할 수 있다. insert('A', 'G'); insert('H', 'C'); insert('A', 'H'); insert('F', 'D'); insert('A', 'F'); return 0; }