[Day 7] JavaScript 주요 문법 (6)

Today I Learn📖

• BFS, DFS (강의)
• 그리디 (강의)

BFS

너비 우선 탐색(Breadth-First Search): 그래프 탐색 알고리즘. 같은 깊이에 해당하는 정점부터 탐색함

=> A ➡️ B - C - D ➡️ E - F ➡️ G 순서로 탐색

BFS 특징

• 큐(Queue)를 이용하여 구현
• 시작 지점에서 가까운 정점부터 탐색
• V = 정점의 수, E = 간선의 수 ➡️ 시간복잡도 = O(V+E)
  

DFS

깊이 우선 탐색(Depth-First Search): 그래프 탐색 알고리즘, 최대한 깊은 정점부터 탐색함

=> A - B - F - C ➡️ G ➡️ D - E 순서로 탐색

DFS 특징

• 스택을 사용하여 구현
• 시작 정점의 깊은 것부터 탐색
• V = 정점의 수, E = 간선의 수 ➡️ 시간복잡도 = O(V+E)
  

---

그리디

매 선택에서 지금 순간 가장 최적인 답을 선택하는 알고리즘
-> 근데 최적해를 보장하지는 X

그리디 특징

• 보통 최적해를 구하는 알고리즘보다 빠름 (보통 선행시간 소요)
• 크루스칼, 다익스트라 알고리즘에 사용됨
• 직관적 문제의 풀이법인 경우가 많음 ㅎ.ㅎ

😊오늘의 느낀점😊

그래프 알고리즘과 그리디 알고리즘 이론에 대해 다시 복귀하는 시간이었다.
오늘은 강의보다 알고리즘 풀이가 많아서, 효율적인 풀이법에 대해 고민을 많이 했다.