[TIL] JavaScript 주요 문법(6)

BFS와 DFS

BFS(너비 우선 탐색)

• 그래프 탐색 알고리즘으로 같은 깊이에 해당하는 정점부터 탐색하는 알고리즘

BFS의 특징
- Queue를 이용하여 구현할 수 있다.
- 시작 지점에서 가까운 정점부터 탐색한다.
- V가 정점의 수, E가 간선의 수일 때 BFS의 시간복잡도는 O(V+E)다.

DFS(깊이 우선 탐색)

• 그래프 탐색 알고리즘으로 최대한 깊은 정점부터 탐색하는 알고리즘

DFS의 특징
- Stack을 이용하여 구현할 수 있다.
- 시작 정점에서 깊은 것부터 찾는다.
- V가 정점의 수, E가 간선의 수일 때 BFS의 시간복잡도는 O(V+E)다.

Gredy(그리디)

• 매 선택에서 지금 이 순간 가장 최적인 답을 선택하는 알고리즘
• 최적해를 구해주지는 않는다.

그리디 알고리즘의 특징
- 보통 최적해를 구하는 알고리즘보다 빠른 경우가 많다.
- 크루스칼, 다익스트라 알고리즘 등에 사용된다.
- 직관적인 문제 풀이에 적합하다.