자료구조

1. Linked List란? Linked list(연결 리스트)는 메모리 공간에서 특정 위치를 불연속적으로 점유하는 데이터 element의 선형 집합이다. array와 달리 데이터들의 메모리 공간이 연속적이지 않기 때문에 한 노드 안에 데이터와 함께 다음 데이터의

BST(Binary Search Tree, 이진 탐색 트리)는 root 노드의 값보다 작은 값은 왼쪽 자식에, 큰 값은 오른쪽 자식에 저장되어 있는 서브 트리들로 구성되어 있는 트리이다. 모든 노드가 최대 2개의 자식 노드를 가지며, 중복된 값은 허용되지 않는다.BST

1. Graph란? Graph(그래프)는 vertex(정점, 노드)와 각 vertex들을 잇는 edge(간선)의 집합이다. 한 vertex는 여러 edge들을 가질 수 있으며, edge에 방향성이 있어 한 방향으로만 이동할 수 있는 그래프를 directed graph,

BFS(Breadth-First Search, 너비 우선 탐색)는 방문한 vertex와 인접한 vertex를 queue에 넣고 FIFO 순서로 탐색하는 탐색 방식이다.트리에서 BFS 방식으로 탐색을 하면 같은 계층에 있는 노드를 우선으로 탐색한다.왼쪽 그림과 같은 그래

Kruskal's Algorithm(크루스칼 알고리즘)은 그래프를 공부할 때 함께 배웠던 minimum cost spanning tree(최소 스패닝 트리)를 구하는 방법 중 하나이다.간단히 설명하면, 그래프의 edge를 모두 제거한 후, 각 edge의 cost를 오름

Prim's Algorithm(프림 알고리즘)은 그래프를 공부할 때 함께 배웠던 minimum cost spanning tree(최소 스패닝 트리)를 구하는 방법 중 하나이다.이 알고리즘에서는 한 노드에서 시작하여, 그 노드의 edge 중 cycle을 만들지 않으면서

Sollins' Algorithm(솔린 알고리즘)은 그래프를 공부할 때 함께 배웠던 minimum cost spanning tree(최소 스패닝 트리)를 구하는 방법 중 하나이다.이 알고리즘에서는 cost가 작은 순으로 edge를 연결하여 component를 만들고,

Dijkstra's Algorithm(다익스트라 알고리즘)은 각 edge에 cost가 있는 direct graph에서 한 vertex에서 출발하여 다른 모든 vertex까지 도달하는 최단 경로를 찾는 알고리즘(Single Source All Destination)이다.

1. Bellman-Ford Algorithm이란? Bellman-Ford Algorithm(벨먼-포드 알고리즘)은 각 edge에 cost가 있는 direct graph에서 한 vertex에서 출발하여 다른 모든 vertex까지 도달하는 최단 경로를 찾는 알고리즘(Si

Winner Tree 1. Winner Tree란? Winner Tree(승자 트리)는 n개의 external node와 n-1개의 internal node로 이루어진 complete binary tree이다. Winner tree는 토너먼트의 대진표라고 생각하면 되는

Quick Sort(퀵 정렬)은 배열을 정렬하는 방법 중 하나이다. 평균적으로 가장 빠른 정렬이기 때문에 퀵 정렬이라는 이름이 붙었다. 그러나 항상 퀵 정렬이 가장 빠른 것은 아니다.(정렬된 리스트에서는 오히려 오래 걸린다.)위와 같은 배열을 오름차순으로 정렬하고자 한