TIL 0211

그리디 알고리즘의 개념
정의: 그리디 알고리즘은 각 단계에서 최적이라고 생각되는 선택을 하여 문제를 해결하는 방법입니다. 이 방법은 전체 문제의 최적해를 보장하지는 않지만, 많은 경우에 유용하게 사용됩니다

특징:
국소 최적 선택: 각 단계에서 가장 좋은 선택을 하여 전체 문제를 해결합니다.
단계적 접근: 문제를 여러 단계로 나누어 각 단계에서 최적의 선택을 합니다.
비교적 간단한 구현: 그리디 알고리즘은 일반적으로 구현이 간단하고 직관적입니다

C++에서의 그리디 알고리즘 예시

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

int main() {
    int amount;
    cout << "교환할 금액을 입력하세요: ";
    cin >> amount;

    // 동전의 종류
    vector<int> coins = {500, 100, 50, 10, 5, 1};
    int count = 0;

    for (int coin : coins) {
        while (amount >= coin) {
            amount -= coin; // 동전의 가치를 금액에서 차감
            count++; // 동전 개수 증가
        }
    }

    cout << "최소 동전 개수: " << count << endl;
    return 0;
}