[알고리즘/Algorithm] 그리디(Greedy:탐욕) 알고리즘(패러다임)

안녕하세요!

이번에는 그리디(Greedy, 탐욕)에 대해서 공부해보려고 합니다.

엄연히 말하면 그리디는 알고리즘 그 자체라기 보다는, 

"알고리즘 설계 기법(패러다임)"입니다.

 

이러한 그리디 기법을 활용한 알고리즘이 많아서 따로 정리해보려고 이렇게 포스팅을 해봅니다 !!

---

그리디(Greedy)란?

---

🔹 Greedy(탐욕) 알고리즘(패러다임)이란?

• 매 단계에서 당장 최선으로 보이는 선택(국소 최적)을 하고
• 그 선택을 되돌리지 않으며
• 다음단계로 나아가는 방법
• 정확히는 "알고리즘 설계 기법(패러다임)"
• 목표: 이러한 국소 최적 선택들의 연쇄가 전역 최적해로 이어지도록 하는 것.

🔹 Greedy 핵심 성질

-> Greedy가 성립하기 위한 조건은 무엇이 있을까요?

1. Greedy-choice property
   
   • 지금 시점에서의 최선의 선택이 어떤 최적해와도 충돌하지 않음
   • 즉, 그 선택을 해도 최적화를 이어갈 수 있음
2. Optimal Substructure: 최적 부분 구조
   • 한 번이 선택 이후 남은 부분 문제의 최적해를 이어붙이면 전체도 최적

결론: "지금 가장 좋은 한 수를 둬도, 나중에 그 선택 때문에 발목이 잡히지 않는다." 입니다.

 

🔹 Greedy 증명 도구(패턴)

그리디를 증명하기 위한 도구들이 몇 가지 있습니다.

그리디는 알고리즘 하나라기 보다는 "각 순간의 최적해를 찾아가면 최종 결과도 최적해"가 나오는 알고리즘 설계 기법(패러다임)이므로 "그리디 기법을 활용한 알고리즘"들이 있습니다. 

증명도 각 알고리즘마다 가능하기도 합니다 :)

1. 교환 논법(Exchange Argument)
   • 한 최적해를 생각해보면, 우리 Greedy 선택과 다르더라도 두 해의 일부를 교환해도 최적성 손상이 없습니다.
   • → 결국 Greedy 선택과 일치하는 최적해가 존재합니다.
   • 예시) 활동 선택(Interval Scheduling), Huffman 코딩 등
2. 컷(Cut) 속성
   • 해를 둘로 가르는 경계(cut)를 만들고, 그 경계를 가로지르는 간선 중 최선(최소/최대)을 고르는 것이 항상 안전함을 보입니다.
   • 예시) MST(Prim, Kruskal)
3. 매트로이드(Matroid) 프레임(선택적 심화)
   • 독립 집합 계열이 유전성 + 증대성(교환성)을 만족하면, 가중치가 있는 원소들을 정렬 후 Greedy로 최적이 가능합니다.
   • 활동 선택(가중치=동일), 스패닝 트리 등이 매트로이드로 설명 가능합니다.
4. 루프 불변식
   • 반복마다 “지금까지의 선택은 항상 최적해로 확장 가능” 같은 불변식을 세워 증명이 가능합니다.

---

Greedy 해결방식 설계 & 시간복잡도

---

🔹 Greedy 활용 해결방식의 설계

1. 판단 기준 정의

: 무엇을 기준으로 "지금 가장 최적의 해"로 판단할 것인지 정합니다.

예시) 종료 시간이 가장 빠른 활동, 간선 가중치가 가장 작은 간선, 가치/무게 비율이 큰 아이템

 

2. 탐욕 선택 규칙 도출

: 정렬/힙 등 자료구조로 1번의 최적해를 판단 시 선택 과정이 빠르도록 구현합니다.

 

3. 안전성 증명

: 교환 논법, 컷 속성, 불변식 등으로 해당 선택이 항상 옳은 선택인지(안전한 선택인지) 증명이 가능해야합니다.

 

4. 시간 복잡도 분석

: 설계 결과의 시간복잡도를 분석합니다.

보통 정렬 혹은 힙 조작 단계의 복잡도가 시간복잡도를 결정합니다.

(주로 정렬: O(n log n), 힙: O(m log n))

 

Greedy는 알고리즘 패러다임으로, 단독 시간복잡도가 따로 있는 것은 아닙니다.

따라서 가볍게 언급하고 넘어가겠습니다ㅎㅎ

 

🔹 그리디 복잡도 일반론

• 정렬 기반
  • O(n log n)이 기본
  • 예시) 활동 선택, Huffman, 비율 정렬 등
• 힙/우선순위 큐
  • 매 단계 O(log n)으로 데이터를 뽑고/ 데이터를 넣습니다.
  • but 크루스칼의 간선 정렬은 별도입니다.
• Union-Find
  
  • 거의 상수(a(n))로 사이클을 검사합니다.

 

그리디를 활용한 알고리즘은 알고리즘 별로 어떤 자료구조와 어떤 해결방식을 가져가느냐에 따라 시간복잡도가 달라지므로, 그리디의 시간복잡도는 별도로 정리하지 않고, 각 알고리즘 별로 포스팅 할 때 시간복잡도를 파악해보겠습니다 !!

---

Greedy 대표 문제와 해결 방법

---

🔹 Greedy 기법을 사용하는 대표적인 문제 유형

• 활동 선택(Interval Scheduling) 알고리즘
  • 종료시간 오름차순으로 정렬 후, 겹치지 않게 가장 빨리 끝나는 것부터 선택합니다.
  • 증명: 교환 논법으로 증명할 수 있습니다.
  • 시간복잡도: O(n log n)
• MST(Kruskal/Prim) - 최소 신장 트리
  • Kruskal
    • 간선 가중치 오름차순 + 사이클 방지(Union-Find)를 활용합니다.
    • 컷 속성
    • 시간복잡도: O(E log E)
  • Prim
    • 임의 시작 정점 → 가장 싼 간선으로 확장(우선순위큐)합니다.
    • 컷 속성
    • 시간복잡도: O(E log V)
• 단일 시작 최단 경로(가중치 >= 0)
  • Dijkstra: 가장 가까운 정점부터 확정합니다.
  • 컷/교환적 논리로 증명이 가능합니다.
  • 시간복잡도: O(E log V)
• Huffman 코딩
  • 빈도가 가장 작은 두 노드를 계속 합칩니다.
  • 교환 논법과 최적 접두사 성질
  • 시간복잡도: O(n log n)
• Fractional Knapsack(분할 가능 배낭)
  • 가치/무게 비율이 큰 것 부터 채웁니다.
  • 교환 논법
  • 시간복잡도: O(n log n)

 

🔹 Greedy가 실패하는 경우

• 0/1 Knapsack 문제
  • 아이템을 쪼갤 수 없으면 “가치/무게 비율” 그리디가 실패할 가능성이 있습니다.
  • 이러한 경우에는 DP가 필요합니다.
• 동전 거스름 문제
  • 예시) {1, 3, 4}로 6 만들기 → 그리디(4+1+1=3개)보다 3+3(2개)이 최적이 됩니다.
  • 단, 한국(10,50,100,500)이나 미국(1,5,10,25) 같은 정규(캐노니컬) 체계에선 그리디가 최적이 가능합니다.

---

마무리 정리 & 주의사항

---

마지막으로, 그리디에 대해서 마무리 정리를 하면서 유의사항까지 정리해보겠습니다.

 

🔹 마무리 정리

1. Greedy 는 "지금 최선"을 반복하면서도 항상 안전한 선택임을 보일 수 있을 때 강력합니다.
2. 증명(교환/컷/불변식)을 같이 해주면 실전에서 안심하고 사용할 수 있습니다.
3. 활동 선택, MST, Huffman, Fractional Knapsack은 정석 Greedy의 대표적인 예 입니다.

🔹 주의사항

• 그리디 규칙 후보가 여러 개라면 반례(작은 케이스)를 만들어 빠르게 테스트 해 보는 것이 좋습니다.
• 그리디는 정렬 기준/우선순위큐 키(key) 선정이 핵심이 됩니다.
• “되돌리지 않는” 특성상, 잘못된 규칙이면 되돌릴 방법이 없습니다.
  • → 증명 또는 강한 직관 + 반례 부재가 필요합니다.
  • 따라서 여러가지 테스트 케이스를 확인하는 습관도 필요합니다 !
• MST/최단경로처럼 컷/불변식이 보이면 그리디를 우선 검토합니다.

---

이렇게 그리디 기법에 대해서 정리해보았습니다.

이번에는 그리디가 알고리즘 그 자체라기 보다는 패러다임이기에, 따로 예제를 첨부하지 않았는데요!

각 알고리즘을 정리하면서 예제는 추가로 정리해보겠습니다 :)

그리디 하나로 많은 알고리즘과,, 증명과,, 정말 쉽지 않았지만, 정리해두니 공부 방향을 잡기가 좋네요 !!

공부하시는 분들께도 도움이 되었으면 좋겠습니다 !!