그리디 알고리즘이란 무엇인가?

그리디 알고리즘은 단순하지만 강력한 문제해결 방법이다.

탐욕법이라고도 하며, 어떠한 문제가 있을때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다.

 

굳이 "탐욕적"이라는 표현을 쓰는 이유는 현재상황에서 지금 당장 좋은 것만 고르기 때문이다.

 

정렬, 최단경로 등도 그리디 알고리즘이 포함되는 경우가 많으며 사용방법을 정확히 알고 있어야 한다.

(플로이드 워셜, 다익스트라, 정렬 등)

 

그리디 알고리즘은 모든 문제에 적용할 수 있는 것이 아니다.

대부분의 문제에서는 그리디를 썼을때 최적의 해를 찾을 수 없을 가능성이 높다.

 

즉, 그리디를 사용했을 때에는 그 결과가 정당한지 검토해야 한다.

거스름돈 문제를 그리디로 풀 수 있는 이유는, 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로,

작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.