[C++ / Algorithm] 그리디 알고리즘이란? #16

1. 그리디 알고리즘이란?

그리디 알고리즘은 최적의 해를 얻기 위해서,
발생하는 각각의 선택지 중, 그 순간에 최적이라고 생각하는 선택지를 선택하는 알고리즘입니다.

2. 그리디 알고리즘의 특징

그리디 알고리즘은 각각의 선택지에서 최적이라고 생각하는 것을 고르지만,
항상 결과가 최적이라고 장담할 수는 없다는 특징이 있습니다.

위 그림을 보면 시작 지점에서 2개의 선택지가 생깁니다.
비용 2를 지불하고 A로 가는 선택지 와 비용 5를 지불하고 B로 가는 선택지가 있습니다.

이 문제에서 그리디 알고리즘을 적용한다면 Start -> A -> C -> End의 순서로 이동해 총 52의 비용이 필요하게 됩니다.
하지만 위 문제에서 최적의 해는 Start -> B -> D -> End 로 그리디 알고리즘이 항상 최적의 해를 보장하지 않는다는 점을 확인할 수 있습니다.