[TIL] Graph Theory Algorithms (유데미)

AI agent 를 하다가 MongoDB를 하다가 알고리즘을 보고 있네요.

공부가 자꾸 샛길로 새고 있습니다. 정체기인가 봅니다.

각설하고… 알고리즘 공부를 제대로 안 하고서 SW 엔지니어라며 살았네요.

반성하는 차원에서 그래프 알고리즘을 비주얼라이제이션으로 알려주는 강의를 들었습니다.

https://www.udemy.com/course/graph-theory-algorithms/

각 알고리즘이 어디에 쓰는 물건인지, 어떤 아이디어로 어떻게 구현한 것인지 쉽고 정확히 알려줍니다.

강의 내용은 클래식 그래프 이론과 네트웍 플로우의 두 부분으로 나뉘어 있습니다.

그래프이론

dfs, bfs 의 원론으로 시작해서 Dijkstra (최적 경로 찾기), Bellman-Ford (가중치없는 최단경로 찾기), Floyd-Warshall (가중치없는 모든 점 사이의 최단경로 구하기), Tarjan (strongly connected components 구하기) 을 설명합니다. Travelling Salesman Problem 에서 DP 의 개념과 유효성, DP를 쓰더라도 25개 노드 이하에서만 유용하다는 설명 등이 곁들여집니다. 오일러 한붓그리기가 dfs 로 O(N)으로 가능한 것을 보여줍니다.

네트웍 플로우

Ford-Fulkerson (dfs 반복의 총 흐름량 구하기), Bipartite Matching (두 그룹간의 매칭) 문제로 변환하면 다양한 문제를 해결할 수 있음을 보여줍니다. 흐름량 구하기 알고리즘의 개선버전들인 Edmond Karp, Capacity Scaling, Dinic 알고리즘 등을 소개합니다.

실습하기는 좋은 강의가 아니라, 실습용 강의는 따로 찾아서 들어야 할 것 같습니다.