그리디 알고리즘으로 해결 가능한 문제를 판단하는 것은 때로는 경험이나 직감에 기반하기도 합니다. 그러나 일반적으로 다음 두 가지 주요 특성을 가진 문제들이 그리디 알고리즘을 사용하여 해결될 가능성이 높습니다.

탐욕적 선택 속성 (Greedy Choice Property)

그리디 알고리즘은 매 단계에서 가장 최적이라고 생각되는 선택을 합니다. 즉, 현재 상황에서 가장 좋은 선택을 함으로써 문제를 해결해 나가는 방법입니다. 따라서, 매 단계의 탐욕적 선택이 최종 해답으로 이어지는 경우에 그리디 알고리즘이 효과적입니다.

최적 부분 구조 (Optimal Substructure)

주어진 문제의 최적 해결 방법이 해당 문제의 부분 문제들의 최적 해결 방법을 포함하는 경우입니다. 즉, 큰 문제의 최적의 해결책을 찾기 위해 작은 문제들의 최적의 해결책을 사용할 수 있어야 합니다.

그리디 알고리즘으로 접근하는 게 효율적인 경우

그리디 알고리즘의 대표적인 예시는 거스름돈 문제입니다.

거스름돈을 구하는 과정은 아래와 같습니다. 예를 들어, 1, 5, 10, 25원의 동전이 있을 때, 32원을 거슬러주기 위해 다음과 같이 합니다.

• 25원 동전 1개

• 5원 동전 1개

• 1원 동전 2개

이를 코드로 그대로 옮기면 아래와 같습니다.

python코드 복사def get_change(amount, coins):
    change = []
    for coin in sorted(coins, reverse=True):
        while amount >= coin:
            amount -= coin
            change.append(coin)
    return change

위의 코드에서, 매 단계에서 가능한 가장 큰 동전을 선택합니다. 이 방법은 각 단계에서 가장 최적의 선택을 함으로써 최종적으로도 최적의 해결책을 찾을 수 있습니다.

그리디 알고리즘으로 접근하는 게 효율적이지 않은 경우

반대로, 그리디 알고리즘이 비효율적인 경우도 있습니다. 대표적인 예로는 배낭 문제가 있습니다.

배낭 문제는 다음과 같습니다.

• 배낭에 담을 수 있는 최대 무게가 정해져 있고, 여러 물건들이 각각의 무게와 가치가 주어집니다.

• 물건들을 선택하여 배낭에 담을 때, 가치의 합이 최대가 되도록 해야 합니다.

그리디 알고리즘을 사용하여 가치가 가장 높은 물건부터 선택하면 항상 최적의 해결책을 찾을 수 없습니다. 예를 들어, 다음과 같은 물건들이 있다고 합시다.

• 물건 A: 무게 3, 가치 4

• 물건 B: 무게 2, 가치 2

• 물건 C: 무게 1, 가치 1

배낭의 최대 무게가 3이라면, 그리디 알고리즘은 물건 A를 선택할 것입니다. 그러나, 최적의 해결책은 물건 B와 물건 C를 선택하여 가치를 3으로 만드는 것입니다. 이처럼, 그리디 알고리즘이 항상 최적의 해결책을 보장하지 않는 경우도 있습니다.

이러한 이유로 배낭 문제는 동적 계획법을 사용하여 해결하는 것이 더 적합합니다.