[アルゴリズム]階調アルゴリズム

Gredyアルゴリズムとは?
欲張りアルゴリズムは答えを選択し、予め設定された基準に基づいて、毎回「一番よく見える」答えを選択します.貪欲なアルゴリズムは動的計画と同様に,主に最適化問題を解くために用いられる.相対的に、貪欲なアルゴリズムは設計がずっと簡単です.ダイナミックプランニングは、再帰関係を確立することによって、入力ケースをより小さな入力ケースに分割します.逆に,貪欲アルゴリズムは入力事例を分割しない.貪欲なアルゴリズムは順番に答えを一つ一つ集め、最終的な答えを構築し、最もよく見える答えを選ぶことで収集する.つまり、どんな答えを選ぶにしても、選ぶとき(ローカル)がベストです.
したがって,常に最適解を求めたいが,常に最適解が得られるとは保証できない.
全部で3段階に分かれている

選択コース

コンプライアンスチェック

解答検査

小銭を探して例を挙げる.グリディアルゴリズムの最適解はコイン個数の最小集合である.最初は手ぶらで始まり、一番額面の高いコインから始まります.つまり、どのコインが一番(地域で一番)良いかを決める基準はコインの額面です.これはグリディアルゴリズムでは選択過程と呼ばれている.手元のおつりの総数が売掛金と等しいかどうかを確認します.これは貪欲アルゴリズムでは「適正性検査」と呼ばれている.
探したお金の総額が探している金額を超えなければ、置いたばかりのコインは探しているお金に含まれます.おつりの総額がおつりの金額と等しいかどうかを確認します.貪欲なアルゴリズムを「答えをチェックする」と呼ぶ.

while(동전이 남아있고 문제 미해결){
	가장 가치가 높은 동전을 잡는다;
    if(동전을 더하여 거스름돈의 총액이 거슬러주어야 할 액수를 초과)
    	동전을 도로 집어 넣는다.;
    else
    	거스름돈에 동전을 포함시킨다.;
    if(거스름돈의 총액이 거슬러 주어야 할 액수가 같다.)
    	문제해결;
}