皆さんこんにちは。システム部のよわよわエンジニア、ダラーです。
今回はleetcodeを使ったアルゴリズムとデータ構造の勉強法について書いてみようと思います。
アルゴリズムとデータ構造とは？
皆さんはアルゴリズムとデータ構造というのをご存知でしょうか？まず、「アルゴリズム」とは、算法とも呼ばれ、コンピューターが問題を解決する際に沿う手順のことで、「データ構造」とは、データを扱いやすくするために一定の形式に当てはめて格納された、データの集合体のことです。
参照：「【入門編】アルゴリズムとデータ構造とは？」
アルゴリズムとは、欲しい結果を得るためにどのような方法でそれを実行するのか、ということを段階的に決めた手順のことです。例えば、任意の数の配列を降順で並び変えるにはどのようなやり方があるか、ということです。そしてデータ構造とは、このアルゴリズムを考える上でどのようなデータの持ち方をするか、というデータ構造のパターンのことです。Javaなどには既に組み込みでこうしたデータ構造が使えるようになっていますが、それはSetやList、Mapといったものです。
参照：Data Structures – Algorithms Basics
日本ではこのアルゴリズムとデータ構造の実装力を競う競技「競技プログラミング」が結構盛んで、Atcoderコンテストなどが有名です。競プロについては、以前弊社エンジニアのプリヤンカさんが書いている記事もあるので、こちらもご覧ください。
英語版：「Let me introduce competitive programming」
日本語版：「競技プログラミングについてお話しします」
最初に言っておくと、私はめちゃくちゃこの競プロが苦手です(爆)…プログラミングを始めたばかりの頃、エンジニア向け学習プラットフォームのpaizaやcodewarsで当時色んな問題をひたすら試していましたが、殆ど解けなくて、当時勉強の面倒を見てもらっていた外部のメンターさんに泣きついて毎度答えを教えてもらい、解説していただいていました。その時の苦手意識が未だに染み付いていて、競技プログラミングは辛い、という心象しかないぐらいです…
ただ競技プログラミングというか、このデータ構造とアルゴリズムはエンジニアである以上避けて通れない問題でもあるので、苦々しいながらもちょっとずつ向き合っています。
ぶっちゃけた話、全部のアルゴリズムとデータ構造について勉強し切った訳ではないのですが、これまで苦手だったこの競プロ力を上げるために自分がしてきたことや、気付いたことについてシェアしてみたいと思います。
アルゴリズムの勉強のコツ
今回はleetcodeを使っていきます。
【leetcode】解く問題を決める
leetcodeには大量に問題が掲載されています。そこがメリットでもあり、逆にデメリットでもあります。というのも、多分普通にleetcodeの問題を見て、上から下までやるにしても、問題数が多すぎるので、効率的にデータ構造・アルゴリズムの勉強をしたかったら、結構大変です(ネットで見ると、Googleに入るために1000問近くの問題を解きました、という記事とか動画が見つかりますが、趣味でもなければ結構キツいはず…)。
そこで、効率的に問題を見つける方法をいくつか紹介したいと思います。
【leetcode】カテゴリで選ぶ
leetcodeには、ソートやカテゴリ選択がちゃんと備わっているので、カテゴリや難易度で選ぶことが出来ます。
例えば今日はLinkedListをやってみようかなと思えば、そのカテゴリで探せるし、ついでに難易度も低いのが良ければ難易度でソートしてEasyから解けば良いです。
検索box上部に表示されているExpandを開くと（↑キャプチャ参考）、アルゴリズムのカテゴリタグが選択できます。
ちなみに
・Solutionにあるマークは、解説があるかどうかです。再生マークが見えているものは、動画の解説もあります
・Acceptanceというのは、問題に挑戦した人が回答にたどり着けた正答率です。これが低いやつは、Difficultyに関わらず結構難しいということです。
・Difficultyは難易度です（と言ってもこれは目安、に近いです）
・Frequencyはどれだけ色々な人が解いているか、という人気度になります。
私のおすすめはFrequencyが高くてDifficultyが低く、Acceptanceが高い問題から始めることです。
【leetcode】これだけ解いておけばOK!効率的にアルゴリズムとデータ構造が学べる問題紹介
そんなに解いてる時間もなければ、効率よくアルゴリズムとデータ構造が学べる良問とかないの？っていう方におすすめなのが、下記の問題から取り組むことです。
また、このどの問題を解けばよいのか分からないという事に関しては、leetcodeの質問箱でもよく議論される問題らしく、この質問箱によく内容がまとまっていました。
「Comprehensive Data Structure and Algorithm Study Guide」
ちなみにこちらはネットでは有名な、LeetCodeで解くべき75問、という記事です。まずここから解いていくのもありですね(実際私はここにある問題を解いているところです)
「New Year Gift – Curated List of Top 75 LeetCode Questions to Save Your Time」
【leetcode】解く時間を測る
さて、問題をピックアップしたところで、実際に解いていくのですが、重要なのは時間を決めて解いてみて、時間内に解けなかったら潔く諦めることです。
解けないと気持ち悪いし、喉元まで答えが出かかっている気がするのに！という気持ちにはなりますが、問題にかけられる時間は有限ですし、多分一日かけて解けなかったら自力で解くのは無理です(笑)
ここは諦めて、答えを見ましょう。(ちなみにleetcodeだと、プレミアムプランを購読しないと解答・解説が見れない問題も多々あります…)
【leetcode】解説読解後、問題に再挑戦
勉強で大事なのは予習と復習、と言いますが、復習はすごく大事です。解説を読んでも、そこで終わってしまったら、残念ながら知識は定着しないのです…
解説を読んで理解したと思ったら、そのあと何も見ずに解いてみると、自分で手を動かしてみることで分かることもあるし、自分でもう一度解いてみたら、解説があまり理解出来てなかった場合にそれにも気づけます。
【leetcode】解説は全部読む
答えは必ずしも1つとは限りません。有名な問題だと、解法が3つ以上ある問題もあります。大抵一番上に一番簡単な解法が書いてあるのですが、ブルートフォース（手当たり次第）方式だったりするので、時間制限などがあったりする問題では普通に落ちるので、出来れば全部ちゃんと読むのがオススメです。
【leetcode】解説がそもそもわからないときは？
そもそも解説の言っていることが全くわからない…という時もあると思います。
多分そういう時は、他の人も難しいと思っていることが多いので、Leetcodeのディスカッション欄を見ると、問題ごとに色んな人のコメントが見られます。ここから解説を見つけるのも良いし、ネットでも大抵のアルゴリズムについては解説記事がいっぱいあります。オススメの動画チャンネルや本については最後に書くので、そちらも参考にしてみてください。
Pythonでやってみる（おまけ）
ちなみにアルゴリズムやデータ構造周りの勉強をする際、よく言われているのが、C言語やJavaみたいなちょっと難易度が高い言語で挑戦するよりPythonでやるのが良いとよく言われています。ライブラリなども豊富なので、自分で全部コーディングするより楽だからです。(もはやどれだけPythonのライブラリを知っているかゲーになりますが)
これからやり始めようかなーという人はPythonで挑戦してみるのもありかもしれません。
ロードマップを参考にする（おまけ）
カテゴリ別に問題を解いていくにしても、どれをどこからやれば良いのか分からない…という方もいると思います。そんな時は、このロードマップを参考にして解いていくのも有りです。
https://neetcode.io/roadmap
「アルゴリズムとデータ構造」おすすめの解説本
いきなりLeetCodeを解いても良いのですが、そもそも概念を良く知らない、という方はまず本か動画で勉強してから取り組むのがお勧めです。以下は自分が実際に読んでみた、見てみたものです。
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
おすすめ度: ★★★★★
難易度:★
個人的にはとりあえず始めたばかりの人にオススメの本です。データ構造ごとに易しい問題から始まります。図もあってわかり易いので、取っ付き易いです。
プログラミングコンテストチャレンジブック
おすすめ度: ★★★
難易度:★★★
競プロ界隈では有名な、蟻本というやつです。ただ、各アルゴリズムなどを難易度順などで紹介してくれる感じではなかったので、初心者がいきなりこれを読んでもちょっと分かりづらいかもしれません。中上級者向けです。
世界で闘うプログラミング力を鍛える本
おすすめ度: ★★★
難易度:★★
これはCracking the Coding Interviewという本の日本語訳です。海外だと本形式になっているアルゴリズムの本だと大体これ一択です。ただ、アルゴリズムなどの説明の分かりやすさは3-1でおすすめしている本の方が分かりやすいです。
コーディング面接対策本で、面接のコツやシステムデザインなどについても書いてあるので、転職目的で勉強したい場合はこちらの本もお勧めです。
なっとく！アルゴリズム
おすすめ度: ★★★
難易度:★★
かなりかわいらしい感じのイラスト付きで、各アルゴリズムについて解説してくれている本です。文字とコードしか書いていない本でアルゴリズムについて理解するのは辛い…とか、そもそもとっつきにくい、苦手意識が、という方に是非お勧めしたい本です。
ただ、説明が若干長いので、とにかく効率的に学びたいという分にはちょっと微妙かも。
プログラマの数学（おまけ）
おすすめ度: ★★★★
難易度:★★★
数学ガールで有名な結城さんの本です。
アルゴリズム解説だと、解法の説明が多くて、数学的な話はあんまり出てこなかったりもしますが、こちらは数学の観点からアルゴリズムを考えるような内容の本になっています。結局のところ、素数を探す問題を解くときは数学のエラトステネスの篩を知っていた方が断然簡単に解けるし、数学知識がゼロだとちょっと厳しいところもあります。私も数学は苦手なのですが、かなり噛み砕いてわかり易く書いてあるので、数学に抵抗感がある人にもオススメです。
「アルゴリズムとデータ構造」おすすめの解説動画
【Youtube動画】Neetcode
アルゴリズム関連では結構有名なYoutubeチャンネルです。LeetCodeとひっかけて、NeetCodeというチャンネル名になっています。
このNeetCodeは結構な数の解説動画があるのと、LeetCode対策と銘打ったサイトの方もあるので、じっくり学びたい方にお勧めです。
【Youtube動画】CSDojo
こちらは個人的にすごく好きなチャンネルです。チャンネルを運営している方は実は日本人の方ですが、解説動画は全部英語です(笑)
ただ、アルゴリズムの説明がものすごく分かりやすくておすすめです。ただ、アルゴリズム解説がメインのチャンネルテーマではないので、上のNeetCodeの方が解説動画はそろっています。
↑の動画チャンネル以外にも、Data Structure and Algorithmで探せばLeetcodeの問題開設ではないですが、基本のことを教えてくれるチュートリアル動画は色々見つかるので、まずはそれで勉強してから取り組むのも良いかもしれません。
「アルゴリズムとデータ構造」おすすめの解説アプリ（おまけ）
アルゴリズム図鑑
本だと紙だからイマイチ分かりにくいし、動画だと解放の説明が多くて、アルゴリズムそのものが分かりづらい…というデメリットはあります。そんなデメリットを解消できるアプリがあります！
これはデバッグするみたく、ステップごとに変化の様子が見られるので、ものすごくわかりやすいです。本でもこのアルゴリズム図鑑が出ていますが、携帯アプリの方が実際に図が動くところが見られるので分かりやすいです（一部課金が必要です）
おわりに
いかがでしたでしょうか？Leetcodeや競プロに挑戦してみたいけど、何をどうやれば良いのか分からないし挫折してしまった、や、とっつきにくいな、と考えている方がいれば参考になれば幸いです。
読んでいただきありがとうございました。
