쥬코딩

쿼드트리 특징 -degree가 4인 트리(각 사분면에 속하는 요소가 한 개일때까지 나눈다) -performance: O(log4n) -불균형 트리 위의 쿼드 트리의 노드를 각 사분면 별로 mapping해서 트리형식으로 표현하면 아래와 같다. (왼쪽부터 차례대로 1,2,3,4사분면) 쿼드트리에서 root노드는 실제로 존재하지 않지만 mapping하여 표현할 때는 root노드를 그려준다. 나뉘어진 사분면의 개수와 각 사분면에 있는 1의 개수를 세는 함수이다. char graph[25][25]; int region[625] = { 0, }; int quad(int i, int j, int n, int cnt) { graph[i][j] = 0; region[cnt]++; if (i - 1 >= 0 && grap..

자료구조 2022. 7. 12. 15:20

Dijkstra's algorithm: 방향그래프(directed graph)에서 한 노드에서 다른 노드까지 최소 비용을 갖는 길 찾기 performance of Dijkstra's algorithm: O(N^2) 아래 그래프에서 Dijkstra's algorithm을 이용하여 노드A에서 노드E까지 최소 비용을 갖는 길 찾기 1. 노드A에서 시작해서 가장 비용이 적은 노드를 선택한다. 2. 1번에서 선택한 노드를 거쳐서 더 비용이 적다면 그 비용을 다시 적는다.

자료구조 2022. 7. 11. 10:49

최소의 총 가중치를 갖는 spanning tree를 찾는 방법 중 prim's algorithim과 kruskal's algrithm에 대해 알아보겠다. spanning tree에 대한 글은 아래 참고 2022.07.01 - [자료구조] - [자료구조] spanning tree (sub graph) [자료구조] spanning tree (sub graph) spanning tree: 그래프에서 cycle이 제거된 sub graph -Depth First Traversal을 이용해 spanning tree 만들기 먼저 DFS방식으로 그래프를 순회한다. 위의 그림에서 서로 연결된 노드들만 그래프에서 다시 연결.. jicoding.tistory.com - Prim's algorithm 1. undirected..

자료구조 2022. 7. 4. 13:30

#define _CRT_SECURE_NO_WARNINGS #include int heap[100001]; int t = 0; int n; void swap(int i, int j) { int tmp = heap[i]; heap[i] = heap[j]; heap[j] = tmp; } //값 저장 void push(int x) { heap[++t] = x; for (int i = t; i > 1; i /= 2) { if (heap[i] < heap[i / 2]) swap(i, i / 2); else break; } } //내림차순으로 값 출력 int pop() { int top = heap[1]; heap[1] = heap[t]; heap[t--] = 0; int i = 1; while (i * 2 heap..

자료구조 2022. 7. 4. 09:23

spanning tree: 그래프에서 cycle이 제거된 sub graph -Depth First Traversal을 이용해 spanning tree 만들기 먼저 DFS방식으로 그래프를 순회한다. 위의 그림에서 서로 연결된 노드들만 그래프에서 다시 연결시키면 spanning tree가 만들어진다. -Breadth First Traversal을 이용해 spanning tree 만들기 먼저 BFS방식으로 그래프를 순회한다. 위의 그림에서 서로 연결된 노드들만 그래프에서 다시 연결시키면 spanning tree가 만들어진다.

자료구조 2022. 7. 1. 12:29

그래프는 node와 edge로 이루어진다. edge에는 undirected edge, directed edge, weighted edge 가 있다. undirected edge (and unweighted) directed edge (and weighted) weighted edge -용어 subgraph: 그래프의 한 부분(그래프의 특성을 가지고 있는) connected graph: 모든 노드가 다른 모든 노드로 접근이 가능한 그래프 disconnected graph: 최소 하나의 노드가 다른 모든 노드로 접근이 불가능한 그래프 adjacent node: 두 노드 사이에 edge로 곧바로 연결된 것 complete graph: 모든 노드가 다른 모든 노드로부터 인접한 것(edge로 곧바로 연결된 것) ..

자료구조 2022. 6. 28. 10:24

T-tree: AVL tree(rotation, not perfectly balanced) + B tree(N ~ 2N data for each node) 시간복잡도: O(log2[N/M]) N: total # of keys, M: # of keyw per node

자료구조 2022. 4. 11. 14:21

2-3Tree: 이진탐색트리의 한 종류 (perfectly balanced) 노드의 종류가 2 node와 3 node로 두 개 있다. 시간복잡도: 2 node -> O(log2n), 3 node -> O(log3n) 2-3 tree의 조건 1: -1 왼쪽과 오른쪽의 height의 차이 즉, BF의 절대값이 클수록 노드 탐색 시간이 길어지기 때문이다 2-3 tree의 조건2: 2-node는 1개의 key, 2개의 child를 가진다. 3-node는 2개의 key, 3개의 child를 가진다. struct node { int key1; intkey2; //2-node의 key2는 NULL 값을 갖는다. struct node *left_child; struct node *middle_child; //2-nod..

자료구조 2022. 4. 11. 14:16