[Algorithm] 그리디(Greedy) 알고리즘

그리디 알고리즘이란?

당장 눈 앞에 보이는 최적의 상황만 쫓는 알고리즘

항상 최적의 결과를 만들어내지는 않지만, 어느정도 최적화 된 값을 빠르게 구할 수 있다.(특정한 상황에서는 최적의 해를 보장할 수도 있다.)

거스름돈 문제같이, 무조건 큰 경우, 작은 경우 등, 차례대로 해결해 나갈 수 있는 문제에 적합하다.

구현

#include <iostream>

using namespace std;

int main(void) {
    int n; // 거스름돈의 양
    int result = 0;

    cin >> n;

    result = result + (n/500); // 몫의 양만큼 result에 더해줌 
    n = n % 500;

    result = result + (n/100); // 몫의 양만큼 result에 더해줌 
    n = n % 100;

    result = result + (n/50); // 몫의 양만큼 result에 더해줌 
    n = n % 50;

    result += n/10; // 몫의 양만큼 result에 더해줌 

    cout << result;
    
    return 0;
}

reference: https://www.youtube.com/watch?v=PNPIk3hc6ic&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=38