그리디(Greedy)

그리디는 매 선택에서 현재 상황에서 가장 최적인 선택지를 선택하는 알고리즘으로
최적해를 보장해주지 않습니다.

다음과 같은 상황에서 A에서 F로 가는 경우의수는
A - B - C - F
A - D - E - F
2가지가 있습니다.

그리디 알고리즘을 사용하면 시작지점 A에서 가장 작은 값을 고르기때문에
A - B를 선택합니다.

하지만 A - B - C - F은 총 115의 코스트를 소비하고
A - D - E - F은 총 31의 코스트밖에 소비하지 않습니다.
이처럼 그리디는 최적해를 보장하지 않습니다.

특징

• 보통 최적해를 구하는 알고리즘보다 빠른 경우가 많다.
• 크루스칼, 다익스트라 알고리즘 등에 사용된다.
• 직관적인 문제 풀이에 적합하다.
• 보통 시간복잡도 O(n)

예시

소비자에게 가장 적은 숫자의 화페를 이용해 거슬러 주는 방법은 무엇일까요?
거스름돈: 2760원