Greedy Algorithm

매 순간 최적인 경우를 찾아가면서 최적의 답을 찾아 내는 알고리즘

• 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법이다
• 탐욕 알고리즘은 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택한다.
• 순간마다 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다.
• 탐욕 알고리즘을 적용할 수 있는 문제들을 지역적으로 최적이면서 전역적으로 최적인 문제들이다.

탐욕 알고리즘의 조건

탐욕 알고리즘은 DFS/BFS, DP들 보다 빠른 속도때문에 적용할 수 있다면 가장 빠르게 결과를 얻을 수 있다.

그러면 빠르게 탐욕 알고리즘이 적용 가능한지 파악하는 것이 중요할텐데, 탐욕 알고리즘을 적용하려면
탐욕스런 선택 (Greedy Choice Property) 와 최적 부분 구조 조건(Optimal Substructure) 이라는 두 조건을 만족 시켜야한다.

최적 부분 구조 조건(Optimal Substructure)

최적 부분 구조 조건(Optimal Substructure)은 동적 계획법(Dynamic Programming) 에서 작은 부분 문제에서 구한 최적의 답으로 합쳐진 큰 문제의 최적의 답을 구할 수 있어야 한다는 것

거스름돈 문제
동전은 10원,50원,100원,500원

물건 가격은 4,270원

손님이 5,000원을 냈을때
가장 적은 개수의 동전을 거슬러 줘야할때를 가정
최소 동전 개수를 구해라

• 500원 : 1개

• 100원 : 2개

• 50원 : 0개

• 10원 : 3개

• 최소 동전 6개

탐욕스런 선택 조건 (Greedy Choice Property)

앞의 선택이 이후의 선택에 영향을 주지 않는다는 것이다

• 730원

  • 최적의 선택 500원 * 1개 차감

• 230원

  • 최적의 선택 100원 * 2개 차감

• 30원

  • 최적의 선택 10원 * 3개 차감

  최소 동전은 6개

  위 과정에서 동전을 고르는 행위는 현재 남은 금액에 따라 선택을 하기 때문에,
  내가 500원을 선택한 앞의 행위는 다음 선택에서 100원을 선택하는 것에 영향을 주지 않는다.