Greedy(욕심쟁이)

흔히 풀 수 있고, 어려운 것은 어려운 그리디에 대해 말해보겠다.  

그리디는 단편적인 큰 코스트를 취하는 방법이다.

1.그리디의 예시

빠르게 본론으로 넘어가겠다. 백문이 불아일견이라 했다.

우리가 1원 5원 10원의 동전들이 무수히 많다고 하자.

자연수인 N이 주어질때 동전들의 합으로 N을 만들어야하는 

상황에 사용되는 동전들의 개수를 최소화 시킬려면

어떻게 해야할까?

 

2.해답

어짜피 1원 5개를 쓰일 상황에선 5원을 하나 쓰는게 이득이고

5원 2개 쓰일빠엔 10원 하나를 쓰는게 이득이다.

고로 10원을 N에서 계속 빼다가 5원을 빼고 1원을 빼는 것.

가장 큰 액수부터 빼는게 이 문제의 답이다.

 

이러한 것 처럼 그리디는 단순히 그 순간만을 위한

최선의 선택을 하는 알고리즘이다.

정당성에 관한 부분은 그 문제를 생각했을때

단순히 그 단편적인 최고의 이득이 요구하는 정답으로

귀결되는가?와 연결된거같다.