그리디(Greedy) 알고리즘

그리디(Greedy) 알고리즘

매 순간 가장 좋아보이는 선택을 하는 알고리즘.

구성 방식

1. Optimal Substructure (최적 부분 구조) 확인

   • 전체 문제의 최적해가 부분 문제의 최적해로부터 만들어질 수 있어야 함.
   • 예: 활동 선택 문제에서 S_ij 같은 식으로 서브문제 설정.

2. Recursive 구조 파악

   • 문제를 재귀적으로 쪼갤 수 있어야 함.
   • 예: OPT(i, j) = max(OPT(i, k) + OPT(k, j)) 같은 형식.

3. Greedy Choice 후, 하나의 하위 문제만 남음

   • 중요한 포인트. 동적 계획법은 보통 하위 문제가 여러 개지만,
   • 그리디는 하나만 남기게 설계되어야 효율적임.

4. Greedy Choice의 안전성 증명

   • “언제나 지금 고르는 게 전체적으로도 최선”이라는 걸 보여야 함.
   • 귀류법으로 자주 증명함 (예: 활동 선택에서 최단 종료시간 선택의 안전성).

5. 재귀적 알고리즘 → 반복적 알고리즘 변환

• 재귀는 스택 오버플로우 날 수 있으니 반복 버전도 만들어보자.

---

그리디가 통하지 않는 경우

• 부분에서의 최적이 전체의 최적을 보장하지 않는 경우
• 예: 0/1 Knapsack → 그리디로 풀면 터진다. (Dynamic Programming 가야 함)

---

분석 팁

• Greedy-Choice Property 검증 → 부분 해가 전체 해로 확장 가능한가?
• 최적 부분 구조 존재 여부 → 부분 문제 풀면 전체 해를 쉽게 구할 수 있나?
• Exchange Argument 사용 → 최적해와 비교하며, greedy가 만든 해도 최적인지 swap으로 증명

질문	의미	예시
1. 이 선택이 현재 최선인가?	“지금 당장 뭘 고를래?”	동전 중 제일 큰 거부터
2. 이 선택이 미래에 문제 안 만들까?	“이러다가 나중에 후회 안 할까?”	배낭 문제에서 물건 다 때려넣다 후회
3. 이 선택이 전체적으로도 최선인가?	“이거 계속하면 전체 최적 나오냐?”	회의실 배정 → 끝나는 시간 빠른 순 OK

---

장점

• 속도: 그리디는 대체로 시간 복잡도가 낮고, 구현이 간단함
• 효율성: 결정 즉시 확정 → 백트래킹, DP 같은 무거운 연산 X
• 해당 문제에 최적화 되어 있으면 그 어떤 방법보다 빠르고 정확

---

주의점

• 항상 최적해를 보장하지 않음 (반례 한 번이면 박살남)
• “그리디로 풀 수 있냐?“를 먼저 판별해야 함
• CLRS에서도 항상 정당성 증명을 강조

---

대표적인 문제 유형 & 전략

유형	예시 문제	전략
활동 선택	회의실 배정	끝나는 시간이 빠른 순
탐욕적 누적	거스름돈, 동전 문제	큰 값부터
정렬 기반 선택	신입사원, 인터벌 커버	조건에 맞게 정렬 후 순차 선택
스케줄링	멀티탭 스케줄링	가장 나중에 쓸 애 제거
그래프 관련	프림 / 크루스칼	최소 간선 / 비용 기준 선택

---

비교 요약

알고리즘	장점	단점	예시
Greedy	빠름, 직관적	정당성 필요, 최적 보장 안됨	회의실 배정
DP	항상 최적	느림, 구현 복잡	Knapsack
백트래킹	정확도 높음	매우 느림	N-Queen