📝

LeetCode 150問を解いて起きた意外な変化

2023/02/18に公開

はじめに

年末に Twitter でこのツイートを見かけました。

もともとアルゴリズムの勉強に興味があり、一年ほど前に数ヶ月だけ AtCoder をやっていましたが、途中で挫折してしまった自分にとって、NeetCodeの勉強ロードマップは非常に魅力的に感じました。(転職意欲があったわけではないです)


NeetCode のロードマップ

そこで、このロードマップに従って LeetCode の問題を 150 問解くことを決意し、結果的におよそ1ヶ月半で全ての問題を解き切ることができました。
この過程で、様々なことを学ぶことができました。中には自分が予想していなかった学びも多くありましたので、同じくアルゴリズムに興味のあるエンジニアの方に役立てていただけるよう、記録として残しておきます。

ハードスキル

📗 データ構造への理解

頻出するデータ構造について、それぞれの長所/短所を理解し、主要な処理の計算量が即座に答えられる状態になりました。それに伴い、自分が考えたアルゴリズムの計算量が問題の制約を満たしているかを判断することができるようになりました。こうして、問題を解くための基礎知識がようやく揃ったことによって、アルゴリズムの奥深さを痛感しました。

  • データ構造の選び方一つで、アルゴリズムのスケーリングが決まる。
  • 問題の制約によって最適解が異なる。

結果的に、個人開発や仕事などでプログラムを書く際にも、明らかに意識が変わりました。どの変数がスケーリングするか、それに耐えられるようにするためにはどのようにデータを持つべきかなどの視点を持ちながらコードを書くことができるようになったのは、大きな成長だと感じています。

🙄 定番アルゴリズムへの理解+ミュータブル処理への慣れ

二分探索やDFS/BFS、スライディングウインドウなどの定番アルゴリズムを、問題に応じたバリエーションを加えながら構築することができるようになりました。これらの勉強を通じて、問題設定に適したデータ構造への落とし込み、アルゴリズムの発想について学べたのはもちろんですが、それに伴ったミュータブルな処理に慣れることができたのが大きな学びでした。
筆者は普段の業務で React/TS を書くことが多く、できるだけイミュータブルに(宣言的に)処理を書くことが求められます。しかし、競技プログラミングのアルゴリズム問題を高速に解くためにはミュータブルな操作が多く必要になります。このギャップが、普段イミュータブルな思考を持っていない自分にとってかなり良い刺激であり、状況に応じてミュータブル/イミュータブルなコードを柔軟に使い分けられるようになったと感じています。

👻 アルゴリズム問題解決フローの仮説

与えられた問題に対してこう考えると比較的解きやすい、という型を自分の中で見つけ出せた気がします。ただ、所詮アルゴリズム初心者が考えていることに過ぎないので、つよつよエンジニアの方の中で体系化されたものがあれば知りたいです。(コメントお待ちしています🙏)現時点での問題解決フローの大枠は以下のようなものです。

  1. Brute Force でどう解けるかを考える。
  2. 問題の制約的に Brute Force では厳しい場合、必ず効率化できる部分があるので、適切なデータ構造の選択やメモ化を行って計算量を落とす(もっと深掘りできそう)。
  3. それでもまだ制約を満たす解法が見つからない場合は、問題設定の中に自分が捉え損ねている本質が残されている可能性が高いので、再度設定を考察する(再帰構造やより小さな部分問題など)。

🐛 バグへの嗅覚

効率的なアルゴリズムは大抵の場合、シンプルです。状態をうまく抽象化して保持する変数を少なくしたり、エッジケースを吸収できるような初期値設定にしたりしています。それらと照らし合わせることによって、自分の書いたアルゴリズムがいかに醜いかを判断できるようになりました。条件分岐が複雑であったり、エッジケースの考慮が多い場合には、「これはバグりそう…」という危険信号が脳内で強く発されるようになりました。この感覚は普段の業務でコードを書く際にも役立つと感じています。

ソフトスキル

🤔 分からないことを言語化する力

150問からできるだけ多くのことを学ぶために、より効果的なPDCAサイクルを回したいと考えました。そのため、問題を解けなかった場合には、すぐに解答を見るのではなく、なぜ解けなかったのかを徹底的に言語化してから解答を確認するようにしました。

自分自身の場合、「愚直解は思いつくが計算量を落とせない」というパターンが主だったので、なぜ計算量を落とせないと判断したのかに注力して理由を具体化していました。これにより、解答を見たときに、自分に何が足りなかったのかが明確に分かり、他の問題にも応用可能な学びを得ることができました。

なぜわからなかったか 学び
自分の知っているデータ構造をどう使っても制約を満たす範囲まで計算量を減らせない この問題に適したデータ構造「XXX」を知らなかった。このデータ構造は、fooやbarといった処理を行いたい場合に有効である。
状態遷移に必要な情報はX,Y,Zだが、これらを全て考慮すると制約を満たす範囲まで計算量を減らせない 実は状態遷移の判定には「X+Y」だけでよかった。状態遷移に必要な要素が多すぎる場合は、その値の一部や計算された値だけで十分であるかどうかを考慮する。
状態遷移のパターンが多すぎて、再帰的な構造や動的計画法に持ち込めない。 もっと遷移の具体化を行うことで、状態パターンが限定的であることが分かった。スタートからゴールまでの具体化をより徹底的に行うことで、限られたパターンを見出したり、遷移に必要な要素を把握することができるようになった。

🛠 継続できる設計づくり

私は比較的、習慣化や継続が得意な人間ですが、「LeetCodeを150問解く」と決めた時点で、うまく設計しないと、途中で絶対に挫折すると確信していました。そのため、少しでも成功確率を上げるために、以下のことを行いました。

  • 2月中旬までに終わらせるという目標を決める
  • そこから日々の目標を逆算する(平日2問、休日5問)
  • 自分の努力の過程をグラフ化し、視覚的に振り返れる状態にする
  • 職場の同僚・上司に計画を伝えて退路を断つ

途中のペースが上下することはありましたが、最終的には何とか辻褄を合わせることができ、約1ヶ月半で150問を解ききることができました。

この経験を通じて、戦略を立てることでより習慣化の成功確率を上げられることを再認識しました。

今回初めて「努力の可視化」や「周りに計画を伝えて退路を断つ」という方法を実践してみましたが、この2つはかなり効果的でした。モチベーションが低下してくる中盤で特に効果的で、これらがあったからこそ無事最後まで継続できました。今後何かを習慣化して進める際にも、より良い戦略を立てながら、習慣化そのものも楽しみながら進めていこうと思います。

終わりに

LeetCode 150問を解いてみて、様々な学びがありました。アルゴリズムやデータ構造などへの理解が深まったのはもちろんですが、それ以外にも数多くの点で成長を実感できました。アルゴリズムの勉強が自分の業務のパフォーマンスに直結することは少なそうですが、エンジニアとしての素養を培ったことによるボトムアップ的な効果があるのではないかと期待しています。ぜひ、みなさんも良いアルゴリズムライフをお過ごしください!

Discussion