Greedy 알고리즘

당장 좋은 것만 선택하는 그리디

그리디 알고리즘은 단순하지만 강력한 문제 해결 방법이다. 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다. 여기서 탐욕적이라는 말은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미
그리디 알고리즘을 이용하면 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

예제 1) 거스름돈

코드를 보면 화폐의 종류만큼 반복을 수행해야 한다. 따라서 화폐의 종류가 K개라고 할 때 위 소스코드의 시간 복잡도는 O(K)이다. 참고로 시간 복잡도에서 거슬러 주어야 할 돈 N은 찾아볼 수 없는 것을 알 수 있다. 즉, 이 알고리즘의 시간 복잡도는 동전 총 종류에만 영향을 받고, 거슬러 줘야 하는 금액의 크기와는 무관하다는 것을 알 수 있다.

그리디 알고리즘의 정당성

그리디 알고리즘을 모든 알고리즘 문제에 적용할 수 있는 것은 아니다. 대부분의 문제는 그리디 알고리즘을 이용했을 때 최적의 해를 찾을 수 없는 가능성이 다분하다. 하지만 거스름돈 문제에서 가장 큰 화폐 단위부터돈을 거슬러 주는 것과 같이, 탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 때는 매우 효과적이고 직관적이다.