Greedy Algorithm
닉값 그대로 탐욕적인 선택을 하는 방법이다.
탐욕적 기법 문제는 한번의 선택을 한 이후에도 문제와 동일한 성질들이 성립하고 있다. 즉, 성질이 동일하기 때문에 탐욕적인 선택을 계속해도 정답을 얻을 수 있는 것이다.
같은 전략을 반복적으로 취할 수 있고, 그것이 정답이 되는 것이다.
그리디 풀이는 시간복잡도도 작은 편인데, 오히려 그리디 문제인데도 문제의 크기가 크지 않은 편인 문제들도 많다고 한다.
500원 100원 50원 10원짜리 동전이 있고 어떤 금액을 표현하려 할때, 동전 개수를 최소로 사용하는 경우를 구해라 라고 하면, 무조건 금액이 큰 동전을 많이 사용하는 경우가 최소가 된다.
그런데 이것이 왜 성립하는가에 의문을 가져야 한다. 이는 사용할 수 있는 동전을 보면 알 수 있다.
10 50 100 500 > 이것들은 모두 큰것이 작은것의 배수이다. 이 특징 때문에 작은 것이 많을 경우 큰것으로 바꿔야 개수가 줄어든다.
만약 10 50 60 이라면 그리디 기법으로 문제를 푸는것이 어려울 것이다. 예를들어 220원을 표현할 때, 그리디 기법으로 접근한다면 60원을 3개 쓰고 나머지 40원을 10원짜리로 채워 7개를 사용한다는 답이 나온다. 하지만 50원짜리 4개와 10원짜리 2개인 6개가 정답이다.
그리디 기법은 같은 전략을 반복적으로 취할 수 있고 그것이 정답이 된다고 했는데, 동전 문제도 그러하다.
가장큰 동전을 한번 사용하면 남은 금액을 다시 최소 개수의 동전을 사용하여 나타내는 문제가 되기 때문이다.
그리디 기법은 풀이가 대부분 "가장 큰", "가장 긴", "가장 빠른" 등 부터 뭔가 해나가라는 것이 많다.
