- 그리디 알고리즘이란,
- 단순하면서 강력한 문제 해결법
- 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향을 고려하지 않음
- 그리디 알고리즘은 기준에 따라 좋은 것을 선택하므로, ‘가장 큰 순서대로’ 혹은 ‘가장 작은 순서대로’와 같은 기준을 제시해야함
- 그리디 알고리즘은 정렬 알고리즘과 짝을 이뤄 자주 출제됨
- Dijkstra Algorithm ( in Greedy )
- 특정 노드에서 시작해 모든 노드까지 도착할 수 있는 가장 짧은 경로들을 탐색하며 모든 노드의 최소 경로를 구함
- 단방향, 양방향(사이클) 모두 사용할 수 있음
- 다익스트라 알고리즘은 BFS 방식과 유사하며 시작 노드에서 모든 노드 간의 거리 값을 저장하는 배열을 생성한 다음, 인접한 노드들의 거리를 구해 가장 짧은 경로를 해당 배열에 업데이트 해나가는 방식
- 간단히 예를 들어보면 A→C로 갈 때 A→B→C 로 가는 경로의 가중치 합이 A→C의 가중치 합보다 작다면 B를 거쳐가는 경로를 선택하는 알고리즘
➰ References
https://brownbears.tistory.com/554
이것이 취업을 위한 코딩 테스트다 with 파이썬
