탐욕 알고리즘
탐욕 (Greedy) 알고리즘은 현재 상황에서 최적이라고 생각되는 것을 선택해 나가며
최종적인 해답에 도달하는 알고리즘이다.
알고리즘
탐욕 알고리즘에는 딱히 정해진 규칙이 있는 것은 아니다.
현재 상황에서 최적이라고 생각되는 것 (보통최대나 최소값)을 선택해 나가며 해답에 도달한다.- 일반적으로
머리 속에 떠오르는 생각을 구현하는 경우가 많다. - 가장 중요한 것은 그것이
최적이라는 보장이 있어야 한다.
거스름돈 문제
가장 대표적인 탐욕 알고리즘 문제이다.
거스름돈으로 사용할 동전이 500원, 100원, 50원, 10원 동전이 무한히 존재한다.
손님에게 거슬러 줘야할 돈이 N원일 때 거슬러주어야 할 동전의 최소 개수를 구하라.
단 N은 항상 10의 배수이다.
이 문제를 보고 가장 먼저 든 생각이 무엇일까?
아마도 가장 큰 단위의 돈부터 거슬러주자일 것이다.
여기서는 어떻게 최적이라는 보장이 되어있는걸까?
숨어있는 내용은 큰 동전은 항상 작은 단위 동전의 배수로 이루어져 있다는 사실이다.
만약 800원을 거슬러줘야할 때,
동전의 단위가 500원, 400원, 100원, 50원, 10원 이라면 어떨까?
정답은 400원 2개로 그리디로 접근할 수 없다.
배낭 짐싸기 문제
배낭에 담을 수 있는 무게의 최대값이 정해져 있다.
일정 가치와 무게가 정해진 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되는 방법은?
이 문제는 물건을 쪼개지 못하는 경우 (0-1 Knapsack)와
물건을 쪼갤 수 있는 경우 (Fractional Knapsack)으로 나누어진다.
이 중 물건을 쪼갤 수 있는 Fractional knapsack의 경우 탐욕 알고리즘으로 풀 수 있는데,
무게당 가치 (value/weight)가 가장 높은 물건부터 우선적으로 담으면 된다.
