Greedy Algorithm (그리디 알고리즘)
그리디 알고리즘이란? 그리디 알고리즘은 눈앞의 이익만을 좇는 알고리즘이다. 그리디 알고리즘은 앞의 선택이 이후 선택에 영향을 주지 않는 문제에 잘 작동한다. 그리고 그리디 알고리즘은 글로벌 최적을 찾기 위해 각 단계에서 로컬 최적의 선택을 하는 알고리즘이다. 대부분의 경우 계산 속도가 빠르므로 매우 실용적이다. 배낭 문제 문제 현재 15kg를 담을 수 있는 배낭, A (12kg, 4달러), B (1kg, 2달러), C (4kg, 10달러), D (1kg, 1달러), E (2kg, 2달러)가 있다. 달러의 가치가 최대가 되도록 배낭에 넣을 짐을 골라보자. 풀이 단가가 가장 높은 짐부터 배낭에 담으면 된다. 동전 바꾸기 문제 문제 현재 알바생에게 10원, 50원, 100원이 존재한다. 160원을 동전의 개수..