Data Structure – Bellman Ford Algorithm
최단경로 알고리즘 에지에 가중치가 주어진 방향 그래프에서 경로의 길이는 경로 상에 있는 에지 가중치 합이다.이 합이 가장 작을 때 ‘최단 경로’라고 한다. […]
Month: June 2021
Data Structure – Dijkstra Algorithm
최단경로 알고리즘 에지에 가중치가 주어진 방향 그래프에서 경로의 길이는 경로 상에 있는 에지 가중치 합이다.이 합이 가장 작을 때 ‘최단 경로’라고 한다. […]
Data Structure – Prim Algorithm
MST: 프림 알고리즘 ‘부분 트리에 속한 정점’과 ‘인접한 정점’ 사이의 에지 중 가중치가 최소인 에지를 선택한다. n-1개의 에지가 선택될 때까지 진행한다. prim으로 […]
Data Structure – Kruskal Algorithm
크루스칼 알고리즘 가중치가 작은 순서대로, 에지를 하나씩 추가하며 MST를 만든다. Cycle이 만들어지면 해당 에지는 버린다. 이를 n-1개의 에지가 만들어질 때까지 진행한다. MST: […]
Data Structure – Heap (Algorithm)
힙(Heap) 각 노드에 저장되어 있는 값이 자식 노드에 저장되어 있는 값보다 크거나 같은 완전 이진 트리 (최대 힙)각 노드에 저장되어 있는 값이 […]
Data Structure – Union-Find (경로압축 및 가중법칙)
Union-Find (유니온 파인드) Union: 원소 x가 속한 부분 집합과 원소 y가 속한 부분 집합의 합집합을 구한다.Find: 원소 x가 속한 부분 집합을 찾는다. […]
Data Structure – BFS (adjacency list & adjacency matrix)
BFS (너비 우선 탐색) 먼저 v를 방문한 후, v에 인접한 정점을 차례로 방문한다. 다음으로 두 번째 방문한 정점과 인접한 정점을 방문하고, 이후 세 […]
Data Structure – DFS (adjacency list & adjacency matrix)
DFS (깊이 우선 탐색) 먼저 v를 방문한 다음 v에 인접한 정점 중에 아직 방문하지 않은 정점 w를 찾아서 w에 대한 DFS를 재귀적으로 […]