그리디 알고리즘
-
[Algorithm_Greedy]_1. 그리디(탐욕법)Algorithm 2021. 2. 20. 20:58
Greedy 그리디(탐욕법)알고리즘은 단순하지만 가장 강력한 문제 해결방법이다. 탐욕법이라고 하는 이유는 단순 무식하게 탐욕적으로 풀어서 그런것 같습니다 여기서 탐욕적이라는 말은 현재 상황에서 가장 좋은 것만 고르는 방법을 의미합니다. 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 보통 문제에서 /가장 큰 순서대로, 가장 작은 순서대로/ -> 정렬알고리즘과 결합하여 자주 출제됩니다. 대표적인 그리디알고리즘 문제는 거스름돈 문제입니다. 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한이 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 하는 동전의 최소 개수를 구하라 N은 10의 배수이다..