728x90

그래프 문제가 나왔을 때 어떤 자료구조, 알고리즘을 사용해야 할 지 감이 안 잡히는 경우가 많다.
그럴 때 참고하면 좋을 것 같다.
- BFS
- Queue 사용
- 출발지 -> 목적지 사이의 최소 비용 구하기
- 가중치가 없는 그래프 일 때
- Dijkstra
- Priority Queue 사용
- 출발지 -> 모든 정점의 최소 비용 구하기
- 가중치가 음수일 수 없다.
- Floyd-W
- DP 사용
- 모든 정점 -> 모든 정점의 최소 비용 구하기
- 가중치 상관 없음
728x90
'알고리즘 > 알고리즘' 카테고리의 다른 글
[python] 이분 탐색 / Binary Search / LIS / 가장 긴 증가하는 부분 수열 / 직접 구현 / bisect (0) | 2021.09.02 |
---|
댓글