그리디 알고리즘

그리디 알고리즘(Greedy Algorithm) 완전 정복 가이드

그리디 알고리즘이란?

Greedy(탐욕) 알고리즘은

“현재 순간에서 가장 최선이라고 생각되는 선택을 반복하여
전체 문제를 해결하는 알고리즘”

즉,

• 미래 상황은 고려하지 않고
• 지금 당장 가장 좋은 선택만을 계속해서 선택하는 방식이다.

---

그리디 알고리즘의 핵심 개념

- 지역 최적(Local Optimum)

매 과정에서 선택한 현재 시점에서의 최선의 선택

- 전역 최적(Global Optimum)

문제가 요구하는 최종적인 최선의 답

- 그리디의 성립 조건 (중요)

그리디 알고리즘은 모든 문제에 적용할 수 없다.
다음 조건을 만족할 때만 최적해를 보장한다.

1. 탐욕적 선택 속성(Greedy Choice Property)
   • 지금 내리는 최선의 선택이
     나중에도 최선의 답을 만드는 데 문제 없음
2. 최적 부분 구조(Optimal Substructure)
   • 문제를 부분 문제로 나눴을 때
     부분 문제들의 최적해 조합이 전체 문제의 최적해가 됨

이 두 조건을 만족하지 않으면
→ 그리디는 '빠른 오답 생성기'가 된다.

---

그리디 알고리즘의 일반적인 흐름

1. 문제를 정렬하거나, 규칙을 정의한다.
2. 현재 시점에서 가장 이득이 되는 선택을 한다.
3. 그 선택을 확정한다(취소하지 않음).
4. 남은 문제에 대해 1~3을 반복한다.

특징:

• 되돌리지 않는다(Backtracking 없음)
• 경우의 수 계산을 하지 않는다
• 시간 복잡도가 빠르다 (대부분 O(N log N) 또는 O(N))

---

가장 유명한 예시로 이해하기

 예시 1: 동전 최소 개수 문제

동전 종류가 [500, 100, 50, 10] 이고
금액 1260원을 만들 때
동전 개수를 최소로 사용하려면?

• 가장 큰 동전부터 사용한다 (Greedy)
• 500 → 500 → 100 → 100 → 50 → 10 → 0

이유:
큰 동전 먼저 사용해도
나중에 불리하지 않다는 “탐욕적 선택 속성”이 성립하기 때문

---

예시 2: 구명보트 문제

문제: 제한 무게 이하로 2명까지 태우는데 보트를 최소로 사용하기

해결법 → 가장 무거운 사람 + 가장 가벼운 사람 조합 시도

이유

• 가장 무거운 사람을 살리는 게 전체적으로 이득
• 무거운 사람끼리는 절대 limit 이하가 안되므로 조합이 불가능
• 가장 가벼운 사람은 누구에게나 붙을 가능성이 높음
• 따라서 무거운 사람과 가벼운 사람을 묶는 것이
  전체적으로 최선의 선택이 됨

이를 구현하는 것이 투 포인터(two pointers) 그리디 전략

---

예시 3: 회의실 배정 문제

“가장 빨리 끝나는 회의”를 먼저 선택하면
전체적으로 가장 많은 회의를 배정할 수 있다.

 

---

그리디 알고리즘의 장점과 단점

장점

• 구현이 쉽다
• 빠르다
• 대부분 정렬 + 반복으로 해결

단점

• 항상 정답을 보장하지 않는다
• 문제 구조를 이해하지 않으면 오답이 발생함
• 탐욕적 선택 속성이 성립하지 않으면 절대 불가능

 

핵심 정리

그리디 = “현재 순간 최선”을 반복하여 전체 최선의 답을 구하는 알고리즘.
단, 이 선택이 전체적으로도 최선이라는 보장이 있어야만 사용 가능하다.