6일차 배운 것 정리 (1)

목차

1. BFS &DFS

1-1. BFS (너비 우선 탐색)

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

• 큐(Queue)를 이용하여 구현

• 시작 지점에서 가장 가까운 정점부터 탐색

• 정점(V), 간선(E) 일 때, 시간복잡도는 O(V+E)

• A를 방문(enQueue)
• A를 방문처리 하고(deQueue)
• A에서 연결된 노드들 방문(enQueue) - (B,C,D)

• B,C,D 차례 대로 방문
• 반복...

1-2. DFS (깊이 우선 탐색)

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

• 스택(Stack)을 이용하여 구현

• 시작 정점부터 깊은 것 부터 찾는다.

• 시간복잡도 O(V+E)

• A를 방문 (스택의 추가)
• 자식 노드 있다면, 스택에 추가 (A-B)
• 없다면 스택에서 꺼냄

2. 그리디(Greedy)