그리디 알고리즘 — 매 순간 가장 좋아 보이는 선택

그리디(greedy)는 ‘욕심 많은’이라는 뜻이다. 미래를 고려하지 않고 지금 이 순간 가장 좋아 보이는 선택을 하는 알고리즘이다. 규칙이 단순한 만큼 계산은 적게 든다. 다만 그 단순함이 최적해를 저절로 보장하지는 않아서, 언제 통하고 언제 통하지 않는지를 따로 따져야 한다.

그리디 알고리즘이란

그리디 알고리즘(Greedy Algorithm) 은 답을 찾기 위해 선택을 반복하는 알고리즘 중에서 다음 두 조건을 모두 만족하는 부류를 가리킨다.

조건	설명
간단한 선택 규칙	매 단계에서 ‘비교적 간단한 방법(greedy)’으로 다음 선택을 결정한다
번복하지 않는 선택	한 번 선택한 결과는 이후 단계에서 바꾸지 않는다

즉, “지금 가장 좋아 보이는 것을 고르고, 뒤돌아보지 않는다”가 그리디의 핵심이다. 매 단계의 선택을 국소 최적(local optimum) 이라 부르며, 그리디는 국소 최적의 연속이 전역 최적(global optimum) 이 되기를 기대하는 전략이다.

---

예시 1: Selection Sort

selection sort는 그리디 알고리즘이 잘 들어맞는 대표적인 예다. 매 단계에서 ‘남아 있는 원소 중 가장 작은 것’이라는 간단한 기준으로 다음 자리를 채우고, 한 번 자리를 잡은 원소는 다시 바꾸지 않는다.

void sort(int a[], int n) {
    for (int i = 0; i < n; i++) {
        // 1. i번째 자리에 들어갈 최소 원소의 인덱스를 찾는다
        int m = i;
        for (int j = i; j < n; j++) {
            if (a[m] > a[j]) m = j;
        }
        // 2. 찾은 최소 원소를 i번째 자리로 보낸다
        int t = a[i];
        a[i] = a[m];
        a[m] = t;
    }
}

동작 방식을 정리하면 이렇다.

• 전체 배열에서 가장 작은 원소를 선택하고, 이를 맨 앞으로 보낸다.
• 다음으로 작은 원소를 그 다음 자리로 보낸다.
• 앞에 자리를 잡은 원소들은 이미 선택된 항목이고, 이후 절대 바뀌지 않는다.

매 단계의 선택 규칙은 단순하다. “남은 영역에서 최솟값을 골라 앞으로.” 그리고 그 선택은 번복되지 않는다. 그리디의 두 조건을 모두 만족한다.

selection sort의 경우, 각 단계의 국소 최적(남은 영역의 최솟값을 앞으로 보내기)이 전체 정렬이라는 전역 최적과 정확히 일치한다. 그리디가 통하는 문제다.

---

예시 2: Shortest Path

같은 그리디 전략이 항상 통할까? 그래프에서 두 정점 사이의 최단 경로를 찾는 문제를 보자.

그리디가 통하는 한 단계

위 그래프에서 S에서 출발해 다음과 같이 선택해 보자.

1. 임의의 정점 $S$에서 나가는 간선 중 가장 작은 가중치의 간선을 따라간다. 여기서는 $S \to C$ (가중치 5).
2. 이때 도착한 정점을 $C$라 하면, $S$에서 $C$까지의 최단 거리는 5 이다.

왜일까? $S$에서 나가는 다른 간선은 모두 5보다 크기 때문이다. 어떤 경로로 우회하더라도, 첫 간선의 비용이 이미 5 이상이므로 $S \to C$의 거리를 5보다 더 줄일 수 없다. 한 단계에서는 그리디가 옳다.

그리디가 무너지는 다음 단계

문제는 그 다음이다. “$C$에서 가장 작은 간선을 또 골라 나아가자”는 식으로 그리디를 계속하면 어떻게 될까?

여기서 말하는 그리디는 “현재 정점에서 가장 짧은 간선을 고른다”는 단순한 nearest-neighbor 전략이다. 거리 정보를 누적해 갱신하며 진행하는 다익스트라 같은 알고리즘과는 구분된다.

경로	총 거리
$S \to C \to D$ (그리디: 5 + 2)	7
$S \to D$ (직행: 6)	6

$C$에서 가중치 2의 간선이 가장 짧아 보이지만, 그 선택을 따라가면 전체 경로는 $5 + 2 = 7$이 된다. 실제로는 $S \to D$로 곧장 가는 6이 더 짧다. 눈앞에 보이는 가장 짧은 길만 고르는 그리디 전략은 여기서 답을 놓친다.