그리디 알고리듬(Greedy Algorithm, 탐욕법)의 원리와 적용 - soo:bak

작성일 :

그리디 알고리듬이란?

그리디 알고리듬(Greedy Algorithm, 탐욕법)은 매 순간 현재 상황에서 가장 최선이라고 판단되는 선택을 하여 최종 해를 구하는 알고리듬입니다.


동전 거스름돈 문제를 예로 들면, 1260원을 거슬러 줄 때 가장 큰 단위인 500원부터 사용하고, 남은 금액에 대해 다시 가장 큰 단위를 사용하는 방식입니다.

1

1260원 = 500원 × 2 + 100원 × 2 + 50원 × 1 + 10원 × 1 = 총 6개

이처럼 각 단계에서 현재 가능한 최선의 선택을 하며, 한 번 선택한 것은 번복하지 않고 다음 단계로 진행합니다.


그리디 알고리듬은 구현이 간단하고 빠르다는 장점이 있지만, 모든 문제에서 최적해를 보장하지는 않습니다.

문제의 구조에 따라 지역적으로는 최선이지만 전체적으로는 최적이 아닌 결과가 나올 수 있으므로, 적용 가능 여부를 먼저 판단해야 합니다.


그리디 알고리듬의 원리

그리디 알고리듬은 다음과 같은 과정으로 동작합니다:


1. 선택(Selection)

현재 상황에서 가장 유리하다고 판단되는 것을 선택합니다.

예를 들어, 회의실 배정 문제에서는 종료 시간이 가장 빠른 회의를 선택합니다.


2. 적절성 검사(Feasibility)

선택한 항목이 문제의 제약 조건을 만족하는지 확인합니다.

회의실 배정 문제에서는 선택한 회의가 이전에 선택한 회의와 시간이 겹치지 않는지 확인합니다.


3. 해답 검사(Solution Check)

현재까지 선택한 항목들이 문제의 해답을 구성하는지 확인합니다.

모든 회의를 검토했다면 선택 과정을 종료합니다.


이 과정을 반복하면서 최종 해를 구성하는데, 이전 선택을 번복하거나 다시 고려하지 않습니다.

이는 백트래킹이나 동적 계획법과의 주요 차이점입니다.


그리디 알고리듬의 적용 조건

그리디 알고리듬이 최적해를 보장하려면 다음 두 가지 조건을 만족해야 합니다:


1. 탐욕적 선택 속성 (Greedy Choice Property)

각 단계의 선택이 이후 선택에 영향을 주지 않으며, 지역적 최선의 선택이 전체 최적해의 일부가 되어야 합니다.


회의실 배정 문제에서 종료 시간이 가장 빠른 회의를 선택하는 것은 탐욕적 선택 속성을 만족합니다.

가장 빨리 끝나는 회의를 선택하면 나머지 시간이 최대화되어, 더 많은 회의를 배정할 수 있는 기회가 생기기 때문입니다.


2. 최적 부분 구조 (Optimal Substructure)

전체 문제의 최적해가 부분 문제의 최적해로 구성되어야 합니다.


회의실 배정 문제에서 첫 번째 회의를 최적으로 선택했다면, 남은 시간에 대한 회의 배정 문제도 독립적으로 최적해를 구할 수 있습니다.

즉, 전체 최적해 = 현재 최선의 선택 + 남은 부분의 최적해 구조를 가집니다.


동적 계획법과의 비교

두 알고리듬 모두 최적 부분 구조를 요구하지만, 접근 방식에서 차이가 있습니다:


구분 그리디 알고리듬 동적 계획법
선택 방식 현재 최선의 선택만 고려 모든 경우를 고려하여 최선 선택
선택의 되돌림 불가능 (한 번 선택하면 고정) 가능 (이전 상태 저장)
부분 문제 해결 탐욕적 선택 속성 필요 중복되는 부분 문제 활용
시간 복잡도 일반적으로 \(O(n \log n)\) 일반적으로 \(O(n^2)\) 이상
최적해 보장 조건 만족 시에만 항상 보장


예를 들어, 동전 거스름돈 문제에서:

  • 동전 단위가 [500, 100, 50, 10]이면 그리디로 최적해를 구할 수 있습니다
  • 동전 단위가 [4, 3, 1]이고 거스름돈이 6이면 그리디는 4 + 1 + 1 = 3개를 선택하지만, 최적해는 3 + 3 = 2개입니다

이처럼 탐욕적 선택 속성이 성립하지 않는 경우 그리디 알고리듬은 최적해를 보장하지 못하므로, 동적 계획법을 사용해야 합니다.


그리디 알고리듬의 구현

그리디 알고리듬은 대부분 정렬 + 선택 구조로 구현됩니다.


기본 구현 패턴

1
2
3
4
5
6
7
8
9
10
11
12

#include <bits/stdc++.h>
using namespace std;

// 1. 정렬 기준에 따라 데이터 정렬
sort(data.begin(), data.end(), comparator);

// 2. 정렬된 순서대로 탐욕적 선택
for (auto item : data) {
  if (조건을_만족하면) {
    선택에_추가();
  }
}


회의실 배정 문제 구현

문제: 한 회의실에서 최대한 많은 회의를 진행하려고 합니다. 각 회의는 시작 시간과 종료 시간이 주어지며, 겹치지 않게 배정해야 합니다.


접근법

회의를 종료 시간 기준으로 정렬하고, 빨리 끝나는 회의부터 선택합니다.

종료 시간이 빠를수록 남은 시간이 많아져, 더 많은 회의를 배정할 기회가 생기기 때문입니다.


구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

#include <bits/stdc++.h>
using namespace std;

struct Meeting {
  int start, end;
};

int main() {
  int n;
  cin >> n;
  
  vector<Meeting> meetings(n);
  for (int i = 0; i < n; i++) {
    cin >> meetings[i].start >> meetings[i].end;
  }
  
  // 종료 시간 기준으로 정렬
  // 종료 시간이 같으면 시작 시간이 빠른 순
  sort(meetings.begin(), meetings.end(), [](const Meeting& a, const Meeting& b) {
    if (a.end == b.end) return a.start < b.start;
    return a.end < b.end;
  });
  
  int count = 0;
  int lastEndTime = 0;  // 마지막으로 선택한 회의의 종료 시간
  
  for (const auto& meeting : meetings) {
    // 이전 회의가 끝난 후 시작하는 회의만 선택
    if (meeting.start >= lastEndTime) {
      count++;
      lastEndTime = meeting.end;
    }
  }
  
  cout << count << "\n";
  
  return 0;
}


시간 복잡도: \(O(n \log n)\)

정렬에 \(O(n \log n)\), 선택 과정에 \(O(n)\)이 소요되므로 전체 시간 복잡도는 \(O(n \log n)\)입니다.


동전 거스름돈 문제 구현

문제: 거스름돈을 최소 개수의 동전으로 만들어야 합니다.


구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#include <bits/stdc++.h>
using namespace std;

int main() {
  vector<int> coins = {500, 100, 50, 10};
  int amount = 1260;
  
  int count = 0;
  
  // 큰 단위부터 사용
  for (int coin : coins) {
    count += amount / coin;  // 해당 동전을 최대한 사용
    amount %= coin;           // 남은 금액 갱신
  }
  
  cout << count << "\n";  // 6
  
  return 0;
}


주의사항: 이 방법은 동전 단위가 배수 관계일 때만 최적해를 보장합니다.

예를 들어, 동전이 [1, 3, 4]이고 거스름돈이 6인 경우:

  • 그리디: 4 + 1 + 1 = 3개
  • 최적해: 3 + 3 = 2개

이처럼 배수 관계가 아닌 경우에는 동적 계획법을 사용해야 합니다.


그리디 알고리듬이 실패하는 경우

그리디 알고리듬이 항상 최적해를 보장하지 않는 대표적인 예시를 살펴보겠습니다.


배낭 문제 (0-1 Knapsack)

문제: 배낭의 최대 무게가 정해져 있고, 각 물건은 무게와 가치를 가지고 있습니다. 물건을 쪼갤 수 없으며, 배낭에 담을 물건을 선택하여 가치의 합을 최대화해야 합니다.


그리디 전략: 가치 대비 무게 비율이 높은 물건부터 선택


예시

물건 무게 가치 비율
A 10 60 6.0
B 20 100 5.0
C 30 120 4.0

배낭 용량: 50


그리디 알고리듬은 비율이 높은 순서대로 A, B를 선택합니다:

  • 선택: A(10) + B(20) = 무게 30, 가치 160
  • 남은 용량 20으로는 C를 담을 수 없음


하지만 최적해는 B와 C를 선택하는 것입니다:

  • 최적: B(20) + C(30) = 무게 50, 가치 220


이처럼 물건을 쪼갤 수 없는 제약 조건이 있는 경우, 현재의 최선 선택이 이후 선택에 영향을 미쳐 전체 최적해를 보장하지 못합니다.

이 경우 동적 계획법을 사용해야 합니다.


참고: 물건을 쪼갤 수 있는 분할 가능 배낭 문제(Fractional Knapsack)에서는 그리디 알고리듬으로 최적해를 구할 수 있습니다.


그리디 알고리듬의 활용

그리디 알고리듬은 다양한 최적화 문제에서 효과적으로 활용됩니다:


스케줄링 문제

  • 회의실 배정, 작업 스케줄링
  • 종료 시간 기준 정렬을 통한 최대 작업 수 선택


최소 신장 트리 (MST)

  • Kruskal 알고리듬: 가중치가 작은 간선부터 선택
  • Prim 알고리듬: 현재 트리에서 가장 가까운 정점 선택


최단 경로

  • Dijkstra 알고리듬: 현재까지의 최단 거리가 가장 짧은 정점 선택


데이터 압축

  • Huffman 코딩: 빈도가 낮은 문자부터 합치며 최적 인코딩 구성


거스름돈 문제

  • 동전 단위가 배수 관계일 때 큰 단위부터 사용


시간 복잡도

그리디 알고리듬의 시간 복잡도는 주로 정렬에 의해 결정됩니다:


단계 시간 복잡도 설명
정렬 \(O(n \log n)\) 정렬 기준에 따라 데이터 정렬
선택 \(O(n)\) 정렬된 순서대로 조건 확인 및 선택
전체 \(O(n \log n)\) 정렬이 지배적


정렬이 필요 없거나 이미 정렬된 데이터인 경우 \(O(n)\)에 해결할 수 있습니다.


그리디 알고리듬 설계 과정

그리디 알고리듬을 설계할 때는 다음 단계를 따릅니다:


1. 탐욕적 선택 기준 정의

각 단계에서 무엇을 기준으로 ‘최선’을 판단할지 결정합니다.

예: 회의실 배정 → 종료 시간, 최소 신장 트리 → 간선 가중치


2. 정렬 기준 설정

탐욕적 선택 기준에 따라 데이터를 정렬합니다.


3. 선택 과정 구현

정렬된 순서대로 조건을 만족하는 요소를 선택합니다.


4. 타당성 검증

탐욕적 선택 속성과 최적 부분 구조를 만족하는지 확인합니다.

간단한 반례를 통해 그리디 방식이 최적해를 보장하는지 검토합니다.


마무리

그리디 알고리듬은 매 순간의 최선 선택을 통해 빠르고 간단하게 최적해를 구하는 알고리듬입니다.


핵심 포인트

  • 탐욕적 선택 속성과 최적 부분 구조를 만족할 때 최적해 보장
  • 대부분 정렬 + 선택 구조로 구현되며, 시간 복잡도는 \(O(n \log n)\)
  • 조건을 만족하지 않으면 최적해를 보장하지 못하므로, 적용 가능 여부를 먼저 확인해야 함


그리디 알고리듬을 적용하기 전에는 반례를 고려하여, 해당 문제가 그리디로 해결 가능한지 판단하는 것이 중요합니다.

만약 그리디로 최적해를 보장할 수 없다면, 백트래킹이나 동적 계획법을 고려해야 합니다.


관련 글

이 블로그의 다른 글