<aside> <img src="/icons/list-indent_lightgray.svg" alt="/icons/list-indent_lightgray.svg" width="40px" />

Table Of Contents

</aside>

정의

그리디(Greedy)는 ‘탐욕스러운’ 또는 욕심이 많은’이라는 사전적 의미를 가진다.

그리디 알고리즘은 문제를 해결할 때 “지금 이 순간에 가장 좋아보이는 선택(=지역 최적 선택)”을 반복해서 만들어 최종 해답을 얻는 방법이다. 매 단계에서 최선이라 판단한 선택을 하고, 그 선택은 나중에 바꾸지 않는다.

이런 특성으로 ‘그리디 알고리즘은 지역 최적해를 추구한다’고 말하기도 한다.

부분적으로는 최적해를 구한다고 할 수 있어도 전체적으로 최적의 해를 구했는가에 대해서는 확실히 그렇다라고 말할 수는 없다.

핵심 아이디어

• 한 번의 선택이 앞으로의 선택에 영향을 주지만, 그 선택을 바꾸지 않고 계속 진행한다.
• “지역 최적”을 여러 번 쌓았을 때 “전역 최적(문제 전체에 대한 최적해)”이 되면 그리디 방식이 성공한다.

특징

• 보통 최적해를 구하는 알고리즘보다 빠른 경우가 많다.
• 크루스칼, 다익스트라 알고리즘 등에 사용된다.
• 직관적인 문제 풀이에 적합하다.
• 시간복잡도: 보통 O(n log n) 이하 (정렬 기반)
• 공간복잡도: O(1) ~ O(n)
• 구현이 간단해서 버그 가능성 낮음
• 하지만 "증명"이 까다로움

그리디 알고리즘이 최적해를 보장하려면?