アルゴリズム攻略の絶対条件：トレースの技術

どうも、アルゴリズムの問題を解いていて、うわー複雑だーって頭を抱えちゃうことありますよね。 実はですね、そんな状況をガラッと変える、たった一つの、でもめちゃくちゃ強力なテクニックがあるんです。 これをマスターすれば、今まで難解に見えていたコードが、きっと驚くほどクリアに見えてきますよ。さあ、その秘密に迫っていきましょう。 ループが何回も回って、変数の値がどんどん変わっていく。あれ？ちょっと待って。今この変数の値っていくらだっけ？ って気づいたらもう完全に思考がフリーズしてる。どうです？こんな経験一度はありませんか？ これね、あなただけじゃないんですよ。アルゴリズムを学んだことがある人なら、もう誰もが通る道なんです。 もしさっきみたいなパニックに陥ってしまうなら、もしかしたらその問題へのアプローチが、根本的に間違ってるのかもしれません。 このスライドの言葉、ちょっとドキッとしません？コードをね、まるで小説みたいに、ただ目でずっと追いかけてるだけだとしたら、 それが迷宮に迷い込む一番の原因なんです。ここで発想を180度グイッと変える必要があります。 そもそもですね、コンピューターってコードを読んで意味を理解してるわけじゃないんですよ。 彼らはただ1行1行書かれている命令を、馬鹿正直に実行してるだけなんです。だから僕らがやるべきことは一つ、 そのコンピューターの動きをそっくりそのまま真似すること。つまり読むんじゃなくて、実行をシミュレーションするんです。 この右側、これこそが正解へのたった一つの道なんですね。そしてそのコンピューターの動きを紙の上で再現する、 魔法のような技術こそが、このトレースなんです。やることはシンプルで、プログラムを上から1行ずつ追いかけて、 変数の値がちょっとでも変わったら、その瞬間にその値を全部メモしていく。一見すると、すっごく地味な作業に見えるかもしれないんですけど、 これが実は、一番確実で、最強の武器になるんです。トレースって聞くと、なんか難しそうって思うかもしれないですけど、全然そんなことないです。 これ例えるなら、そう、RPGのステータス画面。あれを思い浮かべてみてください。敵から攻撃を受けてHPが減ったり、 レベルアップして攻撃力が上がったりしますよね。キャラクターの今の状態って常に画面に表示されてるじゃないですか。 プログラミングの変数も、全く同じ。その変化をリアルタイムで記録していく、もう本当にただそれだけのことなんです。 で、そのステータス画面の役割をやってくれるのが、このトレース表です。見てください、超シンプルですよね。 プログラムに出てくる変数を全部書き出して、まずは初期値をセットする。ここが僕らの冒険のスタート地点ってわけです。 今回は例として、変数iとtotal、この2つを用意しました。 さあ、実際にプログラムが動き出したとしましょう。ループの1週目、スタートです。 まず1行目の処理でiが1増えて1になる。そしたら間髪入れずに、表のiを1に書き換える。はい、次。 次の行で、totalに現在のiの値、つまり1が足されます。 これもすぐに表に書き込んで、totalを1にする。こんな風に、1行ずつ淡々と、機械的に処理を追いかけて記録していくんです。 そして、これが今の処理を反映させたトレース表です。どうです？一目瞭然ですよね。 今どの変数がどんな値を持っているのか、完璧に視覚化されてます。たったこれだけでも、頭の中がめちゃくちゃスッキリすると思いませんか？ これがもっと複雑な条件分岐とか、2重ループとかになったら、その威力はもう絶大ですよ。 ここまで見て、いやいや分かるけど、正直ちょっと面倒くさいな、頭の中でやった方が早いんじゃないのって感じた方いますよね。 僕も最初はそう思いました。でもどうしてこの一見遠回りに見える手作業が、頭の中だけで考えるよりも圧倒的に、しかも確実に優れているのか、その理由をこれからお話しします。 理由は、ものすごくシンプルです。僕たちの脳みそは、コンピューターみたいにはできてないから。 一度に覚えておける情報の量、いわゆるワーキングメモリーって、実はものすごく小さいんですよ。 例えるなら、すぐに散らかっちゃう小さな作業机みたいなもの。そこにループ処理で、次から次へと新しい情報が放り込まれたら、 もう机の上はぐちゃぐちゃ。どれが最新の値だったかなんて、必ず見失っちゃうんです。 ですから、ここで一つだけ、絶対に守ってほしい鉄の掟があります。それは、脳内実行は原則禁止、ということです。 アルゴリズムの問題を解くときに、頭の中だけで変数の値を追いかけるのは、もう今日からきっぱりやめてみましょう。 それって地図も持たずに巨大な迷路に飛び込むようなもの。わざわざ自分で自分を迷子にさせてるようなもんなんです。 さあ、今日のまとめです。これで勝利への道筋ははっきり見えましたよね。 コードは読むな。1行ずつ実行をシミュレートせよ。そしてその過程をトレース表にすべて書き出すこと。 一見面倒に思えるこの方法こそが、実はアルゴリズムという科目を攻略するための唯一にして、最速のルートなんです。 これから皆さんがアルゴリズムの問題に立ち向かうとき、どうかこの言葉を思い出してください。 「書くものが勝つ」。面倒くさがらずにペンを動かし、コンピューターの動きをシミュレートしたものだけが、どんなに複雑な迷路でもゴールにたどり着けるんです。 その一手間が、試験本番での、本当に大きな一歩に繋がるはずですからね。