数列，および，文字列である条件を満たすものの中で辞書順最小のものを求めよという問題によく使われる方法．
最初の $1$ 要素を，最も小さい要素と決めつけて，残りはうまく選ぶことで条件を満たすことができるかを調べる．
可能であれば，最初の $1$ 要素をそれに確定して，同じことを $2$ 番目の要素以降も繰り返していく．
不可能であれば，最初の $1$ 要素を，$2$ 番目に小さい要素と決めつけて，残りをうまく選ぶことで条件を満たすことができるかを調べる，と続けていく．
$2$ 分探索と似た考えだが，区切りを最初数要素を決めつけて，残りをうまく選べるかと調べることで，その調べるときに貪欲法が使えるようになることが多い．
Current time: 2024年04月23日19時31分19秒
Last modified: 2014年05月24日23時48分07秒 (by laycrs)
Tags: no_tags
トップページに戻る
Logged in as: unknown user (not login)