3.6 Greedy Algorithms

CS - 3. Common Algorithms - 3.6 Greedy Algorithms

 

Greedy Algorithms

💡Greedy algorithms are a type of algorithm that always makes the choice that seems to be the best at that moment. This means that it makes a locally-optimal choice in the hope that this choice will lead to a globally-optimal solution.

욕심 알고리즘은 항상 그 순간에 최선인 것처럼 보이는 선택을 하는 알고리즘의 한 유형입니다. 즉, 이 선택이 전 세계적으로 최적의 솔루션으로 이어지기를 바라며 국지적으로 최적의 선택을 하는 것입니다.

 

코테, 알고리즘 공부 하면 가장 유명한 그리디 알고리즘, 욕심 알고리즘 입니다.

그리디 알고리즘(Greedy Algorithm)은 최적화 문제를 해결하는 알고리즘 중 하나로, 각 단계에서 지역적으로 최적의 선택을 하며 이를 통해 전역적인 최적해를 찾아내는 방법입니다. 

이러한 선택은 각 단계에서 이후의 선택에 영향을 미치며, 선택이 이루어지면 취소할 수 없습니다.

그리디 알고리즘의 핵심은 "현재의 선택이 이후의 선택과는 독립적이며, 현재의 선택이 최종 결과에 영향을 미친다"는 것입니다. 

그리디 알고리즘은 항상 최적의 해를 찾아주는 것은 아니지만, 특정 문제에서는 효과적일 수 있습니다.

예를 들어, 거스름돈 문제를 그리디 알고리즘으로 풀 수 있습니다. 

가장 큰 단위의 동전부터 최대한 사용하여 거스름돈을 만드는 것이 최적의 해를 찾는 방법입니다.

In Python

 

방금 위의 거스름돈 문제를 풀어 보겠습니다.

 

사용한 모든 동전의 갯수가 최소가 되도록 원한다는 가정하에, (이 가정이 차후설명에 중요합니다.)

def change(c):
    coins = [500, 100, 50, 10] # 동전의 종류
    count = {500: 0, 100: 0, 50: 0, 10: 0}
    for coin in coins:
        num = c // coin
        count[coin] = num
        c %= coin
    return count

 

가장큰 500원으로 // 더이상 나눠지지 않을떄까지 나눈뒤, 나머지를 다시 다음 100원으로 나누고.. 이런 논리로 반복합니다.

이런경우는 너무나도 깔끔한 경우입니다.

 

그리디 알고리즘은 항상 최적의 해를 보장하지는 않는다.

 

그런데 앞에서 '그리디 알고리즘은 항상 최적의 해를 보장하지는 않는다.' 라고 하였습니다.

def change(c):
    coins = [10, 7, 1] # 동전의 종류
    count = {10: 0, 7: 0, 1: 0}
    for coin in coins:
        num = c // coin
        count[coin] = num
        c %= coin
    return count

예를들어 14를 10, 7, 1 동전으로 나눈다고 생각해 봅시다.

 

 

앞에서 요구했던 답은 사용한 모든 동전의 개수가 최소가 되도록 입니다.

(물론 코드를 바꾸면 가능합니다.)

그리디 알고리즘에 따르면

14원을 10원 1개로 나눈 뒤 4원은 7원동전으로 나눌수 없으니 1원 동전 4개로 처리하였습니다.

 

하지만, 7원 2개를 사용한다면 가장 최소의 동전개수 2개로 처리할 수 있습니다.

 

왜?

그리디 알고리즘은 항상 최적의 해를 보장하지 않지만 왜? 사용할까요?

 

크게 3가지 이유가 있습니다.

 

1.계산 속도

그리디 알고리즘은 각 단계에서 최적의 선택을 하므로, 다른 알고리즘에 비해 계산 속도가 빠릅니다.

따라서 문제의 크기가 크거나, 계산 시간이 제한된 상황에서 유용합니다.

 

2.간결함

그리디 알고리즘은 각 단계에서의 최적의 선택만을 고려하므로, 알고리즘의 설계와 구현이 비교적 간결합니다.

 

3.특정 문제에 대한 최적해

그리디 알고리즘은 특정 문제에 대해 최적의 해를 보장할 수 있습니다.

예를 들어, 거스름돈 문제, 최소 신장 트리 문제, 작업 스케줄링 문제 등에서 그리디 알고리즘은 최적의 해를 찾을 수 있습니다.
그러나 그리디 알고리즘을 적용하기 전에, 그리디 알고리즘을 사용해도 최적의 해를 찾을 수 있는 문제인지 판단해야 합니다. 그리디 알고리즘이 항상 최적의 해를 보장하지 않기 때문에, 문제의 특성과 그리디 알고리즘의 적용 가능성을 고려해야 합니다.

 

3번이 위에 말한 예시인 거스름돈 문제와 모순된다고 생각할 수 있습니다.

하지만 저는 사용한 모든 동전의 갯수가 최소가 되도록 원한다는 가정을 추가하였습니다.

일반적으로 나눌수 있는 거스름돈은 큰단위 부터 나눠주는 것을 의미하죠, 또 7같은 10단위에 벗어나는 동전을 사용한다고 가정하기도 하였습니다.

 

정리해보면 그리디 알고리즘은 항상 최적의 해를 보장하지 않는 이유는, 앞에서 말한 그리디 알고리즘의 논리 떄문입니다.

그리디 알고리즘은 각 단계에서 단지 "지역적으로" 최적의 선택을 한다는 데 있습니다. 이 "지역적으로 최적"이라는 개념이 그리디 알고리즘의 강점이자 약점입니다.