Greedy 알고리즘

Greedy 알고리즘은 문제를 해결하는 데 있어 매우 빠르고 효율적인 방법 중 하나입니다. 이 알고리즘은 매 단계마다 현재 상황에서 가장 좋은 선택을 하는 방법을 택합니다. 그러나 Greedy 알고리즘이 항상 정답을 보장하지는 않기 때문에 사용 시 주의가 필요합니다.

Greedy 알고리즘의 특징

1. 정답이라는 확신이 필요: Greedy 알고리즘을 사용할 때는 매 선택이 최종 결과에 대해 최적임을 확신할 수 있어야 합니다. 각 단계에서의 최적 선택이 전체 문제의 최적 해결책으로 이어지지 않는다면 Greedy 알고리즘은 올바른 결과를 보장하지 못합니다.
2. 반례가 있으면 사용 불가: Greedy 알고리즘을 사용하기 전에 반례가 있는지 확인해야 합니다. 만약 반례가 존재한다면, 이 알고리즘을 사용하면 올바른 해결책을 찾을 수 없습니다.
3. 비슷한 방식: 브루트포스: 브루트포스(완전 탐색)와 Greedy 알고리즘은 모두 가능한 모든 경우를 고려한다는 점에서 비슷해 보일 수 있습니다. 그러나 브루트포스는 모든 가능한 해결책을 전부 탐색하여 최적의 해를 찾는 반면, Greedy 알고리즘은 매 순간 최적의 선택만을 고려합니다.
4. 반대 방식: 동적 계획법: 동적 계획법(DP)은 큰 문제를 작은 하위 문제들로 나누어 각 하위 문제의 해를 조합하여 최적의 해결책을 찾습니다. Greedy 알고리즘은 순간의 최적 선택을 중요시하지만, DP는 전체적인 최적해를 위해 각 부분 문제의 최적해를 고려합니다.
5. 빠른 속도: Greedy 알고리즘의 가장 큰 장점 중 하나는 속도가 매우 빠르다는 것입니다. 문제의 크기가 커지더라도 비교적 짧은 시간 안에 해결책을 찾을 수 있습니다.
6. 독립적인 시행: 각 선택이 다음 선택에 영향을 주지 않는 경우, 즉 서로 간의 시행이 독립적인 경우에 Greedy 알고리즘을 사용할 수 있습니다.

대표적인 문제: 동전 거스름돈 문제

Greedy 알고리즘의 대표적인 예제로 동전 거스름돈 문제가 있습니다. 이 문제는 주어진 금액을 최소한의 동전 개수로 거슬러주는 방법을 찾는 것입니다.

문제 예시:

• 사용할 수 있는 동전의 종류가 500원, 100원, 50원, 10원이 있을 때, 1260원을 최소 동전 개수로 거슬러 주는 방법은 무엇일까요?

해결 방법: Greedy 알고리즘을 사용하여 큰 동전부터 최대한 많이 사용합니다.

#include <iostream>
#include <vector>

int main() {
    int n = 1260;
    std::vector<int> coins = {500, 100, 50, 10};
    int count = 0;
    
    for (int coin : coins) {
        count += n / coin;
        n %= coin;
    }
    
    std::cout << "최소 동전 개수: " << count << std::endl;
    return 0;
}

결과:

• 500원 동전 2개
• 100원 동전 2개
• 50원 동전 1개
• 10원 동전 1개
• 총 6개의 동전으로 1260원을 거슬러 줄 수 있습니다.

결론

Greedy 알고리즘은 빠르고 간단하게 문제를 해결할 수 있는 강력한 도구입니다. 하지만 모든 문제에 적용할 수 있는 것은 아니며, 정답임을 확신할 수 있을 때만 사용해야 합니다. 동전 거스름돈 문제처럼 각 단계에서의 최적 선택이 전체 문제의 최적 해결책으로 이어지는 경우에 적합합니다. Greedy 알고리즘을 사용할 때는 항상 반례를 고려하고, 다른 해결 방법과 비교하여 최적의 방법을 선택하는 것이 중요합니다.