[알고리즘] Greedy

🧐 Greedy 알고리즘이란?

• 당장 눈 앞에 보이는 최적의 상황만을 쫒는 알고리즘
• 항상 최적의 결과를 도출하는 것은 아니지만 어느 정도 최적의 해에 근사한 값을 빠르게 구할 수 있다.
• 극단적으로 문제(무조건 큰 경우, 무조건 작은 경우, 무조건 긴 경우, 무조건 짧은 경우 등)에 접근한다는 점에서 정렬 기법이 함께 사용되는 경우가 많다.
• 갈망법, 탐욕적 기법이라고도 불린다.

🎈 Greedy 알고리즘 예시

#include <iostream>

using namespace std;

int main(void) {
	int n, result = 0;
    cin >> n;
    result += n/500;
    n %= 500;
    result += n/100;
    n %= 100;
    result += n/50;
    n %= 50;
    result += n/10;
    cout << result;
    return 0;
}

그리디 알고리즘이 최적의 해를 보장하는 경우도 많으나 그렇지 않은 경우가 더 많다.
➡️ 이런 경우 다이나믹 프로그래밍(Dynamic Programming) 등의 알고리즘 기법을 적용해야 한다.