アルゴリズムプログラミング体操

先週から始めている、アルゴリズムプログラミングもくもく会。
先週はCodeIQの問題を解こうとチャレンジしました。
なので問題は公開するわけにはいかないのですが、前回はリファレンスコードを作るところまでで時間がきてしまいました。

リファレンスコードとは、誰でも理解できるような非常にシンプルなアルゴリズムで組まれたコードで、潜在的なロジックバグが出にくいのが特徴です。
デメリットとしては、大抵の場合、結果が出るまでに時間がかかります。
シンプルなアルゴリズムなゆえ、無駄が多い場合があります。
ここから高速化を行うために最適化を行っていきます。

例えば1から100まで足したらいくつになるか?
といった問題の場合、リファレンスコードでは、1から100までを順番に足していく方法になります。
100回ループすることになります。
少し考え方を最適化します。
1+99=100になります。
2+98=100になります。

49+51=100になります。
そう考えると、1~49までは対になる数字と合わせて100にします。
残りの50と100を足すと、49 * 100 + 50 + 100 = 5050 となりますね。
ループが半分になり、処理時間が半分になります。
そしてこの最適化の結果を検証するために、リファレンスコードが必要になります。

さて前回の問題で、時間がなくて最適化できなかったところ。
あるマス目が黒マスで分断されているかどうかを調べるにはどうしたらいいか?

これを高速で調べるにはどうしたら良いか?
ということで、「どこか白マスを決めてそこから上下左右行ける白マスをしらみつぶしに移動して、行けない場所があれば分断されている」というアルゴリズムを再帰を使って実装したのですが、これはかなり遅いはず。
もっと良い方法があると思うんだけどなぁ。

ちなみにCodeIQの問題を解くと、いろんな会社からスカウトメールが届くようになります。
もちろんほとんどが自動的に送られるメールなのですが、誰かに求められている感じがするのは、気分が悪くはないです。
ちなみにこんな本も買ったので、ちまちまと解いていければと思います。

アルゴリズムプログラミングもくもく会は、自分自身のために定期的に行っていこうと思っていますので、お時間のある方は是非ご参加ください。

Pocket

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA