그리디 알고리즘 (Greedy Algorithm)

문제를 해결할 때 각 단계에서 그 순간에 최선이라고 생각되는 선택을 하는 방식

이 과정에서 얻은 선택들이 모여 전체 문제에 대한 최적의 해를 구하는알고리즘

그리디 알고리즘은 지역적최적해(Local Optimal Solution)를 찾는 과정 에서, 이를 모아 전역적 최적해(Global Optimal Solution)를 구하는 방식 

다만, 모든 경우에 전역 최적해를 보장하지는않음

 

 

예를들어12100원짜리물건을구매할때내가가지고있는돈이다음과같다고해봅시다.

10000원 5개 5000원 5개 1000원 5개 100원 5개 라고 했을때 가장지폐를적게내는(동전도지폐라고취급)경우의수는무엇일까요? 

바로 10000원 1개. 1000원 2개. 100원 1개.를 내는 것입니다. 이렇게 우리는 가장 큰 것부터 내면 최적해라는것을경험상압니다. 이걸코드로나타내면돈을내림차순정렬하고순차적으로뽑아내면되는것이죠

#include <bits/stdc++.h> // C++ 표준 라이브러리 포함
using namespace std;

int ret, totalAmount = 12100; // ret: 사용한 화폐의 총 개수, totalAmount: 목표 금액

int main() {
    // **화폐 단위와 각 화폐의 개수를 저장한 벡터**
    // {화폐 단위, 해당 화폐의 보유 개수} 형태로 저장
    vector<pair<int, int>> currency = {
        {10000, 5}, // 10,000원권 5장
        {5000, 5},  // 5,000원권 5장
        {1000, 5},  // 1,000원권 5장
        {100, 5}    // 100원 동전 5개
    };

    // **화폐 단위를 내림차순으로 정렬**
    // 큰 화폐부터 처리하기 위해 정렬 (sort + rbegin(), rend() 사용)
    sort(currency.rbegin(), currency.rend());

    // **화폐를 사용해 목표 금액을 맞추는 로직**
    for (auto &c : currency) { // 모든 화폐 단위를 순회
        while (totalAmount >= c.first && c.second > 0) { // 화폐를 사용할 수 있을 때까지 반복
            totalAmount -= c.first; // 목표 금액에서 화폐 단위만큼 차감
            c.second--;             // 해당 화폐의 보유 개수 감소
            ret++;                  // 사용한 화폐 개수 증가
        }
    }

    // **결과 출력**
    if (totalAmount == 0) {
        // 목표 금액을 정확히 맞춘 경우
        cout << ret << '\n'; // 사용된 화폐의 총 개수 출력
    } else {
        // 목표 금액을 맞출 수 없는 경우
        cout << "불가능합니다. \n";
    }

    return 0;
}

주석 추가 내용

1. 전역 변수
   • ret: 사용된 화폐의 총 개수.
   • totalAmount: 맞춰야 할 목표 금액(12100원).
2. 화폐 정보
   • currency 벡터: 각 화폐 단위와 보유 개수를 pair로 저장.
     • 예: {10000, 5}는 10,000원권 5장을 의미.
3. 정렬
   • sort(currency.rbegin(), currency.rend()):
     • 화폐 단위를 내림차순으로 정렬하여 큰 화폐부터 사용할 수 있도록 설정.
4. 화폐 사용 로직
   • 반복문:
     • 큰 화폐부터 사용하여 목표 금액(totalAmount)을 맞춤.
     • 조건: totalAmount >= c.first && c.second > 0:
       • 목표 금액이 현재 화폐 단위보다 크거나 같고, 해당 화폐를 사용할 수 있는 경우.
   • 화폐를 사용할 때마다:
     • totalAmount에서 현재 화폐 단위만큼 차감.
     • 해당 화폐의 보유 개수를 감소.
     • 사용한 화폐 개수(ret) 증가.
5. 결과 출력
   • totalAmount == 0:
     • 목표 금액을 정확히 맞춘 경우 사용한 화폐 개수를 출력.
   • totalAmount != 0:
     • 목표 금액을 맞출 수 없는 경우 "불가능합니다" 출력.

---

그리디의조건

1. 최적부분구조

 : 최적 부분 구조(Optimal Substructure)는 문제를 작은 부분 문제로 나눌 수 있으며, 그 부분 문제들의 최적해가모여서전체문제의최적해를이룰수있는구조

 1. 가장큰화폐단위부터선택하여부분문제로나눕니다.

 2. 선택된화폐를사용하고남은금액을다음단계의문제로넘깁니다.

 3. 이를남은금액이0원이될때까지위과정을반복하여전체문제에대한최적해를찾습니다.

     총금액:12100원 사용할수있는화폐:10000원5개,5000원5개, 1000원 5개, 100원 5개

 

이렇게 작은 단계들로 나누고 그단계에서의최적해가모여전체문제의최적해를만들어낼수있는 구조

 

 

2. 탐욕 선택속성

탐욕선택속성이란 각 단계에서의 최적 선택이 전체 문제에 대해서도 최적의 해를 보장한다는 것을 의미

그 순간 가장 최적인 선택을 하는 것이전체문제를푸는데있어서도최적의결과를낳는다는 것을 말함

앞서 설명한 12100원 문제에서 만약 10000원짜리가 아니라 8000원짜리 5개가 있다고 가정한다면 “각 정점에서 가장 큰 지폐를 쓰는 것"은 올바른 명제가 아니게 됨.

8000원짜리 1개, 1000원짜리 4개, 100원짜리 1개. 총 6개를 쓰게 되는데 이경우5000원짜리2개, 1000원짜리 2개, 100원짜리 1개를 썼을 때의 5개보다 더 많은 지폐를 쓰게 되는 반례가 있기 때문

 

그리디는 틀릴 가능성이 높은 알고리즘

그래서 안전하게 다음과 같은 플로우로 그리디를시도해야함

무식하게시도하기->DP->그리디 팁

 

팁

그리디 알고리즘을 쉽게 구축하는 방법 중하나는자주나오는풀이를외우고그걸기반으로 풀어야 함

보통 그리디는 정렬, 우선순위 큐를사용하는2가지의방법이주로 나옴