DFS(Depth First Search-깊이 우선 탐색)
▶ 스택, 재귀를 통한 구현이 가능하다.
BFS(Breadth First Search-너비 우선 탐색)
▶ 큐, 덱을 통한 구현이 가능하다.
▶ 최단거리를 구할 때 BFS를 사용하는데 종류는 3가지다.
▶ 다익스트라 알고리즘 - 가장 유명한 최단경로를 구하는 알고리즘으로 단일 정점의 최단 경로를 구할 수 있으며 음의 가중치를 가지고 있을 땐 사용 불가하다.
▶ 플로이드 마샬 알고리즘 - 단일 정점이 아닌 모든 정점 사이의 최단거리를 구할 수 있다.
▶ 벨만 포드 알고리즘 - 음의 가중치를 가진 경로에서도 최단거리를 구할 수 있다. (경로 추적이 가능함) 벨만 포드 알고리즘은 DP(다이나믹프로그래밍)이 사용된다.
GREEDY(탐욕법)
▶ 늘 가장 좋은 값을 찾을 때 사용되는데 이때, 조건이 그럴 수 밖에 없는 경우에만 이 알고리즘을 사용한다.
'자료구조와 알고리즘 > 알고리즘(학부과정)' 카테고리의 다른 글
| 그래프 - Graph(2. DFS in undirected graphs) (0) | 2021.12.07 |
|---|---|
| 그래프 - Graph(0. Introduction / 1. what is graph?) (0) | 2021.12.07 |
| 분할정복 - Divide and Conquer (3.2 Multiplication) (0) | 2021.10.05 |
| 분할정복 - Divide and Conquer (3.1 Recurrence relation) (0) | 2021.10.05 |
| 분할정복 - Divide and Conquer (3.0 Introduction) (0) | 2021.10.04 |