[알고리즘 공부] 그리디(Greedy) 알고리즘

그리디 알고리즘(Greedy Algorithm)

- 당장 눈앞에 보이는 최적의 상황만을 쫓는 알고리즘
- 가장 단순한 형태이며, 난이도가 매우 낮은 알고리즘 중 하나.
- 항상 최적의 결과를 도출하는 것은 아니지만 어느 정도 최적의 해에 근사한 값을 빠르게 구할 수 있음.
- 특정한 상황에 있어서는 그리디 알고리즘이 최적의 해를 보장할 수도 있음!
   가장 대표적인 예제 : 거스름돈 문제 - 무조건 더 큰 화폐 단위부터 거슬러 주는 게 최적의 해

#include <iostream>

using namespace std;

int main() {
    int n, result = 0;
    scanf("%d", &n);
    result += n/500;
    n %= 500;
    result += n/100;
    n %= 100;
    result += n/50;
    n %= 50;
    result += n/10;
    n %= 10;

    printf("%d", result);

    return 0;
}

출력

 

그리디 알고리즘은 무조건 큰/작은 경우대로, 무조건 긴/짧은 경우대로 등 극단적으로 문제에 접근한다는 점에서 정렬 기법이 함께 사용되는 경우가 많음.
대표적 예시: 크루스칼 알고리즘(모든 간선을 정렬한 후 짧은 간선부터 연결하는 최소 비용 신장 트리 알고리즘)

=> 굉장히 많은 알고리즘이 그리디 알고리즘에 속하며, 활용도가 높아 실생활 문제 해결에도 도움.

 

그러나, 그리디는 최적의 해를 보장하지 못하는 경우가 더 많음.

다이나믹 프로그래밍(DP) 등의 기타 알고리즘 기법을 적용해야 하기도 함.