기술사 학습노트 | imt-log

기술사 학습노트› 알고리즘› 탐욕 알고리즘

Algorithm · 한장정리

[기술사토픽] 탐욕(Greedy) 알고리즘 완벽 정리 - 한장정리

그리디 알고리즘의 동작 원리, 최적성 원리, 한계 사례를 체계적으로 정리한 기술사 핵심 학습노트

그리디알고리즘탐욕알고리즘GreedyAlgorithm최적성원리최적해거스름돈문제해선택적합성검증정보관리기술사알고리즘

Ⅰ.개요

탐욕 알고리즘(Greedy Algorithm)은 매 단계에서 현재 시점에서 가장 최선으로 보이는 선택을 반복하여 최종 해를 구하는 알고리즘 설계 기법이다. 각 선택이 이후 단계에 미치는 영향을 고려하지 않고 지역 최적(Local Optimum)을 선택하는 방식으로 동작한다.

핵심 조건

탐욕 알고리즘이 전역 최적해(Global Optimum)를 보장하려면 탐욕 선택 속성(Greedy Choice Property)과 최적 부분 구조(Optimal Substructure) 두 조건이 반드시 성립해야 한다.

특성	설명
탐욕 선택 속성	현재의 최선 선택이 전체 최적해에 포함됨을 보장
최적 부분 구조	부분 문제의 최적해가 전체 문제의 최적해를 구성
비가역적 선택	한번 선택한 해는 번복하지 않음(되돌아가지 않음)

Ⅱ.동작 절차

탐욕 알고리즘은 해 선택 → 적합성 검사 → 해 검증의 3단계를 반복하는 구조로 동작한다.

단계	명칭	설명
1	해 선택(Selection)	현재 상태에서 가장 좋아 보이는 후보 선택
2	적합성 검사(Feasibility)	선택한 해가 문제 조건을 만족하는지 검증
3	해 검증(Solution Check)	현재까지 선택이 완전한 해가 되었는지 확인

거스름돈 문제 예시

500원, 100원, 50원, 10원 동전으로 730원을 거슬러 줄 때: 500원 1개 → 100원 2개 → 10원 3개 = 총 6개 동전. 매 단계에서 가장 큰 단위 동전부터 선택하면 전체 동전 수가 최소가 된다.

시험 포인트

그리디 알고리즘의 시간복잡도는 일반적으로 O(n log n) 이하로 동적계획법(DP)보다 빠르다. 단, 최적해 보장 여부를 반드시 증명해야 한다.

Ⅲ.최적해 미도출 사례

탐욕 알고리즘이 항상 최적해를 보장하지는 않는다. 탐욕 선택 속성이 성립하지 않는 경우 지역 최적이 전역 최적으로 이어지지 않는다.

문제	그리디 결과	실제 최적해	비고
배낭 문제(0/1)	가치/무게 비율 우선 선택 → 비최적	DP로 풀어야 함	분할 배낭은 그리디 가능
비표준 동전 거스름돈	1, 3, 4원으로 6원: 4+1+1=3개	3+3=2개	동전 단위 비율 불규칙 시
최단경로(일반)	지역 최솟값 선택 → 실패	다익스트라(양수 간선)	음수 간선 시 벨만포드 필요

그리디 적용 가능 문제	알고리즘
최소 신장 트리	크루스칼, 프림
최단 경로(양수 간선)	다익스트라
데이터 압축	허프만 코딩
활동 선택 문제	종료 시각 기준 정렬 후 선택

Ⅳ.결론

Conclusion

탐욕 알고리즘은 구현이 단순하고 실행 속도가 빠르다는 장점이 있으나, 모든 문제에서 최적해를 보장하지는 않는다. 탐욕 선택 속성과 최적 부분 구조가 성립하는 경우에만 적용 가능하며, 성립 여부를 수학적으로 증명해야 한다. 크루스칼·프림(MST), 다익스트라(최단경로), 허프만 코딩(압축) 등이 대표적인 그리디 알고리즘의 성공 사례이다.

블로그: 기술사 학습노트 · imt-log.tistory.com

← 알고리즘 목록