그리디 알고리즘 (탐욕법, Greedy Algorithm)

 

그래프 탐색이나 탐색 알고리즘과는 다르게,
선택의 기준이 핵심이 되는 알고리즘이 바로 그리디 알고리즘(Greedy Algorithm)이다.

그리디 알고리즘은 매 순간 현재 상태에서 가장 좋아 보이는 선택을 하며 문제를 해결해 나가는 방식이다.

 

구현이 비교적 쉽고 빠르기 때문에 코딩 테스트에서 자주 등장하지만,

항상 정답을 보장하지는 않는다는 점에서 주의가 필요하다.

이번 글에서는 그리디 알고리즘의 개념과 특징, 동작 과정, 그리고 사용할 때 주의할 점을 중심으로 정리해보려고 한다. ✍️

 

 

---

 

 

그리디 알고리즘이란?

그리디 알고리즘(Greedy Algorithm)은
현재 상태에서 볼 수 있는 선택지 중 최선의 선택을 반복하는 알고리즘이다.

 

즉,

• 지금 당장 가장 좋아 보이는 선택을 하고
• 그 선택이 이후의 선택에 어떤 영향을 미칠지는 고려하지 않으며
• 이 과정을 반복해 전체 문제를 해결한다

그리디 알고리즘은

“현재의 최선의 선택이 전체에서도 최선일 것이다”
라는 가정을 바탕으로 동작한다. 🔍

 

 

---

 

 

그리디 알고리즘의 특징 🔧

그리디 알고리즘은 다음과 같은 특징을 가진다.

• 현재 시점에서의 국소 최적해(Local Optimum) 를 선택
• 구현이 단순하고 직관적
• 시간 복잡도가 우수한 경우가 많음
• 항상 최적의 해를 보장하지는 않음 ⚠️

특히,
그리디 알고리즘은 동적 계획법(DP) 에 비해 구현이 훨씬 쉽고 빠르지만,
문제에 따라서는 잘못된 답을 도출할 수 있다는 단점이 있다.

따라서 코딩 테스트에서 그리디 알고리즘을 적용하기 전에는 “이 문제가 정말 그리디로 풀 수 있는 문제인가?”를 반드시 검증해야 한다.

 

 

---

 

 

그리디 알고리즘의 동작 과정 🔁

그리디 알고리즘은 다음 3단계를 반복하면서 문제를 해결한다.

 

1. 해 선택

현재 상태에서 가장 최선이라고 판단되는 해를 선택한다.

 

2. 적절성 검사

현재 선택한 해가 아래 두 가지 조건을 만족하는지 검사한다.

• 문제의 제약 조건을 위반하지 않는지
• 선택이 가능한 상태인지

3. 해 검사

현재까지 선택한 해의 집합이 전체 문제를 해결할 수 있는지 확인한다.

아직 해결되지 않았다면 → 다시 1번 해 선택 단계로 돌아가 같은 과정을 반복한다.

 

이처럼 그리디 알고리즘은 선택 → 검증 → 반복이라는 단순한 구조를 가진다.

 

 

---

 

 

그리디 알고리즘 사용 시 주의점 📌

그리디 알고리즘에서 가장 중요한 점은 그리디 선택이 항상 최적해로 이어지는지에 대한 논리적 근거이다.

아래 질문에 명확하게 답할 수 있어야 한다.

• 현재의 최선 선택이 이후 선택에 영향을 주지 않는가?
• 부분 문제의 최적해가 전체 문제의 최적해로 이어지는가?

이 조건이 만족되지 않는다면 그리디 알고리즘은 틀린 해를 만들 수 있다.

그래서 그리디 문제는
👉 “아이디어를 떠올리는 것”보다
👉 “그 아이디어가 항상 성립하는지 증명하는 것” 이 더 중요하다.

 

 

---

 

 

그리디 알고리즘이 자주 사용되는 문제들

그리디 알고리즘은 다음과 같은 유형의 문제에서 자주 사용된다.

• 거스름돈 문제
• 회의실 배정 문제
• 활동 선택 문제
• 최소 비용 / 최대 이익 문제
• 일정 스케줄링 문제

대부분 정렬 + 선택 기준이 함께 등장하는 경우가 많다.

 

+ 아래 문제들을 풀어 보시면 좋습니다!

https://www.acmicpc.net/workbook/view/12220