그리디 알고리즘

그리디 알고리즘, 또는 탐욕 알고리즘은
현재의 최선의 선택을 통해 문제를 해결하는 접근 방식

핵심은 미래의 선택을 고려하지 않고,
지금 당장 가장 좋은 선택을 하는 것

예를 들어, 동전 문제에서는
주어진 동전들 중 가장 큰 단위의 동전을 최대한 많이 사용하여
주어진 금액을 만드는 방식으로 최소 동전 개수를 구함

하지만 그리디 알고리즘은 항상 최적의 해를 보장하지는 않음
예를 들어, 마시멜로 실험에서 당장 하나를 먹는 것이 최선일 수 있지만,
이는 장기적으로 더 큰 보상을 놓치는 결과를 초래할 수 있음

따라서 이 알고리즘을 적용하기 위해서는 두 가지 조건이 필요
첫째, 현재의 선택이 미래에 영향을 미치지 않아야 하며,
둘째, 작은 문제의 최적 해가 전체 문제의 최적 해를 보장해야 함

그리디 알고리즘은
회의실 배정 문제와 같은
다양한 문제에 효과적으로 적용될 수 있으며,
정렬을 통해 최적의 선택을 찾는 것이 중요

다이나믹 프로그래밍보다 빠른 성능을 제공하므로,
최적화가 보장되는 경우에 유용