그리디 알고리즘이란?
그리디 알고리즘은 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘이다.
가장 좋아보인다는 것은 가장 빠르거나, 저렴하거나 등과 같은 선택을 의미한다.
그리디 알고리즘은 미래는 고려하지 않는다.
즉, 현재 선택이 나중에 미칠 영향에 대해서는 고려하지 않고 선택의 순간에 가장 좋은 것을 고르는 것이다.
그렇다면 현재 상황에서 가장 좋아 보인 것을 고른 것이 결론적으로 좋은 결과를 도출할까? 아니다.
현재의 최적해가 전체의 최적해를 의미하지는 않는다.
전체의 최적해가 보장되는 조건에서만 그리디 알고리즘을 써야 한다.
그렇다면 어떤 조건에서 그리디 알고리즘이 유효할까?
그리디 알고리즘이 유효한 조건
그리디 알고리즘이 전체의 최적해를 보장하려면 두 가지 속성이 필요하다.
1. 그리디 선택 속성(Greedy Choice Property)
현재의 선택이 이후의 결정에 영향을 주지 않고, 전체 문제를 해결하는 데 최적의 선택이 되어야 한다.
2. 최적 부분 구조(Optimal Substructure)
문제를 작은 부분 문제들로 나눌 수 있으며,
이 부분 문제들의 최적해가 전체 문제의 최적해로 이어져야 한다.
이 두 가지 조건이 만족될 때, 그리디 알고리즘은 전체 최적해를 보장할 수 있다.
조건들이 충족되지 않으면, 그리디 알고리즘은 최적해를 찾지 못할 수도 있다.
예를 들어, 아래의 경우는 두 조건을 만족한다.
1. A-B 경로 선택이 B-C 경로 선택에 영향을 주지 않는다.
2. A-C 경로는 A-B와 B-C의 경로로 나눠 구할 수 있다.
| ⭐️포인트⭐️ 문제가 그리디로 풀리는지, 위의 두 조건으로 추론해야 한다 |
그리디 알고리즘과 정렬의 관계
그리디 알고리즘에서는 정렬이 중요한데, 그 이유는 그리디의 특성에 있다.
그리디는 문제를 해결하는 데 필요한 기준을 설정하고 이 기준에 따라 가장 좋아 보이는 선택을 반복한다.
이때 선택의 기준을 정렬된 순서에 맞춰 설정하는 것이
1.그리디 선택 속성과 2.최적 부분 구조를 만족하게 만드는 핵심 요소가 된다.
즉, 그리디 알고리즘에서 정렬은 "가장 좋아 보이는 선택"을 명확히 하기 위해 필요하다.
정렬된 상태에서 그리디 선택을 반복하게 되면, 문제의 구조가 단순해진다.
그리디 알고리즘의 대표적인 문제 유형
[1] 거스름돈
동전 거스름돈 문제에서는 동전을 금액이 큰 순서대로 정렬한 후,
가장 큰 금액의 동전부터 차례로 선택하며 개수를 구한다.
예를 들어, 500원, 100원, 50원, 10원짜리 동전이 있을 때,
760원을 거슬러 주기 위해서는 가장 큰 동전부터 차례대로 선택하는 것이 최적해를 보장한다.
→ 1)그리디 선택 속성 ✅ 2)최적 부분 구조 ✅
하지만 만약 동전의 종류가 1, 3, 4원짜리라면,
6원을 거슬러 주기 위해 4원짜리 하나와 1원짜리 두 개를 선택하는 것이 아닌,
3원짜리 두 개를 선택하는 것이 최적해가 된다.
즉, 이런 경우에는 그리디 알고리즘이 최적해를 보장할 수 없다.
→ 1)그리디 선택 속성 ❌ 2)최적 부분 구조 ✅
Tip)
거스름돈 문제에서 그리디 선택 속성이 성립하기 위해서는 동전의 금액이 서로 배수여야 한다.
동전의 금액이 서로 배수라는 것은 각 동전이 다른 동전으로 정확히 나눠떨어진다는 뜻이다.
때문에 가장 큰 동전으로 먼저 거슬러 준다면, 나머지 금액을 그보다 작은 동전을로 정확히 채울 수 있다.
배수 관계에 있기 때문에 작은 동전들이 큰 동전의 잔여 금액을 정확히 커버할 수 있다.
[2] 회의실 배정 문제
다른 예로 회의실 배정 문제를 생각해보자.
이 문제에서는 각 회의의 종료 시간을 기준으로 오름차순 정렬한 후,
가장 빨리 끝나는 회의부터 차례로 선택하는 것이 최적해를 보장한다.
종료 시간 순으로 정렬함으로써, 그리디 선택 속성을 만족시키는 선택이 가능해지며,
부분 문제로 나뉜 이후의 선택들이 모두 최적해로 이어진다.
코딩 테스트에서의 그리디 알고리즘
그리디 알고리즘은 모든 문제에 적용할 수 있는 것은 아니므로
문제를 분석하고, 그리디 알고리즘이 최적해를 보장할 수 있는 조건인지 판단하는 것이 중요하다.
- 문제를 해결할 수 있는 명확한 기준을 설정한다.
- 그 기준에 따라 반복적으로 선택을 수행한다.
- 최적해를 보장하는지 간단한 예시로 검증한다.
추천 문제
백준
| 문제 | 난이도 | 내 풀이 |
| BOJ 2720 | 세탁소 사장 동혁 | Bronze 3 | 성공 | |
| BOJ 10162 | 전자레인지 | Bronze 3 | 성공 | |
| BOJ 5585 | 거스름돈 | Bronze 2 | 성공 | |
| BOJ 4796 | 캠핑 | Bronze 1 | 성공 | |
| BOJ 2810 | 컵홀더 | Bronze 1 | 성공 | |
| BOJ 2839 | 설탕 배달 | Silver 4 | 성공 | |
| BOJ 11399 | ATM | Silver 4 | 성공 | |
| BOJ 11047 | 동전 0 | Silver 4 | 성공 | |
| BOJ 1541 | 잃어버린 괄호 | Silver 2 | 성공 | |
| BOJ 1931 | 회의실 배정 | Silver 1 | 성공 | |
| BOJ 11000 | 강의실 배정 | Gold 5 | |
| BOJ 1715 | 카드 정렬하기 | Gold 4 | |
| BOJ 1339 | 단어 수학 | Gold 4 | |
| BOJ 1744 | 수 묶기 | Gold 4 | |
| BOJ 1202 | 보석 도둑 | Gold 2 |
이코테 실전 문제 & 기출 문제
| 문제 | 분류 | 난이도 | 내 풀이 |
| 3-2 | 큰 수의 법칙 | 실전 문제 | ★☆☆ | [이코테] Chap 3-2 큰 수의 법칙 (그리디) |
| 3-3 | 숫자 카드 게임 | 실전 문제 | ★☆☆ | [이코테] Chap 3-3 숫자 카드 게임 (그리디) |
| 3-4 | 1이 될 때까지 | 실전 문제 | ★☆☆ | [이코테] Chap 3-4 1이 될 때까지 (그리디) |
| 11-1 | 모험가 길드 | 기출 문제 | ★☆☆ | |
| 11-2 | 곱하기 혹은 더하기 | 기출 문제 | ★☆☆ | |
| 11-3 | 문자열 뒤집기 | 기출 문제 | ★☆☆ | |
| 11-4 | 만들 수 없는 금액 | 기출 문제 | ★☆☆ | |
| 11-5 | 볼링공 고르기 | 기출 문제 | ★☆☆ | |
| 11-6 | 무지의 먹방 라이브 | 기출 문제 | ★☆☆ |
참고
- [책] 이것이 취업을 위한 코딩 테스트다 with 파이썬
- [유튜브] 그리디 탐욕 Greedy 알고리즘 설명 7분만에 이해하기
- [블로그] [알고리즘] 그리디 알고리즘/ 탐욕법 (Greedy algorithm)