최단 경로그래프에서의 최단 경로 문제는 방향 그래프를 기준으로 구한다.음이 아닌 가중치 그래프의 최단 경로 (Dijkstra 알고리즘)다익스트라(또는 데이크스트라) 알고리즘은 한 정점에서 다른 모든 정점까지의 최단 경로 거리를 구한다.Dijkstra 알고리즘은 기본적으로 Prim 알고리즘과 매우 유사하다.Dijkstra 알고리즘은 그래프의 모든 가중치가 음이 아닌 경우에만 유효하다.Prim 알고리즘과 Relaxation 과정만 차이가 있다.Prim 알고리즘은 현재 정점에서 인접한 정점까지의 새로 찾은 거리가 dist 배열에 기록된 거리보다 더 짧은 경우 업데이트Dijkstra 알고리즘은 현재 정점까지의 누적 거리와 인접한 어떤 정점까지의 새로 찾은 거리를 더했을 때 dist 배열에 기록된 거리보다 더 짧..

신장 트리 (Spanning Tree)그래프 상의 모든 정점이 사이클 없이 연결된 부분 그래프를 신장 트리라 한다.정점의 개수가 n개인 경우, 신장 트리는 n-1개의 간선을 가진다.최소 비용 신장 트리 (Minimum-cost Spanning Tree, MST)주어진 그래프에서 모든 정점을 연결하는 트리 중 간선 가중치의 합이 최소인 트리 가중치가 있는 무방향 그래프의 신장 트리의 비용은 신장 트리에 있는 간선들의 비용(가중치)의 합이다.신장 트리의 비용이 최소가 되는 트리를 최소 비용 신장 트리(MST)라 한다.MST를 구성하는 데에는 다음의 제한 조건이 있다.그래프 내에 있는 간선만 사용정확하게 n-1개의 간선만 사용사이클을 생성하는 간선은 사용하지 않음MST를 구하기 위해선 대표적으로 세 가지 알고..

그래프그래프 정의와 용어그래프 G는 공집합이 아닌 정점 집합 V와 간선 집합 E로 구성된다.G = (V,E)두 정점이 간선으로 연결되었다면 두 정점은 인접(adjacent)하다고 한다.자기 자신을 간선으로 연결하는 것을 Self-loop(또는 Self-edge)라고 한다.V(G`)⊆ V(G)이고 E(G`)⊆ E(G)인 그래프 G`를 그래프 G의 부분 그래프(subgraph)라 한다.정점 u부터 정점 v까지의 경로(path)는 정점 순서 u, i1, i2, ..., ik, v를 말한다.한 경로의 길이(length)는 경로 상에 있는 간선의 수이다.경로 상에서 처음과 마지막을 제외한 모든 정점들이 서로 다를 때, 그 경로를 단순 경로(simple path)라 한다.처음과 마지막 정점이 같은 단순 경로를 사이..

Dynamic Set검색, 삭제, 삽입 등의 연산을 지원하는 자료구조를 통틀어 Dynamic Set이라 한다.Dynamic Set을 구현하려면배열, 연결 리스트, 해시 테이블 등 선형 구조를 이용 -> Insert, Search, Delete 중 적어도 하나는 O(n)이진 탐색 트리, 레드-블랙 트리, AVL 트리 등의 트리 기반 구조 이용 -> 모두 O(logn)이진 탐색 트리 (Binary Search Tree)이진 탐색 트리 개요자료를 빠르게 검색하기 위한 검색 트리 중 하나이진 트리의 구조를 가짐각 노드에 하나의 Key만 저장임의의 노드 v에 대하여왼쪽 서브트리에 있는 Key들은 Key[V]보다 작거나 같다.오른쪽 서브트리에 있는 Key들은 Key[V]보다 크거나 같다.서브트리도 이진 검색 트리 ..

Heap Sort힙 정렬은 힙을 사용해 데이터를 정렬하는 알고리즘이다.힙의 루트 노드에서 지속적으로 값을 꺼내면 특정한 순서로 정렬할 수 있다. 힙 자료구조를 모른다면 다음 글을 참고하자.2025.01.13 - [Programming/Data Structure] - [Data Structure] 힙 트리코드#include #include "../Chapter5/5.6/MaxHeap.hpp"void Print(int* arr){ for (int i = 0; i heap; for (int i = 0; i = 0; i--) { result[i] = heap.Top(); heap.Pop(); } return result;}int main(){ s..

힙 트리 (Heap Tree)우선순위 큐를 위해 최대 또는 최소값을 빠르게 검색하는 자료구조완전 이진 트리의 일종아래에서 나올 Heap Property 중 하나를 만족해야 함반정렬(느슨한 정렬) 상태를 유지함Max Heap Property 기준, 부모보다 작기만 하면 되므로 부모-자식 관계가 아닌 다른 노드들끼리는 정렬 관계 상관 X서브 트리가 힙 트리면 서브 트리의 서브 트리도 힙 트리힙 트리 판단하기힙 트리인지 판단하기 위해선 다음 두 가지를 확인하면 된다.완전 이진 트리인가?Heap Property를 만족하는가?Heap PropertyMax-heap Property부모가 자식보다 항상 크거나 같은 성질루트 노드가 항상 최댓값을 가짐서브 트리의 루트 노드는 해당 서브 트리에서 최댓값을 가짐 Min-h..

개요트리 순회(tree traversal)은 트리의 모든 노드를 한 번씩 방문하는 것이다.L, V, R이 한 노드에서 각각 왼쪽 이동, 노드 방문, 오른쪽 이동을 나타낸다면 다음과 같다.전위 순회: VLR중위 순회: LVR후위 순회: LRV트리의 순회는 재귀를 사용하면 쉽게 구현할 수 있다.트리의 순회 방법은 수식에서의 전위 표기(prefix), 중위 표기(infix), 후위 표기(postfix)가 자연스럽게 대응된다.이진 트리 구현#include #include template class TreeNode{ public: TreeNode(T data) { this->data = data; } T data; TreeNode* left..

트리 (Tree)트리의 정의트리는 한 개 이상의 노드로 이루어진 유한 집합으로서노드 중에는 루트(root)라고 하는 노드가 하나 있고나머지 노드들은 n개의 분리 집합 T1, T2, ..., Tn으로 분할 될 수 있다. 이때, 분리 집합 T1, T2, ..., Tn은 각각 하나의 트리이며 루트의 서브트리라고 한다.트리의 구조 및 용어트리 용어차수(degree): 어떤 노드의 자식 개수리프(leaf) 또는 단말(terminal) 노드: 차수가 0인 노드자식(children): 어떤 노드 X의 서브트리의 루트들부모(parent): 어떤 노드 X형제(sibling): 부모가 같은 자식들트리의 차수(degree of tree): 그 트리에 있는 노드의 최대 차수조상(ancestor): 루트에서 그 노드까지의 경로..