코딩테스트 - 패스트캠퍼스 챌린지 16일차

수강한 강의
Chapter 18 그래프 기본 탐색 알고리즘
- 너비 우선 탐색(BFS)
- 깊이 우선 탐색(DFS)

 

학습 후기
알고리즘 문제 중에서 가장 빈번하게 나오는 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)에 대한 강의를 들었다.
알고리즘을 코드로 작성하기 전 강사님이 엑셀에서 BFS와 DFS가 어떻게 동작하는지 설명해주셨다. 일단 그래프는 HashMap과 ArrayList를 사용하여 전체 그래프를 표현하였다. 그리고 HashMap의 CRUD, Create(생성), Read(읽기), Update(수정), Delete(삭제)도 알려주셨다. 이 전체 그래프를 보면서 BFS를 어떻게 구현해 나가는지 설명해주셨다.

그래프 예시

너비 우선 탐색(BFS)
BFS는 자료구조 큐를 활용하여 해당 노드에 방문한 적이 있는지 체크하는 리스트와 다음에 어느 노드를 방문해야 하는지를 담는 리스트를 가지고 구현한다.
알맞은 자료 구조와 해당 자료 구조의 함수 사용으로 정말 간단하게 구현이 가능했다.
너비 우선 탐색의 시간 복잡도는 O(V + E)로 다른 알고리즘과 다르게 N이 아닌 V와 E를 볼 수 있는데 V는 vertex, E는 edge이다. 너비 우선 탐색의 시간 복잡도는 전체 그래프에서의 노드 수와 간선 수에 영향을 받는다.
너비 우선 탐색으로 위 그래프를 탐색하면 탐색 순서는 [A, B, C, D, E, F, G, H, I, J]가 된다.

깊이 우선 탐색(DFS)
DFS는 BFS와 비슷하게 해당 노드에 방문한 적이 있는지 체크하는 리스트와 다음에 어느 노드를 방문해야 하는지를 담는 리스트를 가지고 구현하는데 BFS와는 다르게 자료구조 스택을 활용하여 구현한다.
깊이 우선 탐색의 시간 복잡도도 너비 우선 탐색과 마찬가지로 O(V + E)이다.
깊이 우선 탐색으로 위 그래프를 탐색하면 탐색 순서는 [A, C, G, F, J, I, B, E, D, H]가 된다.

수강 인증샷

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.