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

수강한 강의

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 => 다른 정점까지 최소 이동 횟수도 계산 가능

Dijkstra 알고리즘
그래프는 가중치가 0 이상인 그래프에서 시작점에서 모든 점까지의 최단 거리가 구해진다.
시간 복잡도는 O(E log V)
dist[i] = 시작점에서 i번 정점까지 가능한 최단거리
자료구조는 시작점에서 어떤 정점까지 해당 거리만에 갈 수 있다는 걸 알 수 있게 하는 자료구조

Dijkstra 알고리즘 과정
1. dist 배열 초기화, 시작 점이면 0 아니면 무한대
2. 자료 구조에 시작 점을 추가한다.
3. 자료구조에서 시작점에서 해당 정점까지 가장 작은 거리를 갖는 자료 (v, d)를 뽑는다.
4. dist[v] < d 인 가치가 없는 정보이면 폐기한다.
5. 시작점 S에서 정점 v까지의 거리가 d,
정점 v에서 정점 w까지의 거리가 c,
시작점 S에서 정점 w까지의 거리가 dist[w] 일 때,
d + c < dist[w]이면 dist[w]에 새로운 d + c 값을 업데이트해준다.
6. 자료 구조가 비면 끝난다.

Dijkstra 시간 복잡도 계산
3번의 가장 작은 거리를 갖는 자료 (v, d)를 추출하는 과정과 5번의 거리 비교를 통해 새로운 정보를 자료구조에 추가하는 작업이 Dijkstra의 시간 복잡도를 계산한다. Min Heap / Priority Queue를 사용하면 3번 과정이 O(log E), 5번 과정이 O(log E)이고 모든 정점에서 각 정점과 관련된 Edge에 대해서 3 ~ 5번 과정을 반복하므로 O((log E + log E) * E)의 시간 복잡도 이므로 O(E log E)의 시간 복잡도를 가진다.

수강 인증샷

https://bit.ly/37BpXiC

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

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