[C++] Greedy Algorithm (욕심쟁이 알고리즘) 정리

Greedy

각 단계에서 가장 좋은 선택을 하는 방식으로 문제를 해결하는 방식

 

 

Greedy는 Approximation Algorithm이다.

항상 현재 단계에서 최적인 선택을 하는 것이 최종 결과도 최적임을 보장하지는 않지만, 대부분의 경우에는 빠르고 효율적인 결과를 제공

 

---

 

Greedy 기법을 쓸 수 있는 지 어떻게 확인?

→ 수학적으로 검증 가능

 

1. Greedy Choice Property 성립
2. Optimal Substructure 형태를 갖고 있음

 

 

Greedy 알고리즘의 접근방법

• Selection (선택)
  • 문제에서 가능한 선택지를 파악하고, 이를 선택할 때 기준이 될 가치 평가 기준을 설정

 

• Validation (검증) - Greedy 조건 성립 여부 검증
  • 알고리즘이 항상 최적해를 구하는지 검증하기 위해, 여러 예제 케이스를 이용해 알고리즘의 정확성을 검증
  • 실제로, 두 가지 조건 중 하나 이상이 성립해야 함
    1. Greedy Choice Property: 각 단계에서 가장 최적인 선택을 하면, 전체 문제에 대한 최적해를 구할 수 있어야 함
    2. Optimal Substructure: 전체 문제의 최적해가 부분 문제의 최적해로 구성될 수 있어야 함

 

• Implementation (구현)
  • 선택과 가치 평가 기준을 기반으로 구현을 진행

 

 

• Verification (확인) - 구현한 알고리즘의 정확성 검증
  • 구현한 알고리즘을 검증하고, 최적의 해를 제공하는지 확인
  • 최적의 해가 아닐 때 방법
    1. Selection 단계로 돌아가 가치 평가 기준을 바꿔본다
    2. Greedy가 성립하지 않는 문제라, 다른 접근 방식 선정

 

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

// 거스름돈 예시
/*
1500 4
100 50 10 500
*/

bool cmp(int left, int right) {
    if (left > right)
        return true;
    if (left < right)
        return false;
    return false; 
}

int target; // 거스름돈
int N; // 동전의 수
int coins[5]; 

int main() {
    cin >> target;
    cin >> N; 
    // 동전 입력 
    for (int i = 0; i < N; i++)
        cin >> coins[i]; 

    // S : 탐욕적으로 가장 큰 단위의 동전부터 돌려준다! 
    sort(coins, coins + N, cmp); 

    int ans = 0; 
    for (int i = 0; i < N; i++) {
        int now = coins[i]; 
        ans += target / now; 
        target %= now; 
    }
    cout << ans; 
}