반드시 알아야하는 알고리즘 top 8 - 6. 탐욕 알고리즘, 그리디 알고리즘

반드시 알아야 하는 알고리즘 top 8

• 재귀 알고리즘 

• 이진 탐색 

• 순차 탐색

• 버블 정렬

• 삽입 정렬

• 탐욕 알고리즘

• 최단거리 알고리즘

• 몬테 카를로 알고리즘

탐욕 알고리즘 

• 탐욕 알고리즘은 최적해를 구하는 상황에서 사용하는 방법입니다. 여러 경우 중 하나를 선택할 때 그것이 그 상황에서 가장 좋다고 생각하는 것을 선택해 나가는 방식으로 진행하여 답을 구합니다. 

• 그 상황에서 가장 좋다고 생각하는 것을 선택해 나가는 방식이기 때문에 가장 좋은 결과를 얻는 것이 보장되는 것은 아닙니다. 다음과 같은 예를 살펴 보겠습니다.

• 가장 최적의 해는 초록색 라인을 따라가서 얻는 107 이지만 그리디 알고리즘을 통해서 구한 값은 7과 13 중에 큰 값인 13을 5와 11 중에 큰 값인 11을 선택하여 24입니다. 다시 말해 그리디 알고리즘이 최적해를 보장해 주진 않는 다는 것을 명심해야합니다.

그리디 알고리즘 예제 - 동전 지불 

• 문제 : 지불해야 하는 값이 362원 일 때 1원 50원 100원 짜리 동전으로 동전의 수가 가장 적게 지불하시오. 

• 동전 지불 문제는 그리디 알고리즘을 사용해서 풀 수 있는 아주 간단하고 직관적인 예제 중 하나 입니다. 동전이라는 특성상 큰 단위의 동전부터 지불하면 해결 되긴 하지만 그리디 알고리즘을 통해서 구현해보면 다음과 같습니다.

def min_calc(value, coin):

    a=[]

    for i in coin:

        a.append([value-i, i])

    res = a[0]

    for i in a:

        if res[0] > i[0] and i[0] > 0:

            res = i

    return res

    

coin = [1,50,100]

value = [362, 0]

dic = {}

for i in coin:

    dic[i] = 0

    

while True:

    value = min_calc(value[0],coin)

    if value[0] < 0:

        break

    else:

        dic[value[1]] += 1

print(dic)

• min_calc 라는 함수는 현재 금액에서 각각의 동전을 뺐을 때 가장 적은 금액이 남는 경우를 반환하는 함수 입니다.

• 사용되는 변수는 coin ( 동전의 종류 ) 와 value ( 지불해야 하는 금액 ), dic ( 동전의 종류별로 얼마나 사용되는지 ) 로 총 3가지 변수를 사용합니다.

• while loop 문은 min_calc 를 실행 한 뒤 남은 금액들 모두가 0보다 작아지기 전까지 실행하는 함수 입니다. 실행되는 동안에는 뺀 동전에 대한 value 값을 1씩 증가시키는 기능을 수행합니다.

---

부족한 블로그에 방문해 주셔서 감사합니다.

잘못된 부분이나 질문이 있으시면 

댓글로 말씀해주세요.

금방 확인하고 피드백 드리겠습니다.

좋은 하루 되세요. ^^