그리디(Greedy) 알고리즘 예시와 문제

🤔 그리디 알고리즘이란?

그리디 알고리즘(Greedy Algorithm)은 최적해를 구하는 데 사용되는 알고리즘 중 하나입니다.

최적해란? 주어진 문제에서 가장 최소 또는 최대 값을 구하는 것

 

그리디(greedy) 알고리즘은 말그대로 탐욕스럽게 미래를 생각하지 않고

현재에서 매 순간 최선의 선택을 하면서 답을 구하는 알고리즘입니다.

 

 

 

 

 

 

 

💡 그리디 알고리즘의 예시

거스름돈 문제

 

예를 들어, 1원, 5원, 10원, 50원, 100원의 종류의 동전이 있다고 가정해보겠습니다. 거슬러줘야 할 금액이 230이라면, 그리디 알고리즘을 사용하여 동전의 개수의 총합을 적게 줄 수 있다.

 

가장 큰 동전부터 거슬러주면 된다.

• 100원짜리 동전 2개 거슬러 주기
• 10원짜리 동전 3개 거슬러 주기

총 5개의 동전을 사용하여 거슬러 줄 수 있습니다.

def coin_change(coins, amount):
    # 동전의 종류를 오름차순으로 정렬합니다.
    coins.sort()

    # 필요한 동전의 개수를 저장할 변수를 초기화합니다.
    count = 0

    # 동전의 종류를 역순으로 반복하면서 필요한 동전의 개수를 구합니다.
    for coin in reversed(coins):
        # 현재 동전을 사용할 수 있는 만큼 사용합니다.
        while amount >= coin:
            amount -= coin
            count += 1

    # 필요한 동전의 개수를 반환합니다.
    return count

coins = [1, 5, 10, 50, 100]
amount = 230
print(coin_change(coins, amount))  # 출력값: 5

 

 

 

🎯 그리디 알고리즘의 적용

• 최적 부분 구조(optimal substructure)
  큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제가 큰 문제의 영향을 주지 않아야한다.

 

• 탐욕적 선택 속성(greedy choice property)
  매 순간마다 최선의 선택을 하면서 답을 구할 수 있습니다.

 

• 탐욕적 - > 최적해
  탐욕적 선택이 항상 최적해를 보장해야한다.

 

 

 

 

 

💪 그리디 알고리즘 참고할만한 자료

 

문제 - 1 페이지