그리디 · 다익스트라 · 최소신장트리

---

1) 그리디 알고리즘 (Greedy)

개념

• 한 순간 최선(탐욕) 선택이 전체 최적해로 이어진다고 가정하고 푸는 방법.

• 성립 조건:

  1. 탐욕 선택 속성(현 시점 최선이 전체 최선으로 확장 가능)
  2. 최적 부분 구조(부분 문제의 최적해로 전체 최적해 구성)

전형 문제

• 동전 거스름: 큰 동전부터(단, 한국 화폐처럼 특정 체계에서만 성립)
• 회의실 배정/활동 선택: 끝나는 시간 오름차순 정렬 → 차례대로 선택
• 로프 문제: 하중 오름차순 정렬 후 케이스별 최대 하중 검사
• 분할 가능 배낭( Fractional Knapsack ): 가치/무게 비율 내림차순 (0/1 배낭은 그리디 X)

기본 템플릿

1) 정렬 기준 정의 (예: 끝나는 시간, 비용/가치 비율 등)
2) 조건을 만족하는 한에서 현재 최선의 후보를 고른다
3) 선택으로 인한 상태(용량/시간/집합)를 갱신한다

복잡도 & 주의

• 대부분 정렬 O(n log n) + 단순 선형 스캔 O(n)
• 반례 확인 필수: 동전 단위가 임의면 최적 보장 X, 0/1 배낭도 X

---

2) 다익스트라 알고리즘 (Dijkstra)

목적/전제

• 단일 시작점 최단 거리 (Single-Source Shortest Path)
• 간선 가중치 ≥ 0 (음수 간선 있으면 사용 불가 → 벨만–포드를 사용)

핵심 아이디어

• 방문하지 않은 정점 중 현재까지 거리 최솟값을 뽑아 확정(그리디),
• 그 정점으로부터 완화(relaxation) 반복

우선순위 큐 버전 (의사코드)

dist[] = INF; dist[src] = 0
pq = min-heap of (dist, node)
push (0, src)

while pq not empty:
  (d, u) = pop
  if d > dist[u]: continue     // stale entry skip
  for (v, w) in adj[u]:
    if dist[v] > dist[u] + w:
      dist[v] = dist[u] + w
      push (dist[v], v)

복잡도

• 인접 리스트 + 이진 힙: O((V + E) log V)
• 밀집 그래프에서 인접 행렬 & 단순 스캔: O(V²)

자바 미니 스니펫

class Edge { int to, w; Edge(int t, int w){ this.to=t; this.w=w; } }
List<Edge>[] g;
int[] d; boolean[] vis;

void dijkstra(int s){
    Arrays.fill(d, Integer.MAX_VALUE);
    d[s] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
    pq.offer(new int[]{0, s});
    while(!pq.isEmpty()){
        int[] cur = pq.poll();
        int dist = cur[0], u = cur[1];
        if(dist != d[u]) continue;
        for(Edge e : g[u]){
            if(d[e.to] > d[u] + e.w){
                d[e.to] = d[u] + e.w;
                pq.offer(new int[]{d[e.to], e.to});
            }
        }
    }
}

체크리스트

• 음수 간선 없음
• 우선순위 큐 사용 시 stale 엔트리 무시
• 도달 불가 정점은 INF

---

3) 최소 신장 트리 (MST: Minimum Spanning Tree)

개념

• 연결 무방향 가중 그래프에서 모든 정점을 잇는 사이클 없는 부분 그래프 중
• 간선 가중치 합이 최소인 트리

대표 알고리즘 2종

A. Kruskal (간선 중심)

• 간선 가중치 오름차순 정렬 → 작은 것부터 사이클 안 만들면 채택
• 사이클 판별: 유니온-파인드(Disjoint Set)
  -> 이번에 배운것은 이것

의사코드

sort edges by weight asc
init DisjointSet (parent/rank)

for each edge (u, v, w) in edges:
  if find(u) != find(v):
    union(u, v)
    take edge (u, v, w)

복잡도: 정렬 O(E log E) + 유니온파인드 거의 상수 → O(E log E)

B. Prim (정점 중심)

• 임의의 정점에서 시작, 트리에 가장 싸게 연결되는 간선을 반복적으로 확장
• 구현: 우선순위 큐(간선 비용 기준)

의사코드

pick any start s
visited[s] = true; push all (w, s->v) into pq

while pq not empty and picked < V-1:
  (w, u->v) = pop min
  if visited[v] continue
  visited[v] = true; take (u, v, w)
  push all (w', v->x) where !visited[x]

복잡도: 인접 리스트 + 힙 O(E log V), 인접 행렬 + 선형스캔 O(V²)

Kruskal vs Prim 선택 가이드

• 간선이 많지 않은 희소 그래프, 간선 리스트가 이미 주어진 경우 → Kruskal
• 정점 수가 크고 인접 리스트 보유, 시작점 무관/연결 보장 → Prim
• 둘 다 MST 비용 동일 (그래프가 연결이라면)

유니온-파인드 미니 스니펫 (Java)

class DSU {
    int[] p, r;
    DSU(int n){ p = new int[n]; r = new int[n]; for(int i=0;i<n;i++) p[i]=i; }
    int find(int x){ return p[x]==x ? x : (p[x]=find(p[x])); }
    boolean union(int a, int b){
        a = find(a); b = find(b);
        if(a==b) return false;
        if(r[a] < r[b]) { int t=a; a=b; b=t; }
        p[b] = a;
        if(r[a]==r[b]) r[a]++;
        return true;
    }
}

---

빠른 요약 표

주제	목적	전제/조건	핵심 아이디어	전형 복잡도
Greedy	전역 최적 근사/도출	탐욕 선택 + 최적 부분 구조	“현재 최선”을 반복 선택	보통 정렬 O(n log n) + O(n)
Dijkstra	단일 시작 최단거리	비음수 간선	가장 가까운 정점부터 확정(완화)	O((V+E) log V)
MST–Kruskal	모든 정점 연결 최소 비용	무방향·연결	간선 정렬 + 유니온파인드	O(E log E)
MST–Prim	모든 정점 연결 최소 비용	무방향·연결	PQ로 트리 바깥 최소 간선 추가	O(E log V)

---