Greedy Algorithm (그리디 알고리즘)

 

그리디 알고리즘이란 무엇인가

그리디 알고리즘은 매 순간 가장 최선이라고 생각되는 선택을 반복적으로 하는 방식의 알고리즘이다. 각 단계에서의 최적 선택이 결국 전체 문제의 최적해로 이어진다는 전제 하에 동작한다. 이를 위해 문제를 구성하는 각 부분 문제들에 대해 지역적으로 최적의 해를 구하고, 그 해를 조합하여 전체 해를 구성한다.

 

예를 들어, 거스름돈을 줄 때 가장 큰 단위의 동전을 먼저 주는 방식이 그리디 알고리즘의 대표적인 사례다. 항상 현재 상황에서 가장 큰 가치나 이득을 주는 선택을 하기 때문에 '탐욕적(greedy)'이라는 표현을 쓴다. 구현은 일반적으로 반복문이나 정렬 기반의 로직과 함께 쓰이는 경우가 많으며, 동적 계획법이나 완전 탐색보다 구현이 간단하고 빠르다는 장점이 있다.

 

그러나 그리디 알고리즘이 항상 정답을 보장하지는 않는다. 선택의 순간마다 한 번의 선택으로 확정하기 때문에, 나중에 더 좋은 선택을 위한 여지를 남기지 않는다. 따라서 문제 자체가 그리디 알고리즘에 적합한 조건을 만족해야 한다. 이 조건은 다음 단락에서 다룰 ‘탐욕 선택 속성’과 ‘최적 부분 구조’이다.

---

탐욕 선택 속성 + 최적 부분 구조

그리디 알고리즘이 문제의 최적해를 보장하기 위해서는 두 가지 조건을 만족해야 한다. 바로 탐욕 선택 속성과 최적 부분 구조이다.

 

탐욕 선택 속성

• 정의: 전체 최적해가 반드시 각 단계의 국소적 최적 선택을 포함해야 한다.
• 의미: 지금 당장의 선택이 나중에도 영향을 미치지 않고, 전체적으로도 최선이 되어야 한다.
• 실패 예시: 이 속성이 없으면 현재의 최선이 전체의 최선이 아닐 수 있다 → 잘못된 해 도출

---

최적 부분 구조

• 정의: 문제를 작은 문제로 나누어 풀 수 있고, 이들을 조합하면 전체 문제의 최적해가 된다.
• 공통점: 동적 계획법도 이 조건을 필요로 한다.
• 차이점: 그리디는 이전 선택을 기억하거나 되돌릴 필요가 없다 → 단순하고 빠름

---

예제 1. 거스름돈 문제

 

• 문제: 가장 적은 개수의 동전으로 거스름돈 N원을 만들어야 한다.
• 전략: 큰 단위의 동전부터 가능한 만큼 사용한다.
• 전제 조건: 동전 단위가 배수 관계일 경우에만 정답 보장

int[] coins = {500, 100, 50, 10};
int n = 1260;
int count = 0;

for (int coin : coins) {
    count += n / coin;
    n %= coin;
}
System.out.println(count);

 

 

---

예제 2. 회의실 배정 문제

 

• 문제: N개의 회의 요청이 있을 때, 최대한 많은 회의를 하나의 회의실에서 배정하고 싶다.
• 전략: 종료 시간이 빠른 회의부터 선택한다.
• 이유: 더 많은 회의를 배치하려면 가능한 한 빠르게 끝나는 회의부터 넣는 것이 유리
• 핵심 조건: 회의는 겹치면 안 됨 (시작시간 ≥ 이전 회의 종료시간)

import java.util.*;

class Meeting implements Comparable<Meeting> {
    int start, end;
    public Meeting(int start, int end) {
        this.start = start;
        this.end = end;
    }
    public int compareTo(Meeting o) {
        return this.end != o.end ? this.end - o.end : this.start - o.start;
    }
}

// 예제 사용
List<Meeting> meetings = Arrays.asList(
    new Meeting(1, 4), new Meeting(3, 5),
    new Meeting(0, 6), new Meeting(5, 7),
    new Meeting(8, 9), new Meeting(5, 9)
);

Collections.sort(meetings);

int count = 0, lastEnd = 0;
for (Meeting m : meetings) {
    if (m.start >= lastEnd) {
        lastEnd = m.end;
        count++;
    }
}
System.out.println(count);  // 출력: 4

 

 

---

예제 3. 자를 수 있는 배낭 문제

 

• 문제: 무게 제한이 있는 배낭에 물건을 담을 때, 이익이 최대가 되도록 구성
• 전략: 가치/무게 비율이 높은 물건부터 가능한 만큼 담는다 (일부만 담을 수 있음)

import java.util.*;

class Item {
    int weight, value;
    public Item(int weight, int value) {
        this.weight = weight;
        this.value = value;
    }
}

List<Item> items = Arrays.asList(
    new Item(10, 60), new Item(20, 100), new Item(30, 120)
);

double capacity = 50;
items.sort((a, b) -> Double.compare(
    (double)b.value / b.weight, (double)a.value / a.weight));

double totalValue = 0.0;
for (Item item : items) {
    if (capacity == 0) break;
    if (item.weight <= capacity) {
        capacity -= item.weight;
        totalValue += item.value;
    } else {
        totalValue += item.value * (capacity / item.weight);
        capacity = 0;
    }
}
System.out.println(totalValue);  // 출력: 240.0

 

---

그리디 알고리즘이 실패하는 사례와 주의점

그리디 알고리즘은 빠르고 구현이 간단하다는 장점이 있지만, 문제의 조건이 맞지 않으면 전혀 엉뚱한 해를 내놓을 수 있다. 특히 ⟨⟨탐욕 선택 속성⟩⟩이나 ⟨⟨최적 부분 구조⟩⟩가 성립하지 않는 문제에서는 신뢰할 수 없다.

 

1. 실패 사례: 거스름돈 문제 (비배수 단위)

int[] coins = {10, 7, 1}; // 단위가 배수가 아님
int n = 14;
int count = 0;

for (int coin : coins) {
    count += n / coin;
    n %= coin;
}
System.out.println(count);  // 출력: 4 (10+1+1+1+1) → 오답

• 문제점: 정답은 7원짜리 2개로 2개만 필요하지만, 그리디는 10원부터 써버려 잘못된 선택을 한다.

---

2. 실패 사례: 0-1 배낭 문제 (물건을 자를 수 없는 경우)

• 문제: 자르지 않고 ‘통째로’ 물건을 담아야 할 때는 가치/무게 비율만으로는 정확한 판단이 불가능하다.
• 필요 전략: 동적 계획법처럼 경우의 수를 나눠서 최적값을 계산해야 한다.

---

3. 실전에서의 주의점

• 정렬한 뒤 단순 선택으로 끝나는 구조인가? → 그리디 가능성 있음
• 선택이 이후에 영향을 주는가? 되돌릴 수 있는가? → 그리디에 부적합
• 가능하다면 작은 케이스로 시뮬레이션 해보기 → 실패 여부를 빠르게 파악 가능
• 정답이 보장되는 조건을 명확히 확인하고 사용하기