그리디 알고리즘 (Greedy Algorithm)
눈앞의 이익만 우선 추구하는 알고리즘을 총칭하여 `그리디 알고리즘`이라 한다.
그리디 알고리즘은 대부분의 경우 뛰어난 결과를 도출하지 못하지만, 드물게 최적해를 보장하는 경우도 있다.
📌 그리디 알고리즘은 최적화 문제를 대상으로 한다.
최적해를 찾을 수 있으면 그것을 목표로 삼고, 찾기 어려운 경우에는 주어진 시간 내에 그런대로 괜찮은 해를 찾는 것을 목표로 한다.
do{
가장 좋아보이는 선택을 한다; (매번 최선의 선택)
} until(해 구성 완료)그리디 알고리즘은 하나의 온전한 해가 만들어질 때까지 눈앞에 가장 좋아 보이는 선택을 반복한다.
그리디 알고리즘으로 최적해가 보장되는 예
1) 최소 신장 트리 (MST)
최소 신장 트리를 위한 프림 알고리즘, 크루스칼 알고리즘은 그리디 알고리즘으로 최적해가 보장된다.
2) 회의실 배정 문제
- 회사에 회의실이 1개 있다. 여러 부서에서 회의실을 사용하므로 미리 신청을 받아 스케줄링을 한다.
- 회의실을 사용하고자 하는 부서는 원하는 회의 시작 시간과 종료 시간을 명시해 신청서를 제출한다.
- 이렇게 받은 N개의 회의 신청에 대해 회의실 사용 스케줄을 정하려고 한다.
목표: 겹치는 회의가 없게 하면서 가장 많은 수의 회의를 소화할 수 있도록 하는 것
Greedy_Schedule(S, n)
S = {(s, t), s=시작 시간, t=종료 시간}
{
t에 대한 오름차순으로 정렬하고, 이 순서대로의 번호를 다시 매김
T ← {1};
last ← 1;
for(i ← 2 ~ i≤n, i++){
if(t_last ≤ s_i){
T ← T ∪ {i};
last ← i;
}
}
return T;
}예시
다음의 8개의 회의가 신청된 상황, 각 시작 시간과 종료 시간을 종료 시간이 빠른 순서로 정렬한 결과가 다음과 같음
(3, 5), (1, 6), (6, 7), (5, 9), (8, 13), (7, 14), (12, 18), (16, 20)
알고리즘은 이 순서로 회의들을 포함시킬지 체크
- 먼저 1번 회의 `(3, 5)`는 무조건 포함
- 1번 회의가 끝나는 시간은 5
- (1, 6)은 앞선 회의와 겹치므로 제외
- (6, 7)은 겹치지 않으므로 포함
- 배정된 회의가 끝나는 시간은 7
- (5, 9) 제외
- (8, 13) 포함
- 배정된 회의가 끝나는 시간은 13
- (7, 14) 제외
- (12,18) 제외
- (16, 20) 포함
즉, 차례가 왔을 때 자신의 시작 시간이 이미 배정된 회의 중 맨 마지막에 끝나는 것보다 뒤면 포함 & 반복
배정 결과: (3, 5), (6, 7), (8, 13), (16, 20)
얼핏 직관과 어긋나 보이는 접근
∵ 가장 많은 회의를 소화하려면 회의 시간이 짧은 것을 유리하다고 생각해 소요 시간이 짧은 회의부터 고려하는 경향이 있음
📌 종료 시간을 기준으로 삼는 이유
더 많은 회의를 배정하기 위해 "앞으로 가능한 시간대를 최대한 많이 확보" 하려는 전략이기 때문
3) 그 밖의 예
- 그래프에서 최단 경로를 구하는 다익스트라 알고리즘
- 문서에서 각 원소들의 출현 빈도가 주어질 때 해당 문서를 효율적으로 압축하는 허프만 코딩 알고리즘
그리디 알고리즘으로 최적해가 보장되지 않는 예
1) 이진 트리의 최적합 경로 찾기
각 노드가 양의 가중치를 갖는 이진 트리, 트리의 내용은 사전에 알 수 없음
극단적인 예로, 가보지 않은 어떤 노드가 다른 모든 경로의 합보다 큰 가중치를 갖고 있을 수 있으므로,
모든 노드를 보기 전에는 최적해를 보장할 수 없음
만일 각 단계를 내려갈 때마다 눈앞의 이익만 좇는다면 아래와 같은 그림이 됨
- 루트에서 두 자식의 가중치를 보면 15와 60임
- 그리디 알고리즘은 60을 선택하지만, 이 경로는 한 단계 더 내려가면 리프 노드를 만나 끝남.
- 이 경로의 점수는 62점
최적 경로는 점선을 따라 내려가는 경로로 점수가 157점임.
이 문제는 DFS, BFS 방식으로 모든 노드를 확인하기 전까지 최적해 보장X
2) 보따리 문제
- 부피가 M인 보따리 (냅색, Knapsack)와 이 보따리에 넣으려 하는 n개의 물건이 있다.
- 물건 i의 부피는 `Wi`이고 이것을 보따리에 넣을 경우 `Pi`의 가치가 있다.
- 물건들의 전체 부피 합이 M 이하이면서 가치가 최대가 되도록 보따리에 물건을 넣도록 하라
Greedy_Knapsack(P[], W[], M)
// P: 가치 배열, W: 부피 배열, M: 보따리 부피
{
//P와 W를 P[i]/W[i]에 따라 내림차순(단위 부피당 가치가 큰 순서)로 정렬
beadRoom ← M; i ← 1;
while(W[i] ≤ beadRoom and i ≤ n){
X ← X ∪ {i};
beadRoom ← beadRoom - W[i];
i++;
}
return X;
}
이 코드는 보따리 용량을 초과하지 않는, 한 단위 부피당 가치가 가장 큰 물건 순서로 각 물건을 보따리에 추가
그리디 알고리즘은 조합 전체를 고려한 최적 선택을 하지 않기 때문에 항상 최적해를 보장할 수 없음
예시👇🏻
문제 설정
- 배낭 용량: 50
- 물건 A: W:10, P:60 → 가치 밀도 = 6
- 물건 B: W:20, P:100 → 가치 밀도 = 5
- 물건 C: W:30, P:120 → 가치 밀도 = 4
그리디 알고리즘
- A 선택, 남은 용량 40
- B 선택, 남은 용량 20
총 가치 = 40(A) + 20(B) = 60
최적해 = 100(B) + 120(C) = 220
이 문제는 *NP-Hard에 속하는 난제로, `0/1 보따리 문제`라고 칭함
❓ NP-Hard (Non-determinstic Polynomial-time Hard)
NP-Hard는 모든 NP 문제보다 최소한 어려운 문제들로, 다항 시간 내에 풀 수 있다는 보장이 없음
정답이 맞는지 검증은 빠를 수 있지만, 스스로 푸는 건 매우 어려움
0/1 냅색 문제처럼 겉보기엔 빨리 풀려도, 입력 크기 기준으론 지수 시간이면 NP-Hard에 속함
보따리 문제에서 물건을 자를 수 있다면, 그리디 방식으로 최적해를 보장할 수 있음
즉, 단위 부피당 가치가 가장 큰 물건 순서로 추가하다가 어떤 물건을 넣으려는 순간 보따리 용량이 초과하면,
남은 용량에 들어갈 만큼 잘라서 넣으면 됨
이 유형의 보따리 문제를 `자를 수 있는 보따리 문제 (Fractional Knapsack Problem)` 라 칭함
3) 동전 바꾸기
- 우리 나라 동전(1,5,10,50,100,500)이 있다.
- 3,256원을 가장 적은 개수의 동전을 사용해 만드려면 500원을 사용가능한 데까지 쓰면 6개가 됨
- 다음 100원 2개, 50원 1개, 5원 1개, 1원 1개로 하면 총 11개의 동전으로 만들 수 있음
= 최적해
이처럼 동전의 액면이 커지면서 바로 아래 액면의 배수가 되는 경우에는 그리디한 방식으로 최적해를 구할 수 있음
동전의 액면이 증가하면서 앞 액면의 배수가 되지 않는 경우에는 그리디한 방식으로 최적해가 보장되지 않음.
예시)
500원, 400원, 100원, 75원, 50원 동전이 있다고 가정
목표: 최소한의 동전 개수로 1,300원 만들기
- 그리디 접근: 500원 2개, 100원 3개 선택 👉 5개 사용
- 최적해: 500원 1개, 400원 2개 선택 👉 3개 사용
이 문제는 동적 프로그래밍으로 최적해를 구할 수 있음
동전 바꾸기 DP 코드
public static int coinChange(int[] coins, int amount) {
// 최소 동전 수를 저장할 배열 (무한대로 초기화)
int[] dp = new int[amount + 1];
for (int i = 0; i <= amount; i++) {
dp[i] = Integer.MAX_VALUE;
}
dp[0] = 0; // 0원을 만들기 위한 동전 수는 0개
// 각 금액에 대해 최소 동전 수 계산
for (int coin : coins) {
for (int i = coin; i <= amount; i++) {
if (dp[i - coin] != Integer.MAX_VALUE) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
// 최소 동전 수가 구해지지 않으면 -1 반환
return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}DP vs 그리디
| 동적 계획법 (DP) | 그리디 알고리즘 | |
| 원리 | 문제를 작은 부분 문제로 나누고, 그 해결을 바탕으로 큰 문제를 해결 (최적 부분 구조, 중복되는 부분 문제) | 각 단계에서 최적의 선택을 하여 문제를 해결 (전역 최적해를 구하기 위해 지역 최적해 선택) |
| 해결 방식 | 여러 가능한 해결 방법을 계산하여 가장 최적의 해를 선택 (보통 메모이제이션이나 테이블을 사용) | 각 단계에서 가능한 선택 중 가장 좋은 것을 선택 |
| 문제 유형 | 최적화 문제로 최소화, 최대화 문제에서 효과적. 중복되는 부분 문제 해결이 필요할 때. |
그리디 선택 속성을 만족할 때 사용. 각 단계에서 최적의 선택이 전체 최적을 보장하는 경우에만 유효 |
| 시간 복잡도 | O(n^2), O(nW) (예: 배낭 문제) 등 문제에 따라 다르며, 최악의 경우에도 보통 다항 시간 내 해결 |
O(n log n), O(n) 등 보통 더 효율적일 수 있음 |
| 특징 | 중간 결과들을 저장하여 중복 계산을 피함 | 각 선택에서의 최적값만 고려, 결과적으로 빠름 |