전체 글

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

https://www.acmicpc.net/problem/16236BFS 를 통해 최단거리를 구하는 문제인 것 같다.다만 같은 거리일 경우의 우선순위(* row index 가 작은게 먼저, col index 가 작은게 먼저) 가 추가적으로 붙어있다.그 외의 것들은 크게 다르지 않다. 이런식으로 쭉 풀어봤는데... 메모리 초과가 떴다. 처음이었다. Point 클래스를 너무 남발하면 그럴 수 있다더라...앞으로는 메모리도 좀 신경쓰면서 구현해야겠다. 처음에는 모든 가능한 노드에 대해 Point 객체를 생성해서 비교했었다. 이런 불필요한 인스턴스들은 메모리를 많이 잡아먹을 수 있다. 그래서 이동 가능할 수 있는 노드들을 Point 객체가 아닌, 그냥 row index 와 col index 를 이용했다. 또한 ..

https://www.acmicpc.net/problem/1167아.. 어렵다 처음 생각으로는 DFS 를 여러번 수행해서 각 노드에 대한 최대 길이를 구하려고 했지만N = 100,000 이고 DFS 를 각 노드에 대해 수행하면 빨라야 O(N^2) 이기 때문에 당연히 시간초과가 발생하는거였다.(* 10,000,000,000 번의 계산이 필요한데 일반적인 CPU 는 1억번의 연산 당 1초가 걸리기 때문에 100초가 걸린다.) 어쩔 수 없이 구글링을 해봤는데단 두 번의 DFS 만으로 트리의 지름을 알 수 있는 방법이 존재했다. 트리의 성질을 이용하면 가능한데, 자세한 증명은 아래 접은 글에 첨부해놓았다.더보기https://velog.io/@besyia0k0/Algorithm-diameter-of-tree [알..

0. 들어가기 전 Heap은 '우선순위 큐'에 사용되기 위해 필수적으로 알아야 하는 자료구조입니다. 추가적으로 흔히 동적으로 변수를 만들 때 해당 변수가 저장되는 공간인 Heap 과는 다른 의미입니다. 1. Heap Heap 은 최소값 또는 최대값을 빠르게 찾아내기 위해 완전이진트리의 형태로 만들어진 자료구조입니다. 이진 트리는 아는데 완전 이진트리는 무엇일까? 1.1 Complete Binary Tree 트리(Tree)는 계층 구조를 갖는 자료구조로서, 서로 연결되어 있는 노드들의 집합입니다. 트리에는 자식들과 가지의 형태로 연결되어있는 루트 노드가 있습니다. 이때 이진 트리(Binary Tree)는 자식 노드의 개수를 최대 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 ..