[학교 수업]

1. Path Path는 한 정점에서 다른 정점가지 연속되는 간선들을 통해서 도달할 수 있는 방법입니다. 예를 들어 아래와 같은 그래프가 있을 때:1번 정점에서 3번 정점까지 도달할 수 있는 Path 는 다음과 같이 나타낼 수 있습니다:1-e1 → 2-e1 →  1-e3 →  3-e4 →  2-e6 →  2-e5 →  2-e4 →  3 이때 간선의 이름과 같이 정점의 이름도 같이 적어주는데, 그냥 간선 이름들만 적어줘도 Path 를 설명할 수 있지 않을까?그렇지 않습니다. 만약 e1 → e1 → e3 → e4 → e6 → e5 → e4 라고만 적어놨다면,처음 시작하는 노드는 어디였고, 어느 정점에서 어느 정점으로 향하는 간선인지 명확하지 않습니다. 다시한번 Path 에 대해 정의하자면 다음과 같습니다: ..

3. Graph Patterns 3.1 Complete Graph - Kn 서로 다른 노드들의 모든 노드쌍에 대해서 간선을 공유하는 단순 그래프를 Complete Graph - Kn 이라고 합니다. 이때 n 은 정점의 개수입니다.(* A simple graph is complete if every pair of distinct vertices share an edge. The notation Kn denotes the complete graph on n vertices) 3.2 Cycles - Cn ... (* The cycle graph Cn is a circular graph with V = {0,1,2,...,n-1} where vertex i is connected to i+1 mod n and ..

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 ..