OILAT

수강한 강의 Part 3. 알고리즘 유형별 풀이 Chapter 02 알고리즘 - 최단 경로 (Shortest Path) 학습 후기 최단거리란 그래프의 시작 지점에서 다른 지점까지의 최단거리 최단거리 알고리즘 이름 간선의 가중치 시작점 도착점 시간복잡도 BFS 모두 1 한 정점 모든 정점 O(V + E) Dijkstra >= 0 한 정점 모든 정점 O(E log V) Floyd-Warshall 제약없음 모든 정점 모든 정점 O(V ^ 3) Bellman-Ford 제약없음 한 정점 모든 정점 O(V * E) SPFA 제약없음 한 정점 모든 정점 O(V * E) A* >= 0 한 정점 한 정점 O(b ^ d) 탐색 = 시작점에서 간선을 0개 이상 사용해서 갈 수 있는 정점들은 무엇인가? DFS/BFS BFS ..

수강한 강의 Chapter 20 그래프 고급 탐색 알고리즘 - 최단 경로 알고리즘 이해 학습 후기 최단 경로 알고리즘.. 강의를 다 듣고 학습후기를 쓰는데 오늘 강의는 진짜 어려운 것 같다. 하지만 알고리즘 테스트를 통과하기 위해서는 꼭 이해하고 구현할 수 있도록 해야 하기 때문에 강의 들을걸 잘 정리하고 넘어가자 최단 경로 문제란 두 노드를 잇는 가장 짧은 경로를 찾는 문제다. 가중치 그래프에서 간선의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적이다. 최단 경로 문제 종류 1. 단일 출발 최단 경로 문제: 특정 노드 A에서 출발, 그래프 내 모든 다른 노드에 도착하는 가장 짧은 경로를 찾음. 2. 단일 도착 최단 경로 문제: 모든 노드에서 출발, 특정 노드 A로 도착하는 가장 짧은 경로를 찾..