크루스칼(Kruskal)의 MST 알고리즘 Kruskal 알고리즘은 탐욕적인 방법(Greedy, 그리디)를 사용합니다. 그리디를 간략하게 설명하자면, 선택할 때마다 그 순간 가장 좋다고 생각되는 것을 선택함으로써 최종적인 해답에 도달하는 방법입니다. 그리디는 근사적인 방법이기 때문에 항상 최적의 해답을 주지 않을 수도 있습니다. 하지만 Kruskal의 MST 알고리즘은 최적의 해답을 주는 것으로 증명되었기 때문에 이 방법으로 최적해(최단 경로)를 구할 수 있습니다. 알고리즘의 작동 방식은 다음과 같습니다. 그래프의 간선들을 가중치의 오름차순으로 정렬함 사이클을 형성하지 않는 간선을 찾아서 최소 신장 트리의 집합에 추가함 가장 낮은 가중치를 가진 간선을 먼저 선택함 만약 사이클을 형성하는 간선이 있다면 그..

신장 트리 (Spanning Tree) 신장 트리는 그래프 내의 모든 정점을 포함하는 트리입니다. 다만 아래의 조건들을 만족해야 합니다. 모든 정점들이 연결되어 있어야 함 사이클을 포함하면 안 됨 n개의 정점을 n-1개의 간선으로 연결해야 함 해당 조건만 만족하면 되므로 하나의 그래프에는 다양한 신장 트리가 존재할 수 있습니다. 최소 신장 트리 (MST; Minimum Spanning Tree) 최소 신장 트리는 네트워크에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결한 트리입니다. 최소 신장 트리를 구하는 방법으로는 Kruskal과 Prim이 고안한 알고리즘이 대표적으로 사용되고 있습니다. Union-Find 최소 신장 트리를 구하기 위해서 union-find라는 연산을 해야 합니다. uni..

허프만 코드 (Huffman Code) 앞서 포스팅한 이진 트리를 응용해서 문자열을 압축할 수 있습니다. 허프만 코드는 문자열을 사용한 빈도수에 따라 우선순위를 매겨 이것을 최소 힙 트리로 만들어 마치 압축한 것처럼 바꾸는 것입니다. 예를 들어, 다음과 같은 문장이 있다고 해봅시다. data structure and algorithm 이 문장에서 문자들의 빈도수는 다음과 같습니다. 문자 빈도수 문자 빈도수 a 4 m 1 c 1 n 1 d 2 o 1 e 1 r 3 g 1 s 1 h 1 t 4 i 1 u 2 l 1 이 표에 나온 정보들을 바탕으로 허프만 코드를 만들어 보겠습니다. 위에서 최소 힙 트리를 만든다고 했는데, 빈도수가 최소 힙 트리의 인자값이 되면 됩니다. 우선, 빈도수가 가장 적은 원소를 묶습니..

힙 (Heap) 힙은 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조입니다. 힙의 종류 힙에는 두 가지 종류의 힙 트리가 존재합니다. 하나는 부모 노드의 키 값이 자식 노드보다 큰 최대 힙 (Max Heap), 다른 하나는 부모 노드의 키 값이 자식 노드보다 작은 최소 힙(Min heap)입니다. 루트 노드가 최대면 최대 힙이고 최소면 최소 힙임을 알 수 있습니다. 힙 구현 최대 힙의 함수들을 각각 구현해보면서 최대 힙 트리가 어떻게 동작하는지 차근차근 알아가보겠습니다. insert_max_heap(*h, item) 최대 힙의 삽입 연산은 다음과 같이 동작합니다. 힙 크기를 하나 증가시킨다. 트리를 거슬러 올라가면서 부모 노드와 비교해서 부모 노드보다 크다면 인..

이진 탐색 트리 이진 탐색 트리는 이진 트리를 기반으로 한 탐색을 위해 만들어진 자료 구조입니다. 기존의 이진 트리 정의를 지키면서 탐색에 용이하게 왼쪽 노드에는 루트 노드보다 작은 키의 노드를, 오른쪽 노드에는 루트 노드보다 큰 키의 노드를 삽입해줍니다. 이진 탐색 트리의 정의 모든 원소의 키는 유일한 키를 가진다. 왼쪽 서브 트리 키들은 루트 키보다 작다. 오른쪽 서브 트리의 키들은 루트의 키보다 크다. 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다. 찾고자 하는 키 값이 이진 트리의 루트 노드 키 값과 비교해 루트 노드보다 작으면 왼쪽 서브 트리에 있고 루트 노드보다 크면 오른쪽 서브 트리에 있는 성질을 이용하여 탐색을 쉽게 할 수 있습니다. 동작 방식은 아래와 같습니다. 비교한 결과가 같으면 → ..

이진 트리 순회 이진 트리를 순회한다는 것은 이진 트리에 속하는 모든 노드를 한 번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하는 것을 의미합니다. 이진 트리에서 순회가 중요한 이유는, 순회 순서에 따라 기대할 수 있는 결과값이 다르기 때문입니다. 이진 트리 순회 방법 전위, 중위, 후위 총 3가지의 방법이 있습니다. 이는 루트와 왼쪽 서브트리, 오른쪽 서브 트리 중에서 루트를 언제 방문하느냐에 따라 구분됩니다. 만약 루트를 방문하는 작업을 $V$라 하고, 왼쪽 서브트리 방문을 $L$, 오른쪽 서브트리 방문을 $R$이라고 한다면 다음과 같이 3가지 방법을 생각할 수 있습니다. 이진 트리의 순회방법 전위 순회(preorder traversal): VLR 중위 순회(inorder travers..

이진 트리의 정의 모든 노드가 2개의 서브 트리를 가지고 있는 트리입니다. 서브 트리는 공집합일 수 있습니다. 따라서 이진 트리의 노드에는 최대 2개까지의 자식 노드가 존재할 수 있고 모든 노드의 차수가 2 이하가 됩니다. 따라서 트리의 차수도 2 이하가 됩니다. 공집합도 이진 트리라는 점에 주의합시다. 또한, 이진 트리에는 서브 트리간의 순서가 존재합니다. 따라서 왼쪽 서브 트리와 오른쪽 서브 트리는 서로 구별됩니다. 이진 트리의 정의 1. 공집합이거나, 2. 루트와 왼쪽 서브 트리, 오른쪽 서브 트리로 구성된 노드들의 유한 집합으로 정의된다. 이진 트리의 서브 트리들은 모두 이진 트리여야 한다. 이진 트리의 성질 $n$개의 노드를 가진 이진 트리는 $n-1$개의 간선을 가집니다. 높이가 $h$인 이진..