그리디 알고리즘은 여러 선택지 중에서 항상 가장 최선의 선택을 하는 알고리즘입니다. 이 알고리즘은 각 단계에서 최적의 선택을 하기 때문에 전체적인 결과가 최적이라고 보장할 수는 없지만, 종종 많은 문제에 대해 효과적인 해결책을 제공합니다.

특징

• 각 단계에서 최적의 선택을 함으로써 최종적으로 전역 최적해를 찾지 못할 수 있음
• 단순하고 효율적인 해결책을 제공해주는 경향이 있음
• 다이나믹 프로그래밍과는 다르게 최적 부분 구조를 만족하지 않아도 적용 가능

예시

아래는 그리디 알고리즘을 사용하여 주어진 동전으로 특정 금액을 거슬러 주는 문제의 예시 코드입니다.

#include <iostream>
using namespace std;

int main() {
    int coin[] = {500, 100, 50, 10};
    int money, count = 0;
    cin >> money;

    for (int i = 0; i < 4; i++) {
        count += money / coin[i];
        money %= coin[i];
    }

    cout << count;
    return 0;
}

위 코드는 500원, 100원, 50원, 10원짜리 동전으로 거슬러줘야 할 금액을 입력받아서 가장 적은 동전의 개수로 거슬러주는 방법을 제공합니다.

그리디 알고리즘은 다양한 문제에 적용될 수 있으며, 항상 최적의 해를 보장하지는 않지만 효율적인 방법으로 문제를 해결할 수 있는 강력한 도구입니다.

자세한 내용은 아래 출처를 참고하세요.

출처

• 위키피디아 - 그리디 알고리즘