マイナー、好きなアルゴリズム

Question

みなさんの好きなアルゴリズム、マイナーなアルゴリズムを教えてください

Answer 1

だいぶ昔の質問に、こんなものが眠っていたんですね。
今だったら意見交換に投稿されて盛り上がっていそうな質問です。

好きなアルゴリズム

二分探索です。

とても初歩的なアルゴリズムですが、実生活の中でも偶に使ったりと、わりかし汎用性があるアルゴリズムなので、私は好きです。

例を挙げると、初代ロックマンエグゼでもこのアルゴリズムを使わないと厳しいクイズ（🎲ナンバーマン戦の道中）が登場したんですよ。
小学生にとってはシビアだったんじゃないでしょうか。

マイナー(?)なアルゴリズム

Gale-Shapelayアルゴリズムです。

大学の数学の授業で出てきたのですが、競技プログラミングで出てくるタイプのアルゴリズムしか触っていなかった自分は、当時これがマイナーだと思っていました。

しかし最近YouTubeで有名な早水桃子准教授の動画にも登場したりと、割と有名なアルゴリズムなのかもしれません。

Comments

[fana]

> 今だったら意見交換に投稿されて盛り上がっていそうな質問です

そういう場合，新規に意見交換として立ててしまっても良かったかもですね．

Answer 2

●好きなアルゴリズム

動的計画法による編集距離の算出
文字列同士がどの程度類似しているかを「何回の編集操作で一致させられるか」という数字で出します。
えらい時間のかかりそうな計算と思いきや、動的計画法という工夫により、文字列長の積に比例した時間で算出可能です（計算時間がO(mn)であると表現します）。
http://karel.tsuda.ac.jp/class/algoB/c13.html
このアルゴリズムの恩恵を最も受けているのは生物学者・医学者です。DNA同士の類似度、どのくらい変化したか、種が枝分かれしてから何万年ほど経ったかを見積もるのに使えるので。

●マイナーなアルゴリズム

Sunday法
テキスト中から文字列を見つけるアルゴリズム。一般的な情報カリキュラムではKMP法、BM法というのを習うだけでこのSunday法は習わないのですが、なかなか難解なKMP法・BM法にくらべて理解しやすいのに大抵処理も速いという「みんなもっとこれ知ってれば良いのに」的なアルゴリズムです。
http://fussy.web.fc2.com/algo/search4_bm.htm