[アルゴリズム]
貪欲法
このアルゴリズムは問題の要素を複数の部分問題に分割し、それぞれを独立に評価を行い、評価値の高い順に取り込んでいくことで解を得るという方法である。 動的計画法と異なり保持する状態は常に一つであり、一度選択した要素を再考する事は無い。 このため得られる解は最適解であるという保証は無いが部分問題の解法と単純なソートのみでプログラムを実装することが可能であり、 多くの問題に対して多項式時間での近似アルゴリズムとなる。
具体例
三井住友信託銀行プログラミングコンテスト2019 - D
- ある数列, 例:{1,2,3,9}から3桁の文字列XXX（000~999まである）が作成できるか？ の判定が貪欲法
疑似コード