[Python] 그리디 알고리즘 파이썬, 복학생도 쉽게 이해하는 글 !

그리디 알고리즘(탐욕 알고리즘) 파이썬 초보자 가이드

오늘은 알고리즘 중에서도 그리디 알고리즘(Greedy Algorithm, 탐욕 알고리즘)에 대해 알아볼게요 !

 

 

그리디 알고리즘이란?

그리디 알고리즘은 한 단계 한 단계 최적의 선택을 해 나가면서 문제를 해결하는 방법이에요. '탐욕적'이라는 말대로 그 순간에는 가장 좋아 보이는 선택을 하죠. 이렇게 선택을 계속 이어 나가면서 전체 문제의 해답에 도달하는 데 목적이 있어요.

예를 들어, 마트에 주어진 돈을 최대한 효율적으로 사용하여 물건을 사야 할 때, 매 순간 저렴한 물건을 먼저 담는 방식을 떠올릴 수 있습니다.

그리디 알고리즘의 특징

1. 지역 최적해 선택: 매 단계에서 현재 상태에서 가장 최선의 선택을 합니다.
2. 전역 최적해 지향: 마지막 도착 지점에서는 전체 문제의 최적해에 도달하도록 설계됩니다.
3. 단순성: 구현이 상대적으로 쉽고, 빠르게 해결할 수 있어요.
4. 특정 문제에 효과적: 그러나 모든 문제에 최적의 솔루션을 보장하진 않아요. 그리디 알고리즘이 문제에 잘 맞아 떨어지는 경우가 따로 있답니다.

 

[Python] 그리디 알고리즘 파이썬, 복학생도 쉽게 이해하는 글 !

 

그리디 알고리즘의 예제: 최소 동전 거스름돈

이제 간단한 그리디 알고리즘의 예를 들어볼게요. 여러분이 주변 편의점에서 물건을 사고, 잔돈을 받을 때를 상상해 봅시다. 목표는 거스름돈을 가장 적은 수의 동전으로 주는 것입니다.

문제 상황

거스름돈으로 620원을 주어야 하고, 사용할 수 있는 동전은 500원, 100원, 50원, 10원짜리입니다. 이때 우리가 해야 할 일은 최대한 적은 수의 동전으로 620원을 만드는 것이죠.

해결 과정

1. 가장 큰 단위부터 사용:
   • 먼저, 500원짜리 동전을 사용할 수 있으면 사용합니다.
   • 다음으로는 100원짜리를 고려하고, 그다음 50원짜리, 마지막으로 10원짜리를 선택합니다.
2. 파이썬 코드로 구현하기: 
   이렇게 하면 500원짜리 1개, 100원짜리 1개, 10원짜리 2개를 사용하여 총 4개의 동전으로 620원을 거슬러 줄 수 있어요.

def min_coins(change):
       coin_types = [500, 100, 50, 10]
       count = 0
       for coin in coin_types:
           count += change // coin  # 해당 동전으로 거슬러 줄 수 있는 최대 개수
           change %= coin  # 그 이후 남은 금액
       return count

print(min_coins(620))  # Output은 4입니다.

 

그리디 알고리즘의 한계

방금 봤던 예제는 그리디 알고리즘이 잘 적용되어 성공적인 결과를 가져온 케이스입니다. 하지만 그리디 알고리즘이 항상 최적의 해답을 제공하지는 않아요. 예를 들어, 만약 동전 세트가 1원, 3원, 4원이었다고 가정해 볼까요? 6원을 거스르기 위해서는 3원짜리 2개를 사용하는 것이 최선이지만, 그리디 알고리즘은 4원짜리 하나와 1원짜리 두 개를 선택하게 됩니다.

그리디 알고리즘 사용 시 유의점

• 문제에 따라 다르게 접근: 반드시 그리디 알고리즘이 문제의 최적 솔루션을 보장하는지 확인해야 합니다. 기본적으로, 그리디 알고리즘은 최적 부분 구조라는 성질이 있을 때, 즉 각 단계의 선택이 이후 선택에 독립적일 때 가장 효과적이에요.
• 다양한 알고리즘 검토: 때로는 동적 계획법(DP)나 다른 방법이 보다 나은 해결책을 제공할 수 있습니다.

마무리

그리디 알고리즘은 프로그래밍 문제를 해결하는 여러 가지 기술 중 하나입니다. 가끔은 효율적인 해결책을 줄 수 있지만, 모든 문제에서 항상 최적의 선택은 아닐 수 있으니 주의가 필요합니다. 이렇게 차근차근 다양한 알고리즘을 배워가면서 문제 해결에 대한 감을 얻어보세요!

궁금한 것이 있거나 도움이 필요하다면 언제든지 댓글이나 메일로 문의해주세요. 화이팅! 🙌

---

이 글이 조금이나마 여러분이 그리디 알고리즘을 이해하는 데 도움이 되었기를 바랍니다. 감사합니다!