![]()
0. 들어가기 전 해당 글은 Zeph Grunschlag 의 Graphs 에서 배운 내용을 정리하는 글 입니다. 1. Graphs - Intuitve Notion 그래프는 정점(혹은 노드)(* Vertices or Nodes)들의 집합입니다. 이를 간선(* Edges)들에 연결된 점들로 표현할 수 있습니다.수학적으로 (멀티그래프를 제외한) 그래프는 정점 집합(* Vertices)에 대한 이진 관계(* binary-relations) 입니다. 2. various types of Graphs 그래프를 사용하는 곳이 많기 때문에 서로 다른 종류의 그래프들이 필요합니다. 예를 들어, local computer network 에서는 bidirectional(* undirected) 하고 loop 가 없어야 하며..
![]()
1. an Application Union-Find 를 알아보기 전에 이것을 언제 사용하는지를 먼저 파악하는 것이 좋아보입니다. MST(* Minimum Spanning Tree), 최소신장트리는 Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리입니다. 그렇다면 Spanning Tree 는 무엇일까요? Spanning Tree 는 그래프 내의 모든 노드를 포함하는 부분 그래프입니다. 또한 Spanning Tree 는 그래프의 최소 연결 부분 그래프이기도 합니다. 최소 연결이란 간선의 수가 가장 적은 것을 의미합니다.즉, n 개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1) 개 이므로, Spanning Tree 의 간선의 개수는 (n-1) 개 입니다.다른 말로 하면 주어진 그..
![]()
1. Tree traversal 트리의 모든 노드들을 방문하는 과정을 트리 순회, Tree Traversal 이라고 합니다. 이때 방문은 정말 "방문" 만 하는 것이 아니라 해당 노드에서 어떤 수행을 하는것을 의미합니다. 일반적으로 트리의 순회에는 다음과 같은 방법들이 있습니다.전위 순회(Preorder)중위 순회(Inorder)후위 순회(Postorder)이런 순회는 보통 DFS 를 통해 구현할 수 있습니다.Traverse(Node *D){ if (D == NULL) return; Visit(D); Left); Visit(D); Right); Visit(D); 이렇게 생긴 트리가 있을 때, 각 순회 방식에 따른 노드 방문의 순서는 어떻게 될까요?Preorder : 6, 4, 2,..
0. 들어가기 전 2024.05.18 - [자바[JAVA]/자바[JAVA] 자료구조 구현] - 자바[JAVA] 자료구조 구현 7 - Heap 자바[JAVA] 자료구조 구현 7 - Heap0. 들어가기 전 Heap은 '우선순위 큐'에 사용되기 위해 필수적으로 알아야 하는 자료구조입니다. 추가적으로 흔히 동적으로 변수를 만들 때 해당 변수가 저장되는 공간인 Heap 과는 다른 의미입니hw-hk.tistory.com위 글을 통해 Heap 에 대한 기본적인 이해가 되었다고 가정하고 진행하겠습니다. 1. Priority Queue 2024.04.11 - [자료구조 및 알고리즘] - 자료구조 및 알고리즘 5 - Queue and Stack 자료구조 및 알고리즘 5 - Queue and Stack자료구조 수업을 바탕..
![]()
0. 들어가기 전2024.05.14 - [자료구조 및 알고리즘] - 자료구조 및 알고리즘 10 - 2-3 Tree and 2-3-4 Tree 자료구조 및 알고리즘 10 - 2-3 Tree and 2-3-4 Tree0. 2-3 Tree Likewise, 2-3 Tree is also a height balanced tree. The time complextity of search/insert/delete is O(logN)(* A 2-3 tree is a B tree of order 3) 1. Properties of 2-3 tree Nodes with two children are called 2-nodes. The 2-nodes have one data vhw-hk.tistory.com위 글을 통해 2..
![]()
0. 2-3 Tree Likewise, 2-3 Tree is also a height balanced tree. The time complextity of search/insert/delete is O(logN)(* A 2-3 tree is a B tree of order 3) 1. Properties of 2-3 tree Nodes with two children are called 2-nodes. The 2-nodes have one data value(* one key) and two childrenNodes with three children are called 3-nodes. The 3-nodes have two data value(* two keys) and three childrenThat ..
![]()
0. 들어가기 전2024.05.02 - [자료구조 및 알고리즘] - 자료 구조 및 알고리즘 9 - AVL Tree 1. 구현 앞서 글을 통해 삽입이나 삭제를 통해 불균형이 생기는 경우 어떻게 AVL Tree 가 균형을 맞출 수 있는지에 대해 알아봤습니다. 요약하자면, 크게 4가지 case 로 불균형이 생길 수 있는데LL caseLR caseRL caseRR case입니다. 위 4가지 case 에 대한 구현이 가장 중요한 점입니다. 2. Node 노드는 이전 노드들과 달리 BF, height 요소를 추가적으로 가집니다. (* 해당 요소들에 대한 설명은 이전 글에 자세히 설명했습니다.) 또한 이전 노드 클래스와 달리 reValuing() 이라는 함수도 갖고 있는데, 삽입이나 삭제 이후 변화가 생긴 ..
![]()
0. AVL Tree AVL 트리는 발명자의 이름인 Adelson-Velsky and Landis 에서 따온 이름으로 자가 균형 이진 탐색 트리입니다. 자가 균형 이진 트리는 스스로 균형을 잡는 트리라는 의미로 삽입, 삭제와 같이 데이터 균형이 달라질 것 같은 수행에서 스스로 균형을 맞추도록 트리의 구조를 바꿉니다. 일반적인 이진 탐색 트리와 달리 검색, 삽입, 삭제는 모두 평균과 최악의 경우 O(logN) 을 보장합니다.(* BST 의 경우 최악의 경우 O(N) 입니다.)2024.04.20 - [자료구조 및 알고리즘] - 자료구조 및 알고리즘 8 - Binary Search Tree 1. Definition 1.1 Height-balance property 높이 균형 성질은 트리 T 에 대해 모든..
