アルゴリズム学習初心者の学びとAtcoderのレーティングが茶色になるまで時間がかかるという現実に向き合う
今回はアルゴリズムに関しての学習と、やってみて感じたことをまとめた。
基本情報処理技術者のアルゴリズム
アルゴリズムにどのようなものがあるかは、ざっと基本情報処理技術者試験の内容を見ておくと良い。
基本情報処理技術者試験については内容をわかりやすくまとめてくださっている方がいるので参考になる。アルゴリズム以外の動画も公開されているので、その他の動画も見させていただいている。
無料で基本情報の範囲をざっと確認することができ、感謝です。
【午後_アルゴリズム】01. アルゴリズム問題の対策| 基本情報技術者試験
手元にあったキタミ式の書籍（平成30年度のやつだけど）も大体同じようなトピックが解説されていた。
- キュー
- First In First Out
- スタック
- Last In Last Out
- 木構造（2分木）
- ルート、ブランチ、ノード、リーフ
- 完全二分木
- 2分探索木
- ヒープ木
- 線形探索法
- 前から順番に探していく
- 二分探索法
- 昇順、降順に並んでいる配列を真ん中で区切り、データを探索する方法
- ハッシュ法
- ハッシュ関数を使って目的のデータを探索する方法
- 基本交換法（バブルソート）
- 隣り合うデータを交換して並べる
- 基本選択法
- 最大値、最小値を選択して先頭のデータと入れ替える
- 基本挿入法
- 適切な位置にデータを挿入していくやり方
- シェルソート
- 一定間隔で取り出して並べ替え、さらに間隔を狭めて並べ替えて取り出し、というのを1つになるまで繰り返す
- クイックソート
- 中間となる値を決めて、分けた中でさらに中間となる値を決めて、というのを繰り返して並べる
- ヒープソート
- 子要素は親要素より常に等しいか大きい。または常に等しいか小さいという構造を持つ木から整列させる
- マージソート
- 2分割を繰り返し、1つになったら並べ替えながら戻す
- 再帰処理
アルゴリズムx数学が基礎からしっかり身につく本
実際にはもっと色々なアルゴリズムがあり、その一部を「アルゴリズムx数学が基礎からしっかり身につく本」でもう少し学んだ。
本の中で中学校程度の数学の知識があれば理解できるといったことが書いてあったが、実際には4章の途中から理解できないことが増えていった。
対数、階乗、場合の数、数列、確立、集合、ベクトル、行列、微分積分など高校でやったことの復習になるが、これらの知識を応用して問題を解かなければならない分、難しい。
書籍で紹介されていたアルゴリズムの例には以下のようなものがあった。
個人的なこの書籍の使い方は、書籍を一通りやってわからない箇所は飛ばしつつ、競技プログラミングの問題に取り組んだりして必要な時に参照するというやり方。プログラミングは実際に手を動かした方が理解が早く進む。 というわけでAtcoderの競プロ典型90問にチャレンジした。
Atcoder 競プロ典型90問
取り組んだAtcoderの課題難易度が★2となるので、難易度が150 ～ 399、茶色が400からとなるのでレーティングは灰色の問題だ。
レーティングと色の関係などについては色々なまとまっている記事が出てくるので割愛させていただく。
今回は競プロ典型 90 問から★2の問題をやってみた。
競技プログラミングでよく使われる言語はPythonとC++のようだが、最近C言語やC++を少し学習したので、C++で取り組んでみる。
004 - Cross Sum（★2）
何度も間違えつつ取り組んでいくと、出力結果は正しいものの、TL（時間オーバー）になってしまう解法までは作成できた。
#include <iostream> using namespace std; int A[2009][2009]; /* 入力値を入れる配列 */ int B[2009][2009]; /* 出力値を入れる配列 */ int main() { /* 入力を受け取る */ int H, W; cin >> H >> W; for (int i = 1; i <= H; i++) { for (int j = 1; j <= W; j++) { cin >> A[i][j]; } } /* ijで答えに入れる配列のループを作り、kjで列と行の足し算を行う */ for (int i = 1; i <= H; i++) { for (int j = 1; j <= W; j++) { for (int k = 1; k <= H; k++) { B[i][j] += A[k][j]; /* 列の足し算 */ } for (int l = 1; l <= W; l++) { /* 列で既に足し算をしている箇所はスキップ */ if (j == l) { continue; } B[i][j] += A[i][l]; /* 行の足し算 */ } } } /* 出力する */ for (int i = 1; i <= H; i++) { for (int j = 1; j <= W; j++) { cout << B[i][j] << " "; } cout << endl; } return 0; }
縦横それぞれ2000与えられた際の最低限の計算量の見積もりは、forループのネスト3回を考えると2000*2000*2000=2*10の9乗となり、制限時間の5秒に間に合うかどうか微妙なところになる。
実際にこのロジックで実行したところ5.5秒の実行時間となりTLとなった。
このことからforループの量は最大でも2回に抑えたい。
これを実現するには何度も同じ計算をしている箇所を省く必要がある。
一旦1行、1列を計算すれば、次に同じ列、行を計算するときは同じ値を使いまわせば良いからだ。
何度も考えたが解法が浮かばなかったため、答えをチラ見すると列と行をそれぞれ分けて定義していたため、それを踏まえてもう一度コードを書き直した。
#include <iostream> using namespace std; int A[2009][2009]; int B[2009][2009]; int ROW[2009]; /* 行を定義 */ int COLUMN[2009]; /* 列を定義 */ int main() { /* 入力を受け取る */ int H, W; cin >> H >> W; for (int i = 1; i <= H; i++) { for (int j = 1; j <= W; j++) { cin >> A[i][j]; } } /* 行を事前に足し算 */ for (int i = 1; i <= H; i++) { for (int j = 1; j <= W; j++) { COLUMN[i] += A[i][j]; } } /* 列を事前に足し算 */ for (int j = 1; j <= W; j++) { for (int i = 1; i <= H; i++) { ROW[j] += A[i][j]; } } /* 行と列の足し算 */ for (int i = 1; i <= H; i++) { for (int j = 1; j <= W; j++) { B[i][j] = ROW[j] + COLUMN[i] - A[i][j]; /* それぞれの列と行を足し、被った部分を引く */ } } /* 出力する */ for (int i = 1; i <= H; i++) { for (int j = 1; j <= W; j++) { cout << B[i][j] << " "; } cout << endl; } return 0; }
上記でforループを3回繰り返すことなく実行できた。答えを見るとほぼ同じやり方をしていた。
Atcoderで茶色になるまで時間がかかるという現実について
アルゴリズムの学習をしているとかなり時間がとられてしまい、他のやるべきことが疎かになりやすいということがある。
また、実務に直結するのかというと必ずしも直結するわけではない。
それでも学習をする意味としては時間がかかる分、アルゴリズムを要する課題があったときに下地がないと対応できなくなること。
基礎といわれる範疇に入るので、時間がかかるから避けるというのはあまり良くない。時間はかかってもやるべきではある。
情報系の学部出身の人たちはこの辺りはやってきていることだと思うし、やってみるとわかるが、一つの問題を解くのにかなり考えるので、思考力は養われる。
基本情報のような資格試験でアルゴリズム学習するのも良いが、Atcoderは実際にプログラミングをして手を動かしながら考えることができるので、資格試験でアルゴリズムを学ぶよりも思考力を養うことができる。
実務で必要になった場面での引き出しを作るという面では、競技プログラミングに参加するなどした方が良さそう。
レーティングがはっきりと分けられていて、最初のレーティングである灰色から次の茶色になるまで隔週でやっているとおそらく1年以上かかることが予想されるので、今からやって時間をかけても大した実績になりはしない。それでもやらないよりは遥かに良い。
ただ何に時間を割くべきなのかというのは様々なやるべきこととの兼ね合いを見て決断するものであり、そのやるべきことは定期的に考えていくべきことでもあるので、その辺りは今後も定期的に振り返り、計画立てて日々を過ごしていく。
