티스토리 뷰

반응형



반드시 알아야 하는 알고리즘 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씩 증가시키는 기능을 수행합니다.








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

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

댓글로 말씀해주세요.


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


좋은 하루 되세요. ^^


반응형
댓글
반응형
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함