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

그리디 알고리즘

: "욕심쟁이"

 = 매 순간 가장 좋아 보이는 선택을 하는 알고리즘

 = 문제를 풀 때, 지금 이 순간 최선의 선택을 하면 결국 전체적으로도 최선의 결과를 얻을 수 있다고 가정

 

한마디로, “현재의 최선 = 전체의 최선” 이라는 사고방식!

 

 

 

** 정리하자면,

1. 지금 당장 이득이 되는 선택을 한다.
2. 그 선택이 전체적으로도 최적이라는 보장은 없지만,
   문제 구조상 그것이 항상 맞게 되는 경우가 있다.
3. 그래서 ‘그리디로 풀 수 있는 문제’는 항상 그런 구조를 갖고 있어야 함.

 

---

 

대표 예시 ① 거스름돈 문제

문제:
500, 100, 50, 10원짜리 동전이 있을 때
거스름돈 1260원을 최소 개수의 동전으로 거슬러주려면?

#include <iostream>
using namespace std;

int main() {
    int n = 1260;
    int count = 0;
    int coin[] = {500, 100, 50, 10};

    for (int i = 0; i < 4; i++) {
        count += n / coin[i]; // 해당 동전 몇 개 필요한지
        n %= coin[i];          // 남은 금액 갱신
    }

    cout << "필요한 동전 개수: " << count << '\n';
}

결과:
500×2 + 100×2 + 50×1 + 10×1 = 1260 → 총 6개 동전

 

이유:
동전 단위가 항상 배수 관계(500, 100, 50, 10)이기 때문에
‘가장 큰 단위부터 쓰는 게 항상 최적’이므로 그리디로 풀 수 있는 전형적인 구조

 

대표 예시 ② 회의실 배정 문제

문제:
한 회의실에서 여러 회의가 열릴 때,
겹치지 않게 가장 많은 회의를 진행하려면?

회의 시작 종료

A	1	4
B	3	5
C	0	6
D	5	7
E	8	9

 

풀이 아이디어:
 → “빨리 끝나는 회의부터 선택” (가장 효율적이니까)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<pair<int,int>> meeting = {
        {1,4},{3,5},{0,6},{5,7},{8,9}
    };

    sort(meeting.begin(), meeting.end(), [](auto a, auto b){
        return a.second < b.second; // 종료 시간 기준 정렬
    });

    int endTime = 0, count = 0;
    for (auto [start, end] : meeting) {
        if (start >= endTime) { // 겹치지 않으면 선택
            count++;
            endTime = end;
        }
    }

    cout << "최대 회의 개수: " << count << '\n';
}

 

결과: 총 3개 회의 가능 (A, D, E)

이유:
항상 “가장 빨리 끝나는 회의”를 선택하면 뒤에 남은 시간에 더 많은 회의를 넣을 수 있기 때문.

---

* 그리디로 풀 수 있는 문제의 조건

1. 탐욕 선택 속성(Greedy Choice Property)
   • 매 순간의 최적 선택이 전체 해에도 영향을 주지 않아야 함
2. 최적 부분 구조(Optimal Substructure)
   • 부분 문제의 최적해들이 모여 전체 문제의 최적해가 되어야 함

 => 이 두 조건이 만족되면 그리디 알고리즘이 항상 정답을 보장!

 

 

그리디는 항상 ‘지금 이 순간 가장 좋아 보이는 선택’을 하는 알고리즘이야.
단, 그 선택이 전체적으로도 옳다는 보장이 있을 때만 쓸 수 있다.

 

 

 

*추가공부*

- 그리디 vs 다이나믹 프로그래밍 (DP) 차이!!!

= 둘 다 “최적해(최고의 결과)”를 찾는 알고리즘지만 접근방식에 차이가 있음

	그리디(Greedy)	다이나믹 프로그래밍(DP)
기본 개념	지금 당장 최선을 고른다	이전 결과를 저장하며 최선을 찾는다
선택 방식	한 번의 선택으로 끝	여러 경우를 고려하면서 누적
되돌리기	불가능 (돌이킬 수 없음)	능 (이전 계산 이용)
문제 구조	매 순간의 최선이 전체 최선	부분 문제의 최적해를 합쳐 전체 최적해
예시	거스름돈, 회의실 배정, 다익스트라	피보나치, 배낭 문제, 플로이드 워셜
시간 복잡도	빠름 (단순)	조금 느림 (메모리 필요)
정리하자면?	빠르고 단순하지만 정답 보장 X	느리지만 확실하게 최적해 보장

 

 

 

 

 

** 예시 문제들로 비교해보기!

그리디 알고리즘 대표 문제	다이나믹 프로그래밍 대표 문제
거스름돈 문제 가장 큰 동전부터 거슬러 주기 단위가 배수 관계이기 때문에 ‘현재 최선이 전체 최선’ 핵심 아이디어: 지금 가장 큰 단위부터 써도 전체적으로 최적해를 만든다.	피보나치 수열 F(n) = F(n-1) + F(n-2) 이전 두 값을 이용해 다음 값을 구함. 핵심 아이디어: 이전 계산 결과를 저장해서 재사용.
회의실 배정 문제 시작과 끝 시간이 주어진 회의 중, 최대한 많은 회의를 선택 빨리 끝나는 회의부터 선택하면 최적. 핵심 아이디어: 일찍 끝나는 회의를 먼저 잡으면, 뒤에 더 많은 회의를 넣을 수 있다.	0/1 배낭 문제 (Knapsack) 물건을 “담거나 안 담거나”만 선택할 수 있을 때, 무게 제한 내에서 최대 가치를 구하는 문제. 핵심 아이디어: 부분 문제의 결과를 테이블에 저장하며 최댓값 갱신.
동전 교환 (또는 ATM 인출 시간 최소화) 사람들이 인출하는 데 걸리는 시간이 있을 때, 총 대기 시간을 최소화하려면? 시간이 짧은 사람부터 인출시킨다. 핵심 아이디어: 작은 값을 먼저 처리하면 전체 합이 최소가 된다.	최장 증가 부분 수열 (LIS) 수열에서 증가하는 부분 수열 중 가장 긴 길이를 찾는 문제. 앞선 계산 결과를 이용해 확장해 나감. 핵심 아이디어: 이전에 계산한 최적 부분 길이를 이용.
크루스칼 알고리즘 (최소 신장 트리) 모든 노드를 최소 비용으로 연결하려면, 비용이 작은 간선부터 연결하되, 사이클이 생기지 않도록 한다. 핵심 아이디어: 지금 가장 비용이 적은 간선을 먼저 선택.	플로이드–워셜 알고리즘 (모든 노드 간 최단 거리) 모든 노드 쌍 간의 최단 거리를 구할 때, 중간 노드를 하나씩 거쳐가며 최적 거리 갱신. 핵심 아이디어: “현재까지의 최단 거리”를 이용해 다음 계산을 한다.
다익스트라 알고리즘 (최단 경로) 현재 가장 가까운 노드부터 탐색하며 거리를 갱신. 우선순위 큐를 이용한 전형적인 그리디 기반 알고리즘. 핵심 아이디어: 매 순간 ‘가장 짧은 거리’를 확정시켜나가는 탐욕적 선택.	정수 삼각형 문제 삼각형 꼭대기에서 시작해 아래로 내려갈 때, 합이 최대가 되도록 경로를 선택하는 문제. 핵심 아이디어: 위쪽에서 계산한 최댓값을 아래로 전파하면서 갱신.

 

거스름돈 (500,100,50,10)	✅ 그리디	큰 단위부터 쓰면 항상 최적
회의실 배정	✅ 그리디	빨리 끝나는 순으로 정렬
피보나치 수열	✅ DP	이전 값 이용해야 효율적
배낭 문제 (0/1)	✅ DP	부분 선택 불가, 조합 고려
다익스트라	✅ 그리디 + 우선순위 큐	매 순간 최소 거리 선택