반응형 다익스트라1 [코딩 테스트] 15일차: 그리디 알고리즘 그리디 알고리즘 (Greedy Algorithm)그리디 알고리즘은 매 순간 가장 최적이라고 생각되는 해를 선택하여 문제를 해결하는 방법입니다. 이 방법은 부분적인 최적 해가 전체적인 최적 해가 될 수 있는 문제에 적합합니다.그리디 알고리즘의 주요 개념현재 시점에서 가장 좋은 선택: 각 단계에서 가장 좋은 선택을 하여 문제를 해결부분 최적 해: 각 부분 문제에서의 최적 해가 전체 문제에서도 최적 해가 되는 경우최소 신장 트리 (MST)최소 신장 트리는 그래프의 모든 정점을 포함하면서, 사이클이 없고, 간선의 가중치 합이 최소인 트리입니다. 대표적인 알고리즘으로는 크루스칼 알고리즘(Kruskal's Algorithm)과 프림 알고리즘(Prim's Algorithm)이 있습니다.크루스칼 알고리즘 (Kruska.. 2024. 9. 15. 이전 1 다음 반응형