그리디 알고리즘
그리디 알고리즘 (Greedy Algorithm)
📝 개념 정의
매 선택에서 현재 당장 최적인 답을 선택하여 전체 최적해를 구하는 알고리즘 기법입니다.
핵심:
- 눈앞의 이익만 우선 추구
- 지역 최적해(Local Optimum)를 선택
- 전역 최적해(Global Optimum)를 기대
⚠️ 그리디의 한계
항상 최적해를 보장하지 않음
그리디로 부분 최적해는 구했지만, 전체 선택에서는 최적이 아닌 경로를 선택할 수 있습니다.
예시:
5
/ \
3 4
/ \ / \
1 2 6 7
- 그리디: 5 → 4 → 7 = 16
- 최적: 5 → 3 → 1 + 2 = 11 (잘못된 예시, 실제로는 문제에 따라 다름)
결론: 특수한 조건이 만족되어야만 최적해 보장
🔧 그리디 문제 해결 방법
1. 선택 절차 (Selection Procedure)
현재 상태에서 최적의 해답을 선택합니다.
2. 적절성 검사 (Feasibility Check)
선택된 해가 문제의 조건을 만족하는지 검사합니다.
3. 해답 검사 (Solution Check)
문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 반복합니다.
✅ 그리디가 성립하기 위한 조건
1. 탐욕 선택 속성 (Greedy Choice Property)
이전 선택이 이후에 영향을 주지 않음
2. 최적 부분 구조 (Optimal Substructure)
부분 문제의 최적 결과가 전체에도 적용될 수 있어야 함
매트로이드 (Matroid)
독립성 성질을 만족하는 수학적 구조로, 매트로이드를 이루면 최적해를 보장하는 그리디 알고리즘이 존재합니다.
💡 그리디 예시
1. 거스름돈 문제
문제
고객이 5000원을 내고 4210원 계산 시, 최소 동전 개수로 790원 거슬러주기
동전: 500원, 100원, 50원, 10원
해결 과정
- 선택 절차: 가장 가치가 높은 동전 우선 선택
- 적절성 검사: 동전 합이 거스름돈 초과하는지 검사
- 해답 검사: 동전 합이 거스름돈과 일치하는지 검사
결과
- 500원 × 1 = 500원
- 100원 × 2 = 200원
- 50원 × 1 = 50원
- 10원 × 4 = 40원
- 총 8개
왜 그리디가 가능한가?
큰 단위가 항상 작은 단위의 배수이므로 작은 단위 조합으로 다른 해가 나올 수 없습니다.
반례: 센트 문제
- 동전: 1, 5, 10, 25
- 25는 10의 배수가 아님
- 그리디로 최적해 보장 불가 → DP 사용
2. 활동 선택 (Activity Selection)
문제
한 강의실에서 최대한 많은 회의를 진행하려면?
회의 시간:
- (1, 6), (3, 5), (5, 9), (6, 7)
- (7, 14), (8, 13), (12, 18), (16, 20)
해결 과정
- 선택 절차: 종료 시간이 빠른 회의 선택
- 적절성 검사: 이전 회의와 겹치는지 검사
- 해답 검사: 모든 회의 검토 완료 시 종료
결과
- (3, 5) 선택
- (6, 7) 선택
- (8, 13) 선택
- (16, 20) 선택
총 4개 회의
📊 그리디 vs 동적 프로그래밍
| 특성 | 그리디 | 동적 프로그래밍 | |------|--------|-----------------| | 선택 | 현재 최적 | 모든 경우 고려 | | 속도 | 빠름 | 느림 | | 최적해 | 조건부 보장 | 항상 보장 | | 메모리 | 적음 | 많음 (메모이제이션) | | 적용 | 특수 조건 필요 | 범용적 |
💡 그리디 적용 가능 여부 판단
그리디 사용 가능
✅ 탐욕 선택 속성 만족 ✅ 최적 부분 구조 만족 ✅ 큰 단위가 작은 단위의 배수 (거스름돈) ✅ 종료 시간 기준 정렬 (활동 선택)
그리디 사용 불가
❌ 이전 선택이 이후에 영향 ❌ 부분 최적이 전체 최적 아님 ❌ 센트 문제 (배수 관계 아님)
❓ 면접 질문 예시
Q1. 그리디 알고리즘이란 무엇인가요?
답변: 매 선택에서 현재 당장 최적인 답을 선택하여 전체 최적해를 구하는 알고리즘입니다. 눈앞의 이익만 우선 추구하며, 속도가 빠르지만 항상 최적해를 보장하지는 않습니다. 탐욕 선택 속성과 최적 부분 구조를 만족해야 최적해를 보장할 수 있습니다.
Q2. 그리디 알고리즘이 최적해를 보장하는 조건은?
답변:
- 탐욕 선택 속성: 이전 선택이 이후에 영향을 주지 않아야 합니다.
- 최적 부분 구조: 부분 문제의 최적 결과가 전체에도 적용되어야 합니다. 이 두 조건을 만족하면 그리디로 최적해를 구할 수 있습니다.
Q3. 거스름돈 문제에서 그리디가 가능한 이유는?
답변: 큰 단위 동전이 항상 작은 단위 동전의 배수이기 때문입니다. 500원은 100원의 5배, 100원은 50원의 2배, 50원은 10원의 5배입니다. 따라서 작은 단위 동전을 조합해도 큰 단위 동전보다 효율적일 수 없으므로 그리디로 최적해를 구할 수 있습니다.
Q4. 그리디와 동적 프로그래밍의 차이는?
답변: 그리디는 현재 최적 선택만 고려하여 빠르지만 조건부로 최적해를 보장합니다. 동적 프로그래밍은 모든 경우를 고려하여 느리지만 항상 최적해를 보장합니다. 그리디는 특수 조건이 필요하지만, DP는 범용적으로 사용 가능합니다.
Q5. 활동 선택 문제를 그리디로 푸는 방법은?
답변: 종료 시간이 빠른 순서로 정렬한 후, 이전 회의와 겹치지 않는 회의를 선택합니다. 종료 시간이 빠를수록 이후에 더 많은 회의를 선택할 수 있는 기회가 많아지므로 그리디로 최적해를 구할 수 있습니다.
📚 원본 참고 자료
출처: 2023-CS-Study
- 링크: algorithm_greedy.md
- 내용: 그리디 개념, 조건, 예시 문제