그리디 알고리즘 (Greedy Algorithm)

프로그래밍에서 어떤 선택이 “지금 가장 좋아 보이는 것”이라고 해서 최선의 해가 되는 것은 아니다. 하지만, 그런 탐욕스러운 선택이 오히려 정답으로 이어지는 경우가 있다. 이러한 전략을 우리는 그리디 알고리즘(Greedy Algorithm)이라고 부른다. 이번 글에서는 그리디 알고리즘이 무엇이고, 어떤 상황에서 이를 사용할 수 있는지에 대해서 정리해본다.

---

그리디 알고리즘을 어떤 수식이나 그래프가 있는 그림으로 설명하는 것은 어렵다. 그래서 철학적인(?) 배경과 그 방법에 대한 이론을 정리하는 식으로 내용을 정리해본다.

지금 당장 좋은 선택

일반적으로 알고리즘 문제를 풀다 보면 전체적인 상황을 고려해서 최적의 해를 찾아야 한다. 동적 계획법 (Dynamic Programming)이나 백트래킹 같은 방식이 대표적이다. 하지만 이들은 많은 경우를 탐색하고, 비교하고, 저장해야 한다. 시간도 메모리도 많이 든다.

그런데 만약 “지금 이 순간 가장 좋아 보이는 선택”이 나중에도 최선의 결과를 보장할 수 있다면? 그렇다면 우리는 굳이 모든 경우를 따져보지 않아도 된다. 바로 그게 그리디 알고리즘이 작동하는 방식이다.

최적의 해는 항상 국소적 최선의 선택으로 구성될 수 있다?

그리디 알고리즘은 “매 단계마다 가장 좋아 보이는 선택을 하면, 전체적으로도 최적의 결과를 얻을 수 있다”는 전제를 깔고 있다. 이것이 바로 탐욕 선택 속성(greedy choice property)이다.
또한, 문제 자체가 여러 조각의 결정으로 나뉘었을 때, 작은 문제의 최적해가 전체 문제의 최적해를 구성할 수 있어야 한다. 이를 최적 부분 구조(optimal substructure)라고 한다.

거스름돈 문제는 이 두 가지 핵심 속성을 보여주는 예시이다. 가장 적은 숫자의 동전으로 2,170원의 거스름돈을 지불해야 한다고 가정해보자. 이 때 가장 큰 단위인 1,000원 두 장을 선택하는 것이 현재 상황에서 가장 좋아보이는 선택이다. 이러한 탐욕적인 선택은 최종적으로 사용하는 동전의 개수를 최소화하는 데 기여한다고 가정하는 것이다.

그리고 남은 170원을 거슬러주는 방법에 대한 해답이 2,170원을 거슬러주는 방법에 대한 해답의 일부가 된다.

 

하지만 중요한 점은 모든 동전 시스템에서 이러한 탐욕적인 접근 방식이 항상 최적의 해를 보장하는 것은 아니라는 것이다. 예를 들어, 만약 우리나라 동전 체계에 400원짜리 동전이 추가된다면, 800원을 거슬러 줄 때 그리디 알고리즘은 500원짜리 한 개와 100원짜리 세 개를 선택하여 총 4개의 동전을 사용하지만, 실제 최적 해는 400원짜리 두 개로 총 2개의 동전만 사용하는 것이다. 이처럼 특정 동전 구성에서는 탐욕 선택 속성이 성립하지 않아 최적의 해를 찾지 못할 수도 있다.

그리디 알고리즘 수행 과정

그리디 알고리즘은 정렬 기반의 문제나, 선택 기준이 명확한 문제에서 자주 사용된다. 하지만 “무작정 좋아 보이는 걸 고르자!”가 아니라, 체계적인 프로세스를 따른다.

1. 선택 기준 정의 (Greedy Criteria)
문제를 분석해서 무엇이 좋은 선택인지 기준을 정한다. 이 기준이 바로 알고리즘의 핵심이다. 거스름돈 문제에서 가장 "가능한 큰 단위를 선택한다"가 선택의 기준이 될 수 있다.

2. 정렬 또는 우선순위 지정
선택 기준에 따라 데이터를 정렬하거나 우선순위 큐를 사용해서, 항상 가장 좋은 선택을 빠르게 고를 수 있도록 준비한다. 이 과정은 보통 sort 또는 priority_queue로 구현된다.

3. 선택의 반복 (Greedy Choice)
앞에서 정해둔 기준에 따라 매 순간 최선의 선택을 하고, 이 선택이 가능한지를 확인하면서 결과에 추가한다. 그리고 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지를 확인해야 한다. 전체 문제를 해결하지 못한다면 같은 과정을 반복해야 한다.

코드 구현

주어지는 금액에 대해 최소의 동전으로 지불하는 방법을 구하는 코드는 아래와 같다.

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n; // 거슬러 줘야 할 금액

    int coins[] = {500, 100, 50, 10}; // 큰 단위부터
    int count = 0;

    for (int i = 0; i < 4; i++) {
        count += n / coins[i]; // 해당 동전 몇 개?
        n %= coins[i];         // 남은 금액
    }

    cout << count << endl;
    return 0;
}

앞에서 이야기했던 방법에 대응해서 보면,

선택 기준은 거스름돈의 단위가 큰 것부터 고르는 것을 의미하고, 정렬은 그에 맞게 금액의 크기 순서대로 동전 행렬을 정의했으며, 반복 선택을 위해 for문을 이용해 count에 계속 더해주었다.

---

그리디 알고리즘은 조건만 잘 맞는다면 매우 빠르고 효율적인 방식이다.
하지만, 문제의 구조가 탐욕 선택 속성과 최적 부분 구조를 만족하지 않는다면 정확하지 않은 결과가 나올 수 있다.

즉, 문제를 푸는 것보다 더 중요한 건 "이 문제를 그리디로 풀 수 있는가?"를 먼저 판단하는 능력인 것 같다.