목록Knapsack (1)

데이터 분석 기술 블로그

완전검색 그리디 - 탐욕 알고리즘

1. 문제 제시 : 거스름돈 줄이기손님이 지불한 금액에서 물건값을 제한 차액(거스름돈)을 지불하는 문제를 생각해 봅시다."어떻게 하면 손님에게 거스름돈으로 주는 지폐와 동전의 개수를 최소한으로 줄일 수 있을까요?"2. 탐욕(Greedy) 알고리즘탐욕 알고리즘은 최적해를 구하는 데 사용되는 근시안적인 방법일반적으로, 머릿속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy 접근이 됩니다.여러 경우 중 하나를 선택할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달합니다.각 선택 시점에서 이루어지는 결정은 지역적으로 최적이지만, 그 선택들을 계속 수집하여 최종적인 해달을 만들었다고 해서, 그것이 최적이라는 보장은 없습니다.일단, 한 번 선택된 것은 번복하지..
알고리즘 2024. 6. 22. 09:00
이전 Prev 1 Next 다음