[Python algo] 탐욕 알고리즘 | Greedy algorithm

 

안녕하세요

 

오늘은 탐욕 알고리즘이란 무엇인가 알아보고 , 이를 간단하게 구현해 보도록 하겠습니다.

 

### 탐욕 알고리즘(Greedy algorithm) ?

 

탐욕 알고리즘은 최적의 해를 구하는 방법입니다.

현재 상황에서 가장 좋다고 생각하는 것을 선택해 나가는 방식입니다.

또한, 이러한 선택 방법이 가장 좋을 것이라고 기대하고 사용하는 것입니다.

 

문제를 해결하는 과정에서 순간순간마다 최적의 결정하는 방식

 

하지만 항상 최적의 답을 구해주지는 않습니다.

 

예시로 다음 과정을 확인하시면 됩니다.

 

step 1 : 1에서 시작

step 2 : 7 / 9 선택       ->  탐욕 알고리즘 , 9 선택

step 3 : 11 / 15 선택  ->  탐욕 알고리즘 , 15 선택

 

1 + 9 + 15 = 25 

 

탐욕 알고리즘을 통해 25라는 값을 얻게 되었습니다.

 

하지만 실제로는 1 -> 7 -> 20 의 경우를 통해 28이라는 더 높은 수치를 얻을 수 있습니다.

 

이처럼 탐욕 알고리즘은 전역 최적화를 목적으로 하지만,

실제로는 국소 최적화 수치를 구하게 됩니다.

 

## Python 탐욕 알고리즘

 

탐욕 알고리즘에는 많은 예시가 있습니다.

그 중 거스름돈의 개수를 가장 적게 주는 방법을 찾아보도록 하겠습니다.

 

잔돈 리스트 = 1 , 50 , 100 , 500

금액 = 658

 

# 리스트 내림차순 정렬 

 

잔돈 리스트를 역순(내림차순)으로 정렬합니다.

나눈 몫을 동전의 개수로 나타내고

새로운 금액은 나눈 나머지가 됩니다.

 

pay=658
coin=[1,50,100,500]
coin=sorted(coin,reverse=True)
print(coin)

for i in coin:
    print('%s원 %s개'%(i,pay//i))
    pay=pay%i

 

 

# 각 최소 개수를 구하는 함수 활용

def min_count(pay,coin):
    res={}    
    for i in coin:
        res[i]=pay//i
    
    return res
    
pay=658
coin=[50,1,500,100]

min_count(658,coin)

 

정렬을 하지 않고 coin 전체를 함수에 인자로 넘깁니다.

각 coin의 원소 별 몫의 개수를 확인할 수 있습니다.

 

res 딕셔너리를 value값이 적은 순으로 정렬 , 첫 번째 Key와 value를 리턴합니다

def min_count(pay,coin):
    res={}    
    for i in coin:
        res[i]=pay//i
    res=sorted(res.items(),key=lambda x:x[1])
    return res[0]
    
pay=658
coin=[50,1,500,100]

min_count(658,coin)

 

위의 경우 문제가 있습니다.

 

value가 0인 경우에는 문제를 제대로 해결할 수 없습니다.

if문 하나를 추가해 완성할 수 있습니다.

 

pay=658
def min_count(pay,coin):
    # 거스름돈 단위, 개수를 담을 딕셔너리
    res={}
    # 거스름돈 단위별 개수를 구함
    for i in coin:
        if pay//i!=0: # 거스름돈 개수가 0개가 아니면 딕셔너리 추가
            res[i]=pay//i
    # 2번째 인자를 기준으로(value) 오름차순 정렬        
    res=sorted(res.items(),key=lambda x:x[1])
    return res[0] # 첫 번째 인자(value 가장 작은)return

while pay:
    min_count(pay,coin)
    a,b=min_count(pay,coin)
    print('%s원 %s개'%(a,b),end=' ')
    pay-=a*b

 

 

위 예시에서는 정렬로 간단하게 끝났지만

리스트의 인자간의 차이를 구한다거나, 계산이 필요한 경우에는

함수를 추가로 사용해서 구해야 할 수도 있습니다.

 

또, 추가적인 작업이 필요할 수 있으므로 하나의 알고리즘을 가장 간단한

한 가지 방법으로 구현하기 보다 조금 더 다양한 방법으로 해결해 보고자 했습니다.

 

읽어주셔서 감사합니다