알고리즘) 프림 크루스칼

 

---

 

 

 

 

• 방법 1 (단순하게): 그냥 새로운(더 싼) 정보를 힙에 또 넣습니다. 나중에 힙에서 뽑을 때 이미 가본 곳이면 무시하면 됩니다. (구현은 쉽지만 힙이 커질 수 있음)
• 방법 2 (똑똑하게): 힙 안에 들어있는 기존 정보를 찾아서 값을 바꿉니다.
  • 그러려면 "어느 녀석이 힙의 몇 번째 칸에 있는지"를 따로 기록해둬야 합니다(인덱스 유지).
  • 값이 바뀌었으니 힙의 순서가 망가지지 않게 위아래로 자리를 옮겨주는 작업(up/down logic)이 필요합니다.

 

 

 

 

 

 

 

 

 

프라임이

 

 

 

 

 

 

 

 
 

 
 
 

프림

 

 

 

---

1. 탐욕적인 방법 (Greedy Method)의 개요

탐욕적인 방법은 분할 정복법, 동적 프로그래밍에 이어 배우는 세 번째 알고리즘 설계 기법입니다.

• 기본 개념: 여러 가지 옵션(선택지)이 있을 때, 그 순간에 가장 좋다고 생각되는 답을 선택하여 최종적인 해답에 도달하는 방법입니다.
• 최적화 문제: 가장 길이가 긴 것, 혹은 가장 짧은 것 등을 찾는 최적화 문제를 풀 때 주로 사용됩니다. 전체를 고려하기보다 현재 시점에서 최적인 답을 하나씩 모아가는 방식입니다.
• 검증의 필요성: 순간순간의 최선의 선택이 전체적으로도 정답이라는 보장이 없습니다. 따라서 그리디 알고리즘으로 구한 답이 정말 최적해인지 반드시 **증명(검증)**하는 과정이 필요합니다.
• 설계 절차:
  1. 선정 과정: 현재 상태에서 가장 좋다고 생각되는 답을 선택합니다.
  2. 적절성 검사: 선택한 답이 문제의 조건을 만족하는지(해답이 될 수 있는지) 검사합니다.
  3. 최적성 증명: 최종적으로 모인 답들이 정말 최적인지를 증명합니다.

탐욕적인 방법의 예: 거스름돈 동전 개수 최소화

• 문제: 거스름돈을 줄 때 동전의 개수를 최소로 하여 돌려주는 방법.
• 그리디 전략: 가장 단위가 큰 동전부터 우선적으로 내어줍니다. (예: 160원 → 100원 1개, 50원 1개, 10원 1개 = 총 3개)
• 함정(예외): 만약 120원짜리 기념 주화가 있다면?
  • 그리디 방식: 120원(1개) + 10원(4개) = 총 5개.
  • 최적의 답: 100원(1개) + 50원(1개) + 10원(1개) = 총 3개.
  • 이처럼 그리디는 동전 체계에 따라 최적해를 구하지 못할 수도 있으므로 검증이 필수적입니다.

 
 
 

 
 

 
프림 시간복잡도

 

 
 

 

 
 

 

 
 

 
 
 

 
 
 

정렬이 왜 nlogn인지

 
 
 

 

 
크루스칼

 
 

 
 
 
 
민힙

 
 
 
 
 
 

 
 

 
 
 
 
 
 
 

 
 
 

 
 
 
 

initial(n);

• 의미: Union-Find를 위한 초기화입니다. 개의 정점 각각을 "자기 자신만 있는 독립된 섬"으로 만듭니다. 처음에는 아무 정점도 연결되지 않은 상태입니다.