Greedy Algorithm (탐욕 알고리즘)

---

1. 정의

Greedy 알고리즘은 문제를 해결할 때 현재 단계에서 가장 좋아 보이는 선택(국소 최적해) 을 반복하여 전체 해답을 구하는 방법이다.
즉, 미래의 영향을 고려하지 않고, 매 순간 최선이라고 판단되는 선택을 한다.

---

2. 핵심 아이디어

개념	설명
탐욕적 선택(Greedy Choice)	현재 단계에서 최선의 선택을 한다.
부분 최적해(Local Optimum)	각 단계의 최적 선택이 전체 최적해(Global Optimum)로 이어진다고 가정한다.
비가역성	한 번 선택하면 이후에 되돌리지 않는다.

Greedy는 "순간의 선택 합이 전체 최적을 만든다"는 전제 위에 설계된다.

---

3. 작동 원리

1. 문제를 여러 단계로 분할한다.
2. 각 단계에서 가능한 선택들 중 가장 좋은 선택을 한다.
3. 그 선택을 확정하고 다음 단계로 이동한다.
4. 전체 단계가 끝날 때까지 반복한다.
5. 모든 선택들의 조합이 최종 해답이 된다.

---

4. 대표 예시

1) 거스름돈 문제

문제: 620원을 최소 개수의 동전으로 거슬러주기.
동전 단위: 500, 100, 50, 10원.

Greedy 전략: 현재 남은 금액보다 작거나 같은 가장 큰 동전을 선택한다.

• 500 → 1개
• 100 → 1개
• 10 → 2개

총 4개로 해결.
단, 동전 단위가 일반적이지 않은 경우(예: 500, 400, 100)에는 Greedy가 항상 최적해를 보장하지 못할 수 있다.

---

2) 회의실 배정 문제 (Activity Selection)

문제: 회의들의 시작/종료 시간이 주어졌을 때, 겹치지 않게 최대한 많은 회의를 선택하라.

Greedy 전략: 가장 빨리 끝나는 회의를 우선 선택한다.

이 전략을 따르면 전역 최적해가 보장된다.

---

5. Greedy 알고리즘이 성립하기 위한 조건

조건	의미
탐욕적 선택 속성(Greedy Choice Property)	매 단계의 국소 최적 선택이 전체 최적해로 이어져야 한다.
최적 부분 구조(Optimal Substructure)	전체 문제의 최적해가 부분 문제의 최적해로부터 구성될 수 있어야 한다.

두 조건이 맞지 않으면 Greedy는 정답을 보장하지 못하며 근사해가 될 수 있다.

---

6. 대표 알고리즘 구조 (의사코드)

procedure GREEDY(Problem P)
    solution ← ∅
    while 선택해야 할 단계가 남아 있을 때:
        x ← 현재 상태에서 가장 유리한 후보 선택
        if x가 유효하다면:
            solution ← solution ∪ {x}
        상태 업데이트
    return solution

---

7. 대표 문제 유형

문제	전략
동전 거스름돈	큰 단위부터 사용
회의실 배정	종료 시간이 빠른 회의부터 선택
최소 신장 트리	Kruskal, Prim 알고리즘은 Greedy 기반
허프만 코딩	빈도 낮은 문자부터 결합
Fractional Knapsack	단가가 높은 물건부터 부분적으로 담기

---

8. 시간 복잡도

Greedy 알고리즘은 대부분

• 정렬 O(N log N)
• 이후 한 번의 순회 O(N)
  정도로 동작하는 경우가 많다.

---

9. 장단점

항목	설명
장점	구현이 간단하고 빠르며 효율적이다.
단점	항상 최적해를 보장하지 않는다.
특징	문제 구조가 Greedy 방식에 맞지 않으면 오답이 된다.

---

10. 요약

Greedy 알고리즘은 매 순간 최선의 선택을 반복하여 문제를 해결하는 방식으로, 문제 구조가 이를 허용할 때 매우 빠르고 효과적인 해법이 된다.