アルゴリズム構築能力って何? (vol.4)

 2018.01.19  株式会社システムインテグレータ

AtCoder株式会社 代表取締役社長 高橋 直大
(Twitter:@chokudai )

アルゴリズム構築能力って何?

アルゴリズムは、全てのプログラミングにおいての基礎です。

この主張について、反論する人は多くいます。「有名なアルゴリズムである〇〇法を使ったことがない」だとか、「実際の開発現場において、複雑なアルゴリズムは登場しない」だったりとか、そんな意見が多いです。ですが、こうした人はアルゴリズムの表層しか見ていないのではないでしょうか?

上に書かれた反論はその通りで、各アルゴリズムが開発現場において使われる場面というのは少ないです。なので、「アルゴリズムの知識が役立つ場面が少ない」について、僕は否定するつもりはありません。

ですが「アルゴリズム構築能力はまるで役に立たない」ということにつながるわけではありません。役に立つのは「アルゴリズムを多数知っていること」ではなく「アルゴリズムを構築できる能力」なのです。
複雑な処理に対してどのように実装するべきかを考察し、適切に実装出来る能力こそがアルゴリズムの構築能力です。プログラミングにおいてこの能力が必要ない場なんて殆どないのではないでしょうか?

TOPSICで計っている能力も、このアルゴリズム構築能力に他なりません。

アルゴリズム構築能力の伸ばし方

さて、前述したアルゴリズム構築能力ですが、普通に業務の開発をしていても意外と伸びていきません。
これは持論ですが、その理由は「アルゴリズムの構築能力を伸ばすための負荷が十分にかかっていない」からだと僕は考えています。

例えば、体力を付けたいと思った時に普段通り歩いているだけではなかなか体力はつかないですよね?
体力をつけたかったら、ランニングをするなど体に負荷をかけてあげないといけません。
スポーツなどでも、試合形式の練習ばかりしていては上達効率はあまりよくないでしょう。

アルゴリズムの構築能力もそれと同じです。普段通りのプログラミングをしていても、なかなかアルゴリズムの構築能力はつきません。
アルゴリズムの構築能力を効率よく高めるには、アルゴリズムの構築能力を普段以上に要求される、脳に負荷のかかるプログラミングに取り組む必要があるわけです。

プログラミングスキル判定サービス関連資料


プログラミングコンテストを利用した学習

ここまで読んで、みなさんは「アルゴリズム構築能力をつけるために、脳に負荷をかけるためにはどうしたら良いか?」と、当然思うと思います。

その疑問を解決する最強の手段こそが、プログラミングコンテストです!

AtCoder: http://atcoder.jp/

プログラミングコンテストに出題される問題は、まさにアルゴリズムの構築能力が問われる問題です。
「特別なアルゴリズムを覚えていないとコンテストの問題が解けない」と思っている人は多いですが、覚える必要のあるアルゴリズムは実はそれほど多くなかったりします。

「与えられるデータをよく考えてみると、実はこういう性質を持っているから、これだけの処理でできる!」だとか、
「求めたいのはこれで、普通はこう解かないといけないけど、よく考えるとこれってたったこれだけの処理で出来る!」みたいに、
各問題について考察をし、アドホックに答えを探していくような問題が多いです。

具体的な問題を見ていきましょう。

高橋くんはSNSの管理者をしています。このSNSではユーザ同士が友達という関係で繋がることができます。高橋くんはそれぞれのユーザの「友達の友達」が何人いるかを調べることにしました。友達関係が与えられるので、各ユーザの「友達の友達」の人数を求めてください。ただし、自分自身や友達は「友達の友達」に含みません。

問題詳細:https://abc016.contest.atcoder.jp/tasks/abc016_3

この問題は、情報科学で言うと、「グラフ理論」にあたります。
グラフ理論で有名なアルゴリズムは、ダイクストラ法や、ワーシャルフロイド法などの、最短経路問題などでしょうか?
確かにこの問題は、最短経路問題として解くことも出来ます。
友達関係をグラフに見立て、距離がちょうど2であれば、友達の友達であると言えるからです。

ですが、そんな小難しいことをこの問題で考える必要はありません。
「AさんとBさんが友達の友達である」という条件は、

- AさんとBさんが直接の友達でない
- AさんとCさんが友達であり、BさんとCさんも友達であるようなCさんが存在する

の2つの条件を満たす人が、友達の友達と言えます。
だったらこのような条件を満たすCさんが存在するかどうかを、各A,Bのペアごとに全て調べてしまえば良いだけです。
このアルゴリズムに名前はありませんし、ちゃんと考えればすぐに思いつくのではないかと思いますが、この難易度の問題でも、早く正確に実装出来る人は、正直なところあまり多くはありません。

こうした問題が解けるようになるために必要なのは「有名アルゴリズムの知識」では決してありません。
その問題の性質についてよく考え、正しく計算するためにはどうしたら良いかを考える思考能力こそが大切です。
これは、本などを読むだけではなかなか身につくものではなく、実践的な思考を繰り返すことで鍛えられます。

みなさん、ぜひプログラミングコンテストに出場して、アルゴリズム構築能力を高めてください!

TOPSIC ご説明資料

RECENT POST「プログラミングスキルに向き合う」の最新記事


この記事が気に入ったらいいねしよう!