アルゴリズム学習実践ガイド

[[158318]]

ほぼすべてのトップクラスのインターネット企業やソフトウェア企業は、ソフトウェアエンジニアを評価するためにアルゴリズムとデータ構造を使用しています。ただし、アルゴリズムの重要性や実際の仕事に役立つかどうか（これは優秀なプログラマーにとって不可欠な基本スキルだと思います）を議論するつもりはありませんし、「Googleスタイル」の「アルゴリズム面接」や「ホワイトボードプログラミング」の有効性や合理性を議論するつもりもありません。私は「競技プログラミング」のバックグラウンドを持たない単なるエンジニアです。私自身のアルゴリズムとデータ構造の学習プロセスの一部を共有したいと思います。議論や批判は歓迎します。

私自身の学習経験と「インフォマティクス コンペティション」のコーチとしての教育実践を組み合わせると、アルゴリズムの学習には一般的に次の 3 つのことが重要であると考えています。

1. まずは「表現力」を練習する

大学院入試に向けて勉強している学生から、「教科書に載っているアルゴリズムは『理解』しているし、多肢選択問題や手作業で導出する問題にも答えられる。でも、それを『コード』や『疑似コード』として書くことができず、アルゴリズムの問​​題となるとさらに困ってしまう」という質問によく遭遇します。私の意見では、これはまず第一に「表現力」の欠如です。

経験豊富なプログラマーでない限り、プログラミング言語の構文を学ぶときに最も重要なことは、ロジックとプロセスを「表現」する方法を学ぶことだと思います。多くのアルゴリズム競技の本には「シミュレーション法」と呼ばれる手法が載っています。これは簡単に言うと、問題に対処するために私たちが自然に行う手順を「そのまま」かつ「プログラム」する手法です。例えば、「最大数を求める」という処理や、「行列演算」という処理、「基数変換」や「最大公約数を求める」際に使用する「ユークリッドの互除法」、縦割り計算をシミュレートする「大きな整数の加算」など、この「処理」をプログラムを通じて直接「シミュレート」することができます。ほとんどのプログラミング本では、言語の表現力を高めるために、文法を紹介する際にこれらの質問に似た演習を提供しています。 Python をメイン言語として使っている場合、「Learn Python the Hard Way」には表現力を練習するための質問が多数用意されています。コースを修了すると、間違いなく多くのことが得られます。 「HackerRank」には「プログラム表現」を練習するための特別な「ドメイン」があり、Asange さんが出す質問はなかなか良いものがほとんどです。

簡単なアプリケーションタイプの「デモ」を開発すると、言語表現を学ぶのに役立ちますが、そのロジックが単純すぎることが多いため、この種の練習には役立ちません。

2.まず読んでから練習問題に取り組む

実際のところ、「アルゴリズム入門」を最後まで読み終えて、上記の演習をこなした人は多くありません。私は主に参考書として使っており、時々いくつかの章を詳しく読んだだけです。アルゴリズムの基礎知識が十分でない初心者には、よりシンプルで理解しやすい Robert Sedgewick の「Algorithms」をお勧めします。アルゴリズムの原理と実行プロセスを理解し、プロセスを手動でシミュレートする方法を学び、自分で実装してみます。いくつかの質問を練習して、アルゴリズムの理解を継続的に強化します。

本の練習問題をもっと練習すると、自分で「OJ」から問題を探すよりも通常は良い結果が得られます。特に、証明や分析の問題の中には、直接コードを記述する必要がないものもあり、アルゴリズムの本質の理解を促進できます。たとえば、「クイックソート」の最悪ケースと最良ケースがどのように生成されるか、分割にランダム戦略と固定戦略を使用することの長所と短所、このソートアルゴリズムが「不安定」である理由などです。これを踏まえて、「コーディング」の実装能力を向上させ、アルゴリズムの理解を深めるためには、「OJ」問題の演習を行うことがより効果的です。

こうしたトレーニングを通じて、少なくともアルゴリズムが明確な問題に関しては、コードを正しく記述し、その後「デバッグ」を通じて詳細を解決することができます。

3. 問題の軽減と変革

時々、私は生徒に「二分木のレベルトラバーサル」を書くように明示的に指示し、彼らはそれを書けるかもしれません。しかし、私が彼に「重み付けされていないグラフ」上の「最短経路」を見つけるように頼んだとき、彼は困惑しました。時々、「データ構造」で学んだように、「グラフ」が「隣接行列」や「隣接リスト」で表現されていない場合、問題を「グラフ」に変換する方法が分からないことがあります。彼らは、ここでの「グラフ」は目に見えないグラフである可能性があり、特定の「ノード」に接続されたすべての「ノード」を見つける必要があることを理解していません。見つけるプロセスは、ポインタによって指し示される「実体のあるエッジ」である場合もあれば、何らかの数学的演算または変換の後に取得される値である場合もあります。 「8 人のクイーン」問題のような問題では、正しい解決策を得るために、深さ優先順序で状態グラフ全体を走査しながら、ある状態から別の状態に変換する合理性を常に確認します。私たちのコンピュータは本質的に「ステートマシン」であり、動的プログラミングや検索は状態遷移から正しい解決策を見つけることにかかっています。動的計画法、貪欲法、再帰法など、それぞれの具体的なアルゴリズムの意味については、「Quora」や「Zhihu」に質の高い回答や分析が数多く掲載されています。学習中にそれらを読むことで、疑問を解決することもできます。

問題の削減と変革には継続的な実践が必要です。そのため、先に述べた「アルゴリズム」に加えて、問題を練習するための本を見つけることも非常に重要です。私自身の学習過程では、秋葉卓也著の『チャレンジプログラミング競技会』と劉如佳訳の『チャレンジプログラミング: プログラミング競技会トレーニングマニュアル』を使用しました。基礎が弱い学生は、Liu Rujia の『アルゴリズム競争古典入門（第 2 版）』を選択できます。

私たちの目標はアルゴリズムを学ぶことであり、問​​題を練習して「競技プログラミングプレイヤー」になることではないので、練習するには古典的な問題だけを選択すればよいと思います。私自身は「競技プログラミングプレイヤー」ではありませんが、学習と練習を通じて、特に「難しい」問題でない限り、「Leetcode」や「CC150」、大学院入試レベルの難度にも簡単に対応できます。もちろん、アルゴリズムを学ぶ目的は面接のためではありません。アルゴリズムは私たちの仕事にも大いに役立ちますが、ここではそれについては触れません。

自信がついたら、「Leetcode」で典型的な面接の質問を解いてみましょう。アメリカの大手企業の面接の質問は何度も同じで、本当に創造性に欠けています。あるいは、「ハッカーランク」に行って、会社の「採用目的」のコンテストに参加して、壁を乗り越えてアメリカに行くこともできるかもしれません。