탐욕법
탐욕법 (Greedy Alogrithm)
매 순간마다 최선의 경우만 고르는 알고리즘
완전 탐색은 모든 경우를 살펴보지만, 탐욕법은 현재 가장 최선의 경우만 고른다.
모든 경우를 다 살펴보지 않기 때문에 완전탐색보다 빠른 알고리즘이다. 어떤 것이 최선인지 알기 위해서 규칙성을 찾아야 하기도 한다.
그러나 그리디 문제(탐욕법을 그리디라 부르기도 함)는 이 문제가 그리디로 풀 수 있는지 아닌지 판별하는 것 부터가 어렵다. 왜냐 반례가 있을 수 있기 때문이다. 그런데 그 반례를 찾기가 어렵기 때문에 문제를 판별하는데 있어서 생각을 할 수 밖에 없다.
동전 문제일 경우 동전의 가치가 A_i가 A_i-1의 배수일 때 그리디로 문제를 풀 수 있게 된다.
ex) 1 5 10 50 100 ...
이렇게 동전의 가치가 배수가 될 경우 그리디로 문제를 풀 수 있다.
