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

---

Part 2. 알고리즘 이론

Ch 20. 그래프 고급 탐색 알고리즘

01. 최단 경로 알고리즘 이해 (1)

02. 최단 경로 알고리즘 이해 (2)

03. 최단 경로 알고리즘 이해 (3)

---

오늘은 최단 경로 알고리즘과 최단 경로 알고리즘의 대표적인 예인 다익스트라 알고리즘에 대해 배웠다. 먼저 최단 경로 문제란 두 노드/정점을 잇는 간선 중 가장 짧은 경로를 찾는 문제이다. 주로 가중치 그래프에서 간선의 가중치 합이 가장 작은 경로를 찾아야 한다. 최단 경로 문제는 단일 출발, 단일 도착, 단일 쌍, 전체 쌍 최단 경로가 있다. 이 중 특정 노드에서 출발하여 다른 모든 노드에 도착하는 가장 짧은 경로를 찾는 단일 출발 최단 경로 문제가 다익스트라 알고리즘에 해당한다. 어제 챌린지 글에도 썼지만 다 익스트라 알고리즘은 기사 공부할 때, 뭔지도 모르지만 이름이 하도 신기해서 외웠던 기억이 난다. 
 
 다익스트라 알고리즘은 너비 우선 탐색과 유사하다. 루트 노드에서 모든 자식 노드를 탐색한 후 다음 깊이로 내려갔던 것처럼 다익스트라 알고리즘도 출발해야 하는 특정 노드에서 갈 수 있는 노드별로 가중치를 구하고, 노드별로 다시 다음 노드로 이동하는 방식이다. 여태까지 모든 수업의 내용이 그러하듯 다익스트라 알고리즘을 코드로 구현하는 방법에는 여러 가지가 있지만 이번에는 우선순위 큐와 HashMap, ArrayList를 이용하여 구현했다. 크기를 비교하고 정렬하기 위해 전 수업에서 배웠던 Comparable인터페이스와 compareTo메소드를 이용했다. 이걸 보니까 부스트코스 수업이 생각난다. 그것도 다 들어야 하는데.. 아련... 아무튼 이 구조를 이해하기 위해서는 직접 A4 용지에 그려보면서 이해해보라고 하시길래 해봤다. 이렇게 하니까 어제 들은 탐욕 알고리즘보다 더 금방 이해되는 느낌이다. 중요한 건 코드로 구현하는 거니 코드를 다시 봐야겠지만 말이다....

 

 

---

https://bit.ly/3FVdhDa

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

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