2ヶ月くらい地道に読んでいた「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」読み終えた。
プログラミングコンテストにデビューするために読んだ。。 。わけではなく、アルゴリズムとデータ構造をちゃんと勉強してみようと思って、評判のいい教材を探していたら本書を見つけた感じ。
サンプルコードはCとかC++だけど、普段Rubyばかり使っててCとかあんま知らない私でもその点は大丈夫で普通に読めた。
内容
「Aizu Online Judge」という会津大学が運営しているオンラインジャッジシステムの問題を取り上げてその問題を解説しながらコンピュータサイエンスのメジャーな アルゴリズムとデータ構造を勉強できる。
「基礎編」で情報処理試験でも見るような並び替えアルゴリズム、データ構造、探索ヒープ、グラフアルゴリズム(グラフアルゴリズムは情報処理でみた覚えない気も。。)を学んで、「応用編」でその知識を応用して高度なデータ構造、グラフアルゴリズム、計算機科学、動的計画法、整数論、ヒューリスティック探索とだんだん問題の難度が高くなってく感じ。
感想
ソートアルゴリズムとかデータ構造とか探索アルゴリズムとかは学んだことがあったけど、そこから繋がっていくグラフアルゴリズムを学べたのが個人的には良かった。
本書の中で
コンピュータで扱う多くの問題は「対象」とそれらの「関係」を抽象的に表した"グラフ"と呼ばれるデータ構造で表すことができます。
と書いてあるけど、例えば深さ優先探索と幅優先探索とハッシュを組み合わせて行くとチェス盤にどのクイーンも他のクイーンを襲撃できないようにする「8クイーン」問題がとけたりする。
こうして初歩的なデータ構造とアルゴリズムを発展させて応用していろんなパズルが解けるようになるんだな。。
と、こうしてどう使われているかをイメージできるとアルゴリズム学ぶのも面白くなってくる感があった。