algo - Greedy

각 단계에서 최선의 선택을 하고자 하는 문제를 해결하는 것을 생각합니다. 이것이 탐욕(그리디) 알고리즘의 본질입니다. 사탕을 주면서 다음은 생각하지 않고, 각 단계에서 가능한 한 많은 사탕을 모으는 것과 같습니다. 눈앞에 있는 가장 큰 사탕을 잡기만 하면 됩니다. 즉, 각 단계에서 최선의 선택을 하면 결국 전체적으로는 최상의 솔루션에 도달할 수 있음을 의미합니다.

이는 문제에 대한 해결책이 더 작은 하위 문제에 대한 해결책이 포함되어 있음을 의미합니다. 예를 들어, 30센트의 잔돈을 만들어야 하는데, 20센트와 10센트 잔돈을 따로 만드는 방버을 알고 있는 경우 이를 결합하여 문제를 해결할 수 있습니다.

Sample Quiz

가장 적은 수의 동전으로 일정 금액을 벌고 싶다고 가정해 봅시다. 1센트, 5센트, 10센트, 25센트와 같이 서로 다른 가치의 동전이 있습니다.

• Denominations: [1, 5, 10, 25]

• Amount: 63

• 동전을 내림 차순으로 정렬합니다.

• 25센트 동전을 최대한 많이 사용한 다음 10센트 동전, 5센트 동전, 마지막으로 1센트 동전으로 이동합니다.

• 각 동전을 몇 개씩 사용했는지 기록합니다.

def solution(denomination: list[int], cent: int) -> int:
    sorted_denomination = sorted(denomination, reverse=True)
    remain = cent
    used_coin_count = 0
    for coin in sorted_denomination:
        if remain == 0:
            break
        quo, rem = divmod(remain, coin)
        remain = rem
        used_coin_count += quo

    if remain > 0:
        return -1

    return used_coin_count


solution([1, 5, 10, 25], 63) # 6
solution([2, 5, 10, 25], 63) # -1

최적의 값을 구해야 하는 상황에서 근시안적인 방법론으로 각 단계에서 최적이라 생각되는 것을 선택하여 나가는 방식으로 답을 도출하는 알고리즘입니다. 이 때, 항상 최적의 값을 보장하는 것이 아니라 최적의 값의 '근사한 값'을 목표로 합니다.

주로 문제를 분할 가능한 문제들로 분할한 뒤, 각 문제들에 대한 최적해를 구하여 이를 결합 후 전체 문제의 최적해를 구하는 경우에 사용됩니다.

💡 근시안적 방법론이란?

• 단기적인 목표를 중심으로 한 전략적인 접근 방법을 의미합니다. 이 방법론은 주로 현재의 문제를 해결하는 데 초점을 맞추며, 장기적인 전망보다는 단기적인 성과를 중요시합니다.

💡 근사 알고리즘(Approximation Algorithm) 이란?

• 최적의 해를 구할 수 없는 문제에서 근사한 해를 구하는 알고리즘을 의미합니다. 근사 알고리즘은 항상 최적해를 보장하지는 않지만, 많은 경우에는 최적해에 근접한 값을 구할 수 있습니다

💡 문제를 풀 때 두 가지 조건이 성립해야 그리디 알고리즘을 적용할 수 있습니다.

• 탐욕 선택 속성(Greedy Choice Property) 이란?

  • 각 단계에서 ‘최선의 선택’을 했을 때 전체 문제에 대한 최적해를 구할 수 있는 경우를 말합니다. 즉, 각 단계에서 가장 이상적인 선택을 하는 것이 전체적으로 최적의 결과를 가져온다는 것입니다.

• 최적 부분 구조(Optimal Substructure)

  • 전체 문제의 최적해가 ‘부분 문제의 최적해로 구성’될 수 있는 경우를 말합니다. 즉, 전체 문제를 작은 부분 문제로 나누어 각각의 부분 문제에서 최적의 해를 구한 후 이를 조합하여 전체 문제의 최적해를 구하는 것을 의미합니다.

그리디 알고리즘의 단계는 매 단계마다 최적이라고 생각되는 선택을 하면서 최종적으로 전체적으로 최적인 해답을 찾아내는 과정을 의미합니다.