그리디 (Greedy)

정의

그리디 (Greedy) 알고리즘은 매 단계마다 국소 최적 (locally optimal) 선택을 하여 전역 최적해 (globally optimal solution) 에 도달하는 설계 패러다임. 핵심은 선택의 순서와 그 선택이 최적성을 해치지 않는다는 exchange argument 증명.

역사: 1950년대 Dijkstra 의 최단 경로, Kruskal/Prim 의 MST 등에서 정립. 1970년대 Huffman coding, activity selection 이론적 틀 완성.

문제 상황과 동기

“최적해를 찾아라” 유형 문제.

• naive (완전 탐색): 모든 선택 조합 탐색. O(2^N) 또는 O(N!). N=20 면 2^20 = 100만, N=50 이면 절대 불가능.
• 동적 계획법 (DP): 중복 부분 문제. O(N^2) ~ O(N^3). 메모리 많이 사용.
• greedy: 선택의 순서를 정렬 / 우선순위로 정한 뒤 한 번만 순회. O(N log N) (정렬) + O(N) (선택). 메모리 O(1) ~ O(N).

핵심 통찰: 선택을 바꿔도 (exchange) 최적성이 유지된다면 greedy 가 맞다.

자주 등장: activity selection, interval scheduling, fractional knapsack, Huffman, MST (Kruskal/Prim), Dijkstra, coin change (특정 동전 체계), load balancing.

시각화

핵심 아이디어

greedy choice property: 각 단계의 국소 최적 선택이 전역 최적 부분 문제로 이어진다.

optimal substructure: 문제의 최적해가 부분 문제의 최적해로 구성.

증명 패턴 (exchange argument):

1. 최적해 OPT 가 greedy 선택과 다르다고 가정.
2. OPT 의 첫 선택을 greedy 선택으로 교환.
3. 교환 후 해가 여전히 최적 (또는 더 좋음) 임을 보임.
4. 모든 선택을 greedy 로 바꿔도 최적성 유지 → greedy 가 최적.

예: activity selection (종료 시각 빠른 순으로 선택). 종료가 빠르면 이후 선택 가능한 구간이 최대로 남음. OPT 가 다른 걸 선택했다면 그걸 greedy 선택으로 바꿔도 충돌 없고 선택 가능 개수 유지 또는 증가.

알고리즘 (Activity Selection)

activity_selection(S):
    // S: [(start, end)] 리스트
    S.sort(by end time)    // 종료 시각 오름차순
    result = []
    last_end = -∞
    for (s, e) in S:
        if s >= last_end:
            result.append((s, e))
            last_end = e
    return result

시간: O(N log N) (정렬) + O(N) (선택) = O(N log N).

구현

// Activity Selection, 종료 빠른 순
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n; cin >> n;
  vector<pair<int,int>> a(n);
  for (auto& [s, e] : a) cin >> s >> e;
  sort(a.begin(), a.end(), [](auto& x, auto& y){ return x.second < y.second; });
  vector<pair<int,int>> res;
  int last = -1e9;
  for (auto [s, e] : a) {
      if (s >= last) {
          res.push_back({s, e});
          last = e;
      }
  }
  cout << res.size() << "\n";
  for (auto [s, e] : res) cout << s << " " << e << "\n";
}

# Activity Selection
import sys
input = sys.stdin.readline
​
n = int(input())
a = [tuple(map(int, input().split())) for _ in range(n)]
a.sort(key=lambda x: x[1])   # 종료 시각 오름차순
res = []
last = -float('inf')
for s, e in a:
  if s >= last:
      res.append((s, e))
      last = e
print(len(res))
for s, e in res:
  print(s, e)

// Activity Selection
import java.util.*;
import java.io.*;
public class Main {
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int n = Integer.parseInt(br.readLine());
      int[][] a = new int[n][2];
      for (int i = 0; i < n; i++) {
          StringTokenizer st = new StringTokenizer(br.readLine());
          a[i][0] = Integer.parseInt(st.nextToken());
          a[i][1] = Integer.parseInt(st.nextToken());
      }
      Arrays.sort(a, Comparator.comparingInt(x -> x[1]));
      List<int[]> res = new ArrayList<>();
      int last = Integer.MIN_VALUE;
      for (int[] p : a) {
          if (p[0] >= last) {
              res.add(p);
              last = p[1];
          }
      }
      System.out.println(res.size());
      for (int[] p : res) System.out.println(p[0] + " " + p[1]);
  }
}

6
1 3
2 5
3 7
4 6
5 8
7 9

3
1 3
4 6
7 9

복잡도

대표 문제와 greedy 기준

변형 / 활용

• Interval Scheduling Maximization: activity selection.
• Minimum Spanning Tree: Kruskal, Prim 모두 greedy.
• Dijkstra: 최단 경로. 음수 간선 없으면 greedy 최적.
• Huffman: 최적 prefix-free code.
• Fractional Knapsack: 배낭 무게 제한, 물건 쪼개기 가능. 단위 가치 순.
• 0/1 Knapsack: 쪼개기 불가 → greedy 불가, 동적 계획법 필요.

함정

1. Greedy 가 최적이 아닌 경우

0/1 Knapsack: 물건 쪼개기 불가. 단위 가치 순 greedy 는 반례 존재.

예: 용량 10, 물건 [(w=6, v=30), (w=5, v=25), (w=4, v=24)]. 단위 가치: 5, 5, 6. greedy 는 (4,24) + (5,25) = 49. 최적은 (6,30) + (4,24) = 54.

2. Coin Change (일반 동전 체계)

동전이 배수 관계가 아니면 greedy 실패.

예: 동전 [1, 3, 4], 목표 6. greedy (큰 것 먼저): 4 + 1 + 1 = 3개. 최적: 3 + 3 = 2개.

미국/한국 동전 (1, 5, 10, 25, 100, …) 은 배수 관계 → greedy 최적.

3. 증명 없이 greedy 사용

직관적으로 “이게 맞을 것 같다” 만으로 greedy 쓰면 틀림. 반드시 exchange argument 또는 optimal substructure 증명 필요.

4. 정렬 기준 잘못 선택

Activity selection 에서 시작 빠른 순 / 길이 짧은 순 은 반례 존재. 종료 빠른 순만 최적.

예: [(1,10), (2,3), (4,5)]. 종료 순: (2,3), (4,5) → 2개. 시작 순: (1,10) → 1개.

BOJ 연습 문제

참고

• 동적 계획법 (greedy 안 되면 DP)
• Kruskal, Prim (MST greedy)
• Dijkstra (최단 경로 greedy)
• Huffman (최적 prefix code)