LeetCodeで頭の体操とコンピュータサイエンスのお勉強
この記事は note株式会社 Advent Calendar 2022 の 15 日目の記事です。
LeetCode はプログラミング問題の対策サイトだというのが専らの紹介文だと思うんだけど、別にそれだけに限定した使い方じゃなくても十分楽しいサービスだよ、という話をしたい。
LeetCodeとは
改めて LeetCode とはなにかを説明すると、ソフトウェアエンジニアの就職面接でよく出題されるプログラミングの問題を集めた Web サイトである。このサイトで多くの模擬問題を解くことで、特に大手企業の就職面接の対策ができるというわけである。
現在 2504 問が公開されていて、各問題にはジャンルごとのタグ、難易度、解法、ユーザー同士のディスカッションの場などが用意されている。
たとえばこんな感じの問題がある。
サンプル問題
問題文自体はシンプルで、累乗を自分で実装してみてということが求められていて、難易度は Medium、Example が 3 つ、Constraints が 4 つ、正答率は 32.8% となっている。また、問題文の上にいくつかタブがついていて、
Description: 問題ページ
Discussion: ユーザーの質問投稿ページ
Solution: 公式の解法、ユーザーの解法
Submission: 自身の回答結果
が見られるようになっている。更に、Facebook、Apple、Amazon などで類似の問題が出たことを示すタグがついているので、受けたい企業で頻出している問題を中心に解きたい場合は、このタグを利用するとよい。
身につくスキル
効率のよいアルゴリズムを考えようとする姿勢
上のサンプル問題でいうと、一見「 x を n 回かけるループを実装すれば良さそう」という見立てはつくんだけど、与えられた条件を見てみるとそう簡単にはいかないことが分かる。
x も n もマイナスの値を取り得る。
2,147,483,647回も累乗しないといけないケースがある。
負の累乗 $${x^{-n}}$$ も考慮する必要がある。
実際、単純に「 x を n 回かけるループを実装」をしてみても、タイムアウトになってしまいパスしない。問題を多角的に捉えて、ただ答えを出せるコードではなく、効率よく答えを出せるコードを書かなければならない。
昨今の Web 開発において、プログラミング言語やハードウェア自体が賢くなっているかつリソースにも余裕があることが多いため、素直にコードを書けばそれで済んでしまうことがある(※効率の悪いコードを書いてバグを起こすことももちろんある)。ただ、それで済んでしまうのは、効率よく実用に堪える言語やライブラリを実装してくれている人たちのおかげだったりする。
そうしたいわゆる「気にしなくても済んだ」複雑な技術や考えた方を身につけるには LeetCode は良い教材になりそう。
プログラミング言語自体で提供している標準ライブラリとかをそのまま使って解いてしまうのは、そういう意味ではなにかもったいない気がする。
コンピュータサイエンスの基礎知識
アルゴリズムとはなにかというと、ある解を求めるための計算ステップを指す。この計算ステップをより少なく、効率よくすることで大量の計算を省エネで行うことができる。通常コンピュータが行う計算は 1 + 1 = 2 のような単純なものだけではなく、大量の入力を制限時間内にさばいて結果を返さないといけない「限られたリソース下で行うやりこみゲー」のため、過去にいろいろな理論やテクニックが考案されてきた。
そうしたものの中には定番というかクラシックな理論が長らくあって、LeetCode ではそれらを体系的に学べるコンテンツも用意してある。
英語
LeetCode に日本語版は存在しないので、英語で問題文を読んで解き、英語で解法を読んで理解する必要がある。すでに英語でドキュメントを読んでいる人にとっては特にハードルの高いことではないし、LeetCode で対策する企業は海外の企業がほとんどのため、必然的に入社してからも英語でコミュニケーションを取ることになるので、なんというか避けて通るものでもない気がする。
苦手だからといって翻訳機能で凌ぐのは最初は仕方ないにしても、新出単語を調べる機会をみずから損失していてもったいない。
あと単純に日本語でよく見る問題文の表現は英語だとこうなるのかという発見が毎回あるので面白いし勉強になる。
※たまに情報が足りていない問題文や解説があったりして、何度読んでも意味が分からない文章に出会ったりする。コメント欄を見ると同じように困っている人もよくいて、他のユーザーの補足があって初めて理解できたりして「いやそこ書いといてくれよ…」となることも間々ある。
なんでLeetCodeはじめようと思ったのか
面白そうだから
数学は苦手科目で大学受験のときの成績もあまり良くなかった。だけど、問題を考えることは割と好きであったのと、上記であげた 3 つのスキルが付きそうだなと思ったからとりあえず有料会員になって始めてみた。結果、その見立ては間違っていなかった。いいサブスクである。
コンピュータサイエンスの勉強をはじめたいから
「別に CS の degree なくても仕事やっていけるよ」という論もありそうだし、そういう類の Quora とかいっぱいありそう。
あった。
それでも、まだ知らない知識がいっぱいあるなら勉強しようと思えるし、その方が面白い。その点、LeetCode は学習コンテンツが他の類似サービスに比べてとても充実しているので、じっくり体系的に勉強したい人向けかなと思っている。
実際に手を動かしながら学びたい人におすすめ
就職面接対策のために LeetCode を使うのはもちろんおすすめする。実際の大手 IT 企業に内定もらったユーザーがその勉強法を LeetCode 内の掲示板に投稿してたりするので参考にしやすい。
それもそうだし、CS の知識もかじりながら楽しく手を動かして色々学びたい方にも LeetCode はホントおすすめする。今の時点で 2500 問以上あるので、到底一年とかじゃ制覇できない量の問題が待っている。一日一問解くのだけでもフルタイムの仕事がある人にはちょっとしんどいかもしれないので、すぐ終わってしまうのではという心配はない。
ぜひ、試しに一問解いてみてほしい。
・・・
他に面白そうなもの(おまけ)
MIT 6.006 Introduction to Algorithms, Spring 2020
アルゴリズムと様々なデータ構造を元に色々な問題を解いていく入門講義。MIT が一般公開している。2011 年の方観てたけど 2020 年の比較的最近のやつがアップされていたのを知ったのでこっちも観てみようと思う。
Computer Science Roadmap
コンピュータサイエンスの勉強で網羅すべきトピックとそれらを勉強できる無料コンテンツのリンクを紹介しているサイト。
こういう感じの図が見られるので、LeetCode などでカバーできなかった部分をつまんで勉強してみようと思う。
ちなみに、この手のロードマップの図は他の分野もよくあって、改めてソフトウェアエンジニアのカバーしている領域って年々広がっているよなと思うばかり。それはそれで楽しいし良い職業だとは思うんだけど、やはり相応の努力と資質(こういう大量で広範囲の知識を常に獲得する姿勢と気概があるかとか)は求められるよなあと思った。