TIL7 - 2023.09.27

너비 우선 탐색 (BFS)

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

BFS의 특징

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

깊이 우선 탐색(DFS)

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

DFS의 특징

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

---

그리디 (Greedy)

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

그리디 알고리즘의 특징

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

---

BFS / DFS 응용하기 어렵네요.... 연휴 기간동안 공부 열심히 해야겠습니다..