패스트캠퍼스 챌린지 13일차

---

Ch 17. 그래프 이해와 자료 구조

01. 그래프 이해와 자료 구조

Ch 18. 그래프 기본 탐색 알고리즘

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

02. 너비 우선 탐색(BFS) (2)

03. 깊이 우선 탐색(DFS)

---

오늘은 그래프와 그래프 기본 탐색 알고리즘인 너비 우선 탐색과 깊이 우선 탐색에 대해 배웠다. 학원에서 교육받을 때도 느낀 거지만 정보처리기사 공부해두길 잘했다는 생각이 든다. 물론 공공기관 관련 프로젝트에 참여할 때, 정보처리기사 자격증이 있으면 프로젝트 참가자의 급여를 높게 책정할 수 있어 SI 회사가 아니면 필요 없다고 들었고, 학원 강사님께서도 공부할 필요 없다고 하셨다. 나도 오늘 그래프를 배우면서 정보처리기사를 공부할 때, 잘못 공부했구나 싶지만 그래도 학원 강의를 들으면서도 도움이 되었고, 이렇게 다른 강의를 찾아 들을 때도 봤던 것들이 많아 전반적인 CS 지식을 쌓는 데 좋다고 생각한다. 물론 진짜 개발자가 되려면 각각의 과목을 깊게 공부해야 하겠지...

  그래프는 실제 세계의 현상이나 사물을 노드(Node) 또는 정점(Vertex)과 간선(Edge)로 표현하기 위해 사용한다고 한다. 나는 정보처리기사를 공부할 때 트리와 비교하면서 트리는 사이클이 없는 것, 그래프는 사이클이 있는 것이라고 비교하면서 공부했는데 사실 트리도 그래프의 한 종류이다. 그래프는 종류에 따라 무방향 그래프와 방향그래프, 연결 그래프와 비연결 그래프, 사이클과 비순환 그래프, 완전 그래프가 있다. 나의 구분 방법에 따르면 비순환 그래프가 있기 때문에 잘못 공부한 것이다. 이렇게 다시 배울 수 있어 다행이다..^^!

그 다음으로 너비 우선 탐색(Breath First Search)와 깊이 우선 탐색(Depth First Search)가 있다. 너비 우선 탐색은 트리를 예로 들자면 루트 노드부터 자식 노드를 탐색하되, 형제 노드가 있다면 같은 레벨에 있는 형제 노드를 먼저 순회하고 자식 노드를 탐색하는 방식이다. 반면 깊이 우선 탐색은 루트 노드부터 자식 노드를 먼저 탐색한 뒤 다른 형제 노드를 탐색하는 방식이다. 각각의 탐색 방법을 코드로 구현하는 과정에서 다른 클래스나 자료구조를 사용할 수 있지만 강사님께서는 알고리즘에 중점을 둔 수업이므로 기존에 배웠던 ArrayList와 HashMap을 이용해서 가르쳐주셨다. 너비 우선 탐색은 FIFO방식의 큐를, 깊이 우선 탐색은 LIFO방식의 스택을 이용해 구현하셨다. 그래프를 코드로 작성하는 게 감이 잡히지 않았는데 강사님께서도 처음 알고리즘을 공부할 때 같은 알고리즘만 이틀 내내 생각할 정도로 어려웠으니 걱정하지 말라고 하셨다. 나도 혼자 코드로 작성하면서 다시 해봐야겠다.

 

 

---

https://bit.ly/3FVdhDa

수강료 100% 환급 챌린지 | 패스트캠퍼스

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