プログラミング ゲーム制作に勤しんでいる友達の姿を見て、大規模システムのクラス設計について調べていました。ここでは、リンクの整理にとどめます。 1年前にはGoFのデザインパターンを実践・勉強していました。当時アーキテクチャパターンについても調べ…

迷路を解くといえば、幅優先探索。現在メモ化部分までしか完成していません。あとは辿るだけ。 bfsの練習

Quick Sort quick sortは、最悪計算量がO(N2)と知られていますが、乱択アルゴリズムにすることで計算量の期待値がO(N*lgN)になります。 乱択クイックソートの実装は、私がネットで見たものだけで、二つの方法がありました。 枢軸（ピボット）をランダムに選…

sort 昔あったアルゴリズム熱が再燃して、いろいろなアルゴリズムを調査しています。アルゴリズムといえば基本はソートです。今回はマージソートを実装してみました。マージソートはオンラインアルゴリズムとしても有名*1らしいのですが、今回はオフラインで…

与えられたリストの順序をバラバラにしたいときは、Knuth Shuffleが便利です。 ここでは、アルゴリズム理解のために、プログラムを書きました。 実際に使う場合には、C++であれば、STLにrandom_shuffle関数が用意されているのでそちらを使ったほうがいいでし…