🏖️ jcowwk's develop

그리디 알고리즘 - 크루스칼, 프림(최소 신장 트리)그리디 알고리즘의 최소 신장 트리 알고리즘인 크루스칼과 프림 알고리즘에 대해서 공부한 내용 정리 입니다 ! 1. 최소 신장 트리2. 크루스칼 알고리즘3. 프림 알고리즘1. 최소 신장 트리그래프에서 사이클이 없이 모든 점들을 연결시킨 트리들 중 선분의 가중치 합이 최소인 트리하나의 그래프에서 여러 개의 트리가 나올 수 있다. 2. 크루스칼 알고리즘가중치가 가장 작은 선분이 사이클을 만들지 않을 때만 욕심내어 그 선분을 추가시킨다.n개의 트리들이 점차 합쳐져서 1개의 신장 트리가 된다.  위의 그래프에 크루스칼 알고리즘을 적용해보겠다. 먼저, 선분의 가중치가 작은 순서대로 정렬한다.다음으로 가장 첫 번째 선분을 고른 후, 사이클을 형성하는지 체크하고 추가시..

다익스트라(feat. 프림), 벨만-포드, 플로이드-워샬 알고리즘 개념 차이 이때까지 헷갈렸던 알고리즘의 개념을 정리해봤습니다 ! 1. 다익스트라 알고리즘(feat. 프림 알고리즘) 2. 벨만-포드 알고리즘 3. 플로이드-워샬 알고리즘 1. 다익스트라 알고리즘(feat. 프림 알고리즘) 다익스트라 알고리즘은 하나의 정점에서 모든 정점으로 가는 최단 거리를 구한다. 프림 알고리즘도 그리디 방식으로 간선을 선택한다. 프림 알고리즘은 모든 정점을 사이클없이 이을 때의 최소 비용을 구한다. 각 정점에 자신과 연결된 간선의 가중치를 저장하여 최소 비용을 업데이트한다. 다익스트라 알고리즘은 각 정점에 시작점으로부터의 경로를 저장하여 시작 정점이 바뀔 때마다 다른 결과값이 저장된다. 말로만 하면 이해가 안될 수 있기..