🗒 목차
- BFS, DFS
- 그리디
✅ 1. DFS, BFS
트리에서 노드의 넓이 우선으로 탐색하는가 깊이 우선으로 탐색하는가에 따라 넓이 우선 탐색(BFS)와 깊이 우선 탐색(DFS)으로 나뉜다. 두 탐색 방법모두 정점의 수가 N이고 간선의 수가 M일 때, 시간 복잡도는 O(N+M)이 된다.
출처 : 너비 우선 탐색
DFS
- Stack을 사용해서 구현한다.
- 루트 노드(또는 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법.
- 모든 노드를 방문하는 경우 이 방법을 사용한다.
BFS
- Queue를 사용해서 구현한다.
- 루트 노드(또는 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법.
- 두 노드 사이의 최단 경로 또는 임의의 경로를 찾고 싶을 때 사용한다.
✅ 2. 그리디(Greedy)
- 현재 상황에서 가장 좋은 것을 선택하는 알고리즘이다.
- 현재 상황에서 가장 좋은 것을 선택하기 때문에 그로 인해 도출되는 결과가 최적해를 보장하지 않는다.
- 직관적인 문제 풀이에 적합하다.
✅ 정리
DFS, BFS, 그리디를 사용하는 알고리즘 문제를 풀면서 Javascript로 알고리즘을 구현해보려 했으나...
아직 구현중입니다. 우선 DFS, BFS 그리디의 개념을 간단하게 정리하고 추가적으로 내용을 정리하겠습니다
