[알고리즘 스터디 with 케이시] 탐욕 알고리즘

• 자판기의 동전 반환 로직
• 마시멜로 실험에서 아이의 선택
  • 15분 기다리면 마시멜로 2개
  • 지금 먹으면 마시멜로 1개
  • 지금 먹는것이 확실하므로 지금 먹음

이런 알고리즘을 어떻게 구현할지가 그리디 가 나오게된 배경

정의

• 매 선택에서 지금 이 순간 가장 최적인 답을 선택하는 알고리즘

특징

• 보통 최적해를 구하는 알고리즘보다 빠른 경우가 많다.
• 크루스칼, 다익스트라 알고리즘 등에 사용된다.
• 직관적인 문제 풀이에 적합하다.
• 최적해를 보장하지 않는다.

예시1

• A 에서 출발
• 가중치가 B가 더 작으므로 B로 감
• A → F 의 총 가중치
  • 65 b route
  • 33 d route
• 하지만 그리디 알고리즘에 따르면 65를 선택함.
• 기계적으로 욕심을 구현했다는게 재밌음

예시2

• 상황
  • 자판기의 동전 반환 문제
    • 거스름돈은 번거롭기 때문에 최대한 큰 단위로 거슬러 주고 싶다.

• 방법
  • 큰 단위인 지폐, 동전 순으로 거스름돈을 만들면된다.
  • 가장 쉽고 직관적인 그리디 문제

출처

케이시 강의 자료