Spanning Tree, 신장트리란?그래프에 포함된 모든 정점(vertex)들을 포함하는 부분 그래프이다. (즉, 그래프 구성 edge만이 달라짐)모든 vertex는 적어도 하나의 edge에 연결되어 있다.트리이므로 cycle이 존재해서는 안 된다.주어진 하나의 그래프에 대해 다양한 신장트리가 존재할 수 있다.vertex의 개수 v에 대해 (v-1)개의 edge를 가진다.신장 트리는 DFS, BFS 등을 이용하여 구성할 수 있다. (탐색을 통해 방문한 정점 순서대로 신장 트리 구성) Minimum Spanning Tree, 최소 비용 신장트리가중치가 부여된 무방향 그래프에서, 신장 트리의 비용이 가장 적은 spanning tree를 최소 비용 신장트리라 한다.즉, 신장트리를 구성하는 edge들의 가중치..

그래프의 정의그래프는 연결되어 있는 원소 간 관계를 표현하는 자료구조이다.실세계의 지하철 노선도, 컴퓨터 네트워크 등의 예를 생각하면 된다.그래프의 구성 요소 그래프는 vertex(정점)과 정점들을 잇는 edge(간선)으로 구성된다.위 사진에서 0,1,2,3,4가 정점에 해당하고, 정점을 잇는 선이 간선이다. 그래프 G가 있을 때, G에 포함된 모든 정점들의 집합을 V(G), 모든 간선들의 집합을 E(G)라고 표기한다.G = (V,E)라고 쓰기도 한다. 그래프의 종류그래프는 무방향성 그래프와 방향성 그래프로 나뉜다.무방향성 그래프무방향성 그래프는 각 vertex가 서로 연결됐음만을 나타내는 그래프이다.이 때 vertex 0과 1에 대해서 (0,1)과 (1,0)는 동일한 ..

힙의 정의 A Heap is a special Tree-based data structure in which the tree is a complete binary tree. 힙은 트리, 그 중 완전 이진 트리를 기반으로 한 자료구조이다.힙이 되기 위해서는 완전 이진 트리이면서, 부모 노드가 가진 데이터 값은 자식 노드가 가진 데이터 값보다 무조건 크거나(이 경우 Max Heap), 혹은 작아야(이 경우 Min Heap) 한다.  위 사진을 보면, Max Heap의 경우 모든 부모 노드는 자식 노드보다 데이터의 값이 크고 Min Heap의 경우 모든 부모 노드가 자식 노드보다 데이터의 값이 작은 것을 확인할 수 있다. 따라서 루트 노드에 Min Heap의 경우 항상 트리의 최솟값이, Max Meap의 경우..

이진 트리 정의트리 중, 모든 노드의 차수(degree)가 2가 넘지 않는 것을 이진트리라 한다.유한 개의 노드들의 집합으로서노드 수가 0이거나 하나의 root 노드와 왼쪽 서브트리, 오른쪽 서브트리로 구성되어 있으며, 각 서브트리는 다시 이진트리다. 이진트리 종류편향 이진 트리 (Skewed Binary Tree): 트리의 노드가 왼쪽/오른쪽 중 한 쪽으로만 치우쳐진 트리이다.포화 이진 트리 (Full Binary Tree): 트리의 깊이가 k일 때, 2^k-1 개의 노드를 가진 이진트리이다. (= 트리의 깊이까지 노드가 모두 꽉 차 있는 상태의 트리)완전 이진 트리 (Complete Binary Tree): 마지막 레벨을 제외한 모든 레벨은 노드로 꽉 차 있으며, ..

트리의 정의사이클 없이 모든 정점이 연결되어 있는 그래프이다. (따라서 정점이 V개면 간선의 개수는 V-1개)노드(정점)와 노드를 연결하는 링크(간선)들로 구성되어 있다.보통 루트 노드가 존재하는 트리를 트리라 부르고 사용한다.Root(루트)라고 불리는 노드가 하나 존재한다.루트 노드는 0개 이상의 자식 노드를 가진다.나머지 노드들은 n(>=0)개의 서브 트리(부분집합)로 이루어져있다.트리 안에 서브 트리가 있고, 서브 트리 안에 또 서브 트리가 있는 재귀적 자료구조이다. 위 이미지에서 루트 노드는 2이며, 7과 5를 자식 노드로 가진다.각 7과 5노드를 시작으로 서브트리가 구성되어 있으며, 각 서브트리에서 7과 5는 루트 노드의 역할을 한다. 트리는 자료의 계층적 구조..

큐의 정의데이터의 삽입과 삭제가 서로 다른 곳(top,rear)에서 발생하는 선형구조이다.- 데이터 삽입 발생 위치 : rear- 데이터 삭제 발생 위치 : front 가장 먼저 들어온 데이터를 front가 참조하며 데이터 삭제 시 가장 먼저 삭제된다.이를 FIFO(First In First Out) 구조라고 한다. 큐의 연산enqueueQueue의 가장 뒤쪽(rear)에 데이터를 삽입한다.dequeueQueue의 가장 앞쪽(front)의 데이터를 삭제하고 반환한다.peekQueue의 가장 앞쪽(front)의 데이터를 반환한다.isFullQueue가 꽉 차있는지 확인한다.isEmptyQueue가 비어있는지 확인한다. 큐의 구현 큐의 구현은 스택과 마찬가지로 ..

스택의 정의데이터의 삽입과 삭제가 top이라 불리는 한쪽 끝에서만 발생하는 선형 구조이다. 가장 늦게 들어간 데이터가 가장 먼저 삭제되고, 가장 먼저 들어간 데이터가 가장 늦게 삭제된다.이를 LIFO(Last In First Out)구조 , 혹은 FILO(First In Last Out)구조라고 할 수 있다.  스택의 연산push스택의 가장 위(top)에 데이터를 삽입한다.pop스택의 가장 위(top) 데이터를 삭제한다.peek스택의 가장 위(top) 데이터를 반환한다.isEmpty스택이 비어있는지 확인한다.isFull스택이 꽉 차있는지 확인한다.getSize스택에 현재 저장된 데이터의 수를 반환한다. 스택의 구현스택을 구현하는 방법에는 두 가지 방법이 있다.배..