11주차
현재 상황에서 가장 좋아 보이는 선택을 반복하여 최종 해답을 구하는 알고리즘입니다.
- 매 순간 가장 최선이라고 판단되는 선택을 합니다.
- 한 번 선택한 결정은 되돌리지 않습니다.
- 모든 경우를 탐색하지 않기 때문에 완전 탐색보다 훨씬 빠르게 답을 구할 수 있습니다.
- 단, 현재의 최선 선택이 전체 최적해로 이어진다는 보장이 있어야 사용할 수 있습니다.
Greedy는 말 그대로 “욕심쟁이 알고리즘”입니다.
미래의 모든 경우를 계산하지 않고, 지금 당장 가장 유리해 보이는 선택을 계속 반복합니다.
이렇게 하면 복잡한 문제를 단순한 선택의 반복으로 바꿀 수 있습니다.
예를 들어, 거스름돈을 줄 때 가장 큰 동전부터 사용하는 방식이 Greedy의 대표적인 예시입니다.
거스름돈 760원
→ 500원 선택
→ 100원 선택
→ 100원 선택
→ 50원 선택
→ 10원 선택
이처럼 현재 남은 금액에서 사용할 수 있는 가장 큰 동전을 계속 고르면 빠르게 답을 구할 수 있습니다.
- 현재 상황에서 가장 좋아 보이는 선택을 합니다.
- 이전 선택을 다시 취소하거나 수정하지 않습니다.
- 보통 정렬, 우선순위 큐, 조건 분기와 함께 자주 사용됩니다.
- 정답을 빠르게 구할 수 있지만, 모든 문제에 적용할 수 있는 것은 아닙니다.
- Greedy가 성립하려면 문제에 탐욕 선택 속성과 최적 부분 구조가 있어야 합니다.
1. 탐욕 선택 속성
- 현재 단계에서 가장 최선인 선택을 해도 전체 최적해를 구할 수 있어야 합니다.
- 즉, “지금 가장 좋아 보이는 선택”이 나중에 손해가 되지 않아야 합니다.
2. 최적 부분 구조
- 큰 문제의 최적해가 작은 문제들의 최적해로 구성될 수 있어야 합니다.
- 현재 선택 이후 남은 문제도 같은 방식으로 최적으로 풀 수 있어야 합니다.
완전 탐색은 가능한 모든 경우를 확인합니다.
모든 경우를 확인 → 가장 좋은 답 선택
장점은 정답을 확실히 찾을 수 있다는 점입니다.
하지만 경우의 수가 많아지면 시간이 너무 오래 걸릴 수 있습니다.
Greedy는 매 순간 가장 좋아 보이는 선택만 합니다.
현재 최선 선택 → 다음 현재 최선 선택 → 반복
모든 경우를 확인하지 않기 때문에 빠릅니다.
하지만 현재의 선택이 전체 최적해로 이어진다는 보장이 없으면 틀릴 수 있습니다.
| 구분 | 완전 탐색 | Greedy |
|---|---|---|
| 방식 | 모든 경우 탐색 | 현재 최선 선택 반복 |
| 속도 | 느릴 수 있음 | 빠름 |
| 정답 보장 | 대부분 보장 | 조건이 맞을 때만 보장 |
| 핵심 | 빠짐없이 확인 | 선택 기준 설계 |
-
문제에서 “최소 개수”, “최대 개수”, “가장 적은 비용”, “가장 빠른 시간” 같은 최적값을 요구한다면?
➡ Greedy 가능성 확인 -
매 단계에서 하나를 선택해야 하고, 그 선택을 되돌릴 필요가 없다면?
➡ Greedy 의심 -
정렬한 뒤 앞에서부터 또는 뒤에서부터 선택하면 답이 나올 것 같다면?
➡ Greedy + 정렬 -
가장 작은 값 또는 가장 큰 값을 계속 꺼내야 한다면?
➡ Greedy + 우선순위 큐
Greedy 문제는 대부분 “어떤 기준으로 선택할 것인가?”를 묻는 경우가 많습니다.
1. 자주 나오는 문제 형태
- 회의 시간이 주어졌을 때 최대한 많은 회의 선택하기
- 사람들의 몸무게가 주어졌을 때 최소한의 보트 수 구하기
- 제한 조건에 맞게 가장 많은 작업 처리하기
2. 접근 방법
- 문제에서 가장 중요한 기준을 찾습니다.
- 해당 기준으로 배열을 정렬합니다.
- 앞에서부터 또는 뒤에서부터 조건에 맞는 선택을 합니다.
- 선택한 결과가 이후 선택에 영향을 주는지 확인합니다.
예를 들어 회의실 배정 문제에서는 “빨리 끝나는 회의”를 먼저 선택하는 것이 중요합니다.
빨리 끝나는 회의를 선택해야 뒤에 더 많은 회의를 배치할 수 있기 때문입니다.
회의 종료 시간이 빠른 순서로 정렬
→ 선택 가능한 회의 중 가장 빨리 끝나는 회의 선택
→ 다음 회의 탐색
1. 자주 나오는 문제 형태
- 거스름돈을 최소 동전 개수로 만들기
- 가장 큰 수 만들기
- 가장 작은 비용으로 작업 처리하기
2. 접근 방법
- 선택 가능한 값 중 가장 유리한 값을 고릅니다.
- 선택 후 남은 문제를 다시 같은 방식으로 처리합니다.
- 더 이상 선택할 수 없을 때까지 반복합니다.
예를 들어 거스름돈 문제에서는 가장 큰 동전부터 선택합니다.
남은 금액보다 작거나 같은 가장 큰 동전 선택
→ 남은 금액 감소
→ 반복
다만 이 방식은 동전 단위가 Greedy에 맞게 구성되어 있을 때만 항상 정답이 됩니다.
1. 자주 나오는 문제 형태
- 가장 작은 값 두 개를 계속 합치기
- 가장 우선순위가 높은 작업부터 처리하기
- 최소 비용을 반복적으로 선택하기
2. 접근 방법
- 데이터를 우선순위 큐에 넣습니다.
- 가장 작은 값 또는 가장 큰 값을 꺼냅니다.
- 문제 조건에 맞게 처리한 뒤, 필요한 경우 다시 큐에 넣습니다.
- 조건을 만족할 때까지 반복합니다.
대표적으로 “더 맵게” 문제처럼 가장 작은 값을 계속 꺼내서 처리해야 하는 문제에서 자주 사용됩니다.
전체 학생 수
n, 체육복을 잃어버린 학생 배열lost, 여벌 체육복을 가진 학생 배열reserve가 주어집니다.
여벌 체육복이 있는 학생은 바로 앞 번호 또는 바로 뒷 번호 학생에게만 체육복을 빌려줄 수 있습니다.
체육 수업을 들을 수 있는 학생의 최댓값을 반환하라!
이 문제는 현재 학생에게 체육복을 빌려줄 수 있는 학생이 있는지 확인하고, 가능한 경우 바로 빌려주는 방식으로 해결할 수 있습니다.
핵심은 다음과 같습니다.
- 여벌 체육복을 가져왔지만 도난당한 학생은 자기 자신이 입어야 하므로 빌려줄 수 없습니다.
- 잃어버린 학생들을 번호 순서대로 확인합니다.
- 앞 번호 학생이 빌려줄 수 있으면 먼저 빌립니다.
- 앞 번호가 불가능하면 뒷 번호 학생에게 빌립니다.
- 빌려준 학생은 더 이상 다른 학생에게 빌려줄 수 없도록 처리합니다.
왜 앞 번호부터 확인할까요?
학생을 번호 순서대로 처리할 때, 현재 학생의 앞 번호 학생은 이후 학생에게 영향을 줄 가능성이 거의 없습니다.
반면 뒷 번호 학생은 다음 학생에게도 빌려줄 수 있습니다.
따라서 앞 번호 학생이 빌려줄 수 있다면 먼저 사용하는 것이 안전합니다.
n = 5
lost = [2, 4]
reserve = [1, 3, 5]
1. 초기 상태
1번: 여벌 있음
2번: 체육복 없음
3번: 여벌 있음
4번: 체육복 없음
5번: 여벌 있음
2번 학생은 1번 또는 3번에게 빌릴 수 있습니다.
2. 2번 학생 처리
2번 학생은 앞 번호인 1번 학생에게 빌릴 수 있습니다.
1번 → 2번에게 체육복 대여
이제 1번 학생은 더 이상 여벌이 없습니다.
3. 4번 학생 처리
4번 학생은 앞 번호인 3번 또는 뒷 번호인 5번에게 빌릴 수 있습니다.
앞 번호인 3번 학생이 여벌을 가지고 있으므로 3번에게 빌립니다.
3번 → 4번에게 체육복 대여
4. 결과
1번: 수업 가능
2번: 수업 가능
3번: 수업 가능
4번: 수업 가능
5번: 수업 가능
모든 학생이 체육 수업을 들을 수 있으므로 정답은 5입니다.
⏱️ 시간 복잡도 :
O(N log N)
잃어버린 학생 배열을 정렬하기 때문에O(N log N)이 걸립니다.
이후 학생들을 한 번씩 확인하는 과정은O(N)입니다.
def solution(n, lost, reserve):
# 여벌이 있지만 도난당한 학생은 자기 체육복을 입어야 하므로 제외
real_lost = sorted(set(lost) - set(reserve))
real_reserve = set(reserve) - set(lost)
# 체육복을 잃어버린 학생들을 번호 순서대로 확인
for student in real_lost:
# 앞 번호 학생이 빌려줄 수 있다면 먼저 빌림
if student - 1 in real_reserve:
real_reserve.remove(student - 1)
# 앞 번호가 안 되면 뒷 번호 학생에게 빌림
elif student + 1 in real_reserve:
real_reserve.remove(student + 1)
# 둘 다 불가능하면 체육 수업을 들을 수 없는 상태로 남음
else:
n -= 1
return n코드 해설:
-
set(lost) - set(reserve)를 통해 체육복을 잃어버렸고 여벌도 없는 학생만 남깁니다. -
set(reserve) - set(lost)를 통해 실제로 다른 학생에게 빌려줄 수 있는 학생만 남깁니다. - 잃어버린 학생을 번호 순서대로 확인하면서 앞 번호, 뒷 번호 순서로 체육복을 빌립니다.
- 빌릴 수 없는 학생이 생길 때마다 전체 학생 수
n에서 1을 뺍니다.
function solution(n, lost, reserve) {
const lostSet = new Set(lost);
const reserveSet = new Set(reserve);
// 여벌이 있지만 도난당한 학생 처리
for (const student of lost) {
if (reserveSet.has(student)) {
lostSet.delete(student);
reserveSet.delete(student);
}
}
// 번호 순서대로 처리하기 위해 정렬
const realLost = [...lostSet].sort((a, b) => a - b);
for (const student of realLost) {
// 앞 번호 학생이 빌려줄 수 있다면 먼저 빌림
if (reserveSet.has(student - 1)) {
reserveSet.delete(student - 1);
}
// 앞 번호가 안 되면 뒷 번호 학생에게 빌림
else if (reserveSet.has(student + 1)) {
reserveSet.delete(student + 1);
}
// 둘 다 불가능하면 수업을 들을 수 없음
else {
n--;
}
}
return n;
}코드 해설:
-
Set을 사용해 도난당한 학생과 여벌이 있는 학생을 관리합니다. - 도난당했지만 여벌도 있는 학생은 자기 체육복을 입어야 하므로 두 집합에서 모두 제거합니다.
- 이후 실제로 체육복이 없는 학생만 번호 순서대로 처리합니다.
- 체육복을 빌려준 학생은
reserveSet에서 제거하여 중복 대여를 막습니다.
import java.util.*;
class Solution {
public int solution(int n, int[] lost, int[] reserve) {
Set<Integer> lostSet = new HashSet<>();
Set<Integer> reserveSet = new HashSet<>();
for (int student : lost) {
lostSet.add(student);
}
for (int student : reserve) {
reserveSet.add(student);
}
// 여벌이 있지만 도난당한 학생 처리
for (int student : reserve) {
if (lostSet.contains(student)) {
lostSet.remove(student);
reserveSet.remove(student);
}
}
// 번호 순서대로 처리하기 위해 정렬
List<Integer> realLost = new ArrayList<>(lostSet);
Collections.sort(realLost);
for (int student : realLost) {
// 앞 번호 학생이 빌려줄 수 있다면 먼저 빌림
if (reserveSet.contains(student - 1)) {
reserveSet.remove(student - 1);
}
// 앞 번호가 안 되면 뒷 번호 학생에게 빌림
else if (reserveSet.contains(student + 1)) {
reserveSet.remove(student + 1);
}
// 둘 다 불가능하면 수업을 들을 수 없음
else {
n--;
}
}
return n;
}
}코드 해설:
-
HashSet을 사용하여 학생 번호를 빠르게 확인합니다. - 체육복을 잃어버렸지만 여벌이 있는 학생은 먼저 제외합니다.
- 남은 도난 학생을 오름차순으로 정렬한 뒤 앞 번호, 뒷 번호 순서로 체육복을 빌립니다.
- 빌려준 학생은
reserveSet에서 제거하여 한 번만 빌려줄 수 있게 합니다.
Greedy는 매 순간 최선의 선택을 하는 방식이지만, 모든 문제에서 정답을 보장하지는 않습니다.
예를 들어 동전 단위가 [1, 3, 4]이고 거스름돈이 6이라면, 가장 큰 동전부터 고르면 다음과 같습니다.
4 + 1 + 1 = 3개
하지만 실제 최적해는 다음과 같습니다.
3 + 3 = 2개
즉, 현재 가장 좋아 보이는 선택이 항상 전체 최적해가 되는 것은 아닙니다.
따라서 Greedy를 사용할 때는 선택 기준이 정답을 보장하는지 확인해야 합니다.
Greedy 문제에서는 정렬 기준이 매우 중요합니다.
회의실 배정 문제에서는 시작 시간이 빠른 순서가 아니라, 종료 시간이 빠른 순서로 정렬해야 합니다.
빨리 끝나는 회의를 먼저 선택해야 뒤에 더 많은 회의를 배치할 수 있기 때문입니다.
잘못된 기준: 시작 시간이 빠른 회의부터 선택
올바른 기준: 종료 시간이 빠른 회의부터 선택
정렬 기준을 잘못 잡으면 코드가 맞아 보여도 정답이 틀릴 수 있습니다.
Greedy에서는 한 번 사용한 값이나 선택한 대상은 다시 사용할 수 없는 경우가 많습니다.
체육복 문제에서 한 학생이 여벌 체육복을 두 명에게 빌려줄 수는 없습니다.
따라서 빌려준 학생은 반드시 후보 목록에서 제거해야 합니다.
real_reserve.remove(student - 1)이 처리를 하지 않으면 한 명이 여러 번 빌려주는 잘못된 결과가 나올 수 있습니다.
체육복 문제에서는 여벌 체육복이 있지만 도난당한 학생이 있을 수 있습니다.
이 학생은 다른 사람에게 빌려줄 수 없고, 자기 자신이 입어야 합니다.
따라서 본격적인 대여 로직 전에 반드시 제외해야 합니다.
real_lost = set(lost) - set(reserve)
real_reserve = set(reserve) - set(lost)이 예외 처리를 하지 않으면 정답보다 더 많은 학생이 수업을 들을 수 있다고 잘못 계산할 수 있습니다.
Greedy 문제는 단순히 “이렇게 하면 될 것 같다”로 풀면 위험합니다.
반드시 다음 질문에 답할 수 있어야 합니다.
왜 지금 이 선택을 해도 나중에 손해가 없을까?
왜 이 선택이 전체 최적해로 이어질까?
이 이유를 설명할 수 없다면 Greedy가 아니라 완전 탐색, DP, BFS 등의 다른 방법이 필요할 수 있습니다.
Greedy는 매 순간 가장 좋아 보이는 선택을 반복하여 답을 구하는 알고리즘입니다.
다만 핵심은 “가장 좋아 보이는 선택” 자체가 아니라,
그 선택이 전체 최적해를 보장하는지 판단하는 것입니다.
따라서 Greedy 문제를 풀 때는 다음 순서로 접근하는 것이 좋습니다.
- 어떤 값을 최적화해야 하는지 확인합니다.
- 매 순간 어떤 기준으로 선택할지 정합니다.
- 그 선택이 나중에 손해가 되지 않는지 확인합니다.
- 정렬, 우선순위 큐, Set 등을 사용해 효율적으로 구현합니다.
⏱️ Greedy의 시간 복잡도
문제에 따라 다르지만, 보통 정렬이 포함되면O(N log N),
단순 순회만 하면O(N)으로 해결할 수 있습니다.