그리디 알고리즘이란?
그리디 알고리즘은 눈앞의 이익만을 좇는 알고리즘이다.
그리디 알고리즘은 앞의 선택이 이후 선택에 영향을 주지 않는 문제에 잘 작동한다.
그리고 그리디 알고리즘은 글로벌 최적을 찾기 위해 각 단계에서 로컬 최적의 선택을 하는 알고리즘이다.
대부분의 경우 계산 속도가 빠르므로 매우 실용적이다.
배낭 문제
문제
현재 15kg를 담을 수 있는 배낭, A (12kg, 4달러), B (1kg, 2달러), C (4kg, 10달러), D (1kg, 1달러), E (2kg, 2달러)가 있다.
달러의 가치가 최대가 되도록 배낭에 넣을 짐을 골라보자.
풀이
단가가 가장 높은 짐부터 배낭에 담으면 된다.
동전 바꾸기 문제
문제
현재 알바생에게 10원, 50원, 100원이 존재한다. 160원을 동전의 개수를 최소로 하여 거슬러주자.
풀이
동전의 액면이 10원, 50원, 100원처럼 증가하면서 이전 액면의 배수 이상이 되면 그리디 알고리즘으로 풀 수 있다. 숫자가 큰 동전부터 선택하면 된다. -> 100원짜리 1개, 50원짜리 1개, 10원짜리 1개
총 3개의 동전으로 160원을 거슬러 줄 수 있다.
그런데 만약 다른 나라에 갔더니 80원짜리 동전이 더 있었다고 치자. 이 경우 더 이상 그리디 하게 풀 수 없다.
160원을 거슬러줘야 한다면 80원짜리 동전 2개가 정답인데 그리디 알고리즘으로는 100원부터 선택하게 될 것이고 80원 2개로 풀이할 수 없기 때문이다. 이 경우 다이나믹 프로그래밍으로 풀어야 한다.
참고
파이썬 알고리즘 인터뷰