230927 [Day7] JavaScript 주요 문법 (6)

자료구조&알고리즘 - BFS, DFS

 

 

BFS(너비 우선 탐색)

• 그래프 탐색 알고리즘으로 같은 깊이에 해당하는 정점부터 탐색하는 알고리즘
• BFS의 특징
  • Queue를 이용하여 구현할 수 있다.
  • 시작 지점에서 가까운 정점부터 탐색한다.
  • 선의 수일 때 BFS의 시간복잡도는 O(V+E)다.

 

DFS(깊이 우선 탐색)

• 그래프 탐색 알고리즘으로 최대한 깊은 정점부터 탐색하는 알고리즘
• DFS의 특징
  • Stack을 이용하여 구현할 수 있다.
  • 시작 정점에서 깊은 것부터 찾는다.
  • V가 정점의 수, E가 간선의 수일 때 DFS의 시간복잡도는 O(V+E)다.

 

자료구조&알고리즘 - 그리디

• 자판기는 남은 금액을 어떻게 반환할까?
• 매 선택에서 지금 이순간 가장 최적인 답을 선택하는 알고리즘
• 최적해를 보장해주지 않음

 

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