Studio3104::BLOG.new

uninitialized constant Studio3104 (NameError)

半年間で LeetCode の問題を300問解いてみて（※）

とは言ってみたものの実際にはちょうど1年前くらいからやってました。始めてからすぐ Premium 買ってたので。

ではなんで「半年間で」なのかというと、今年の前半は英語の勉強をがっつりやってたので英語と仕事以外のことは何もしてなかったから。
そして300問はまだいってないんだけど、英語漬けから空けた6月アタマから数えて半年経過の今月末には300問いくだろうという見込みがあるということでタイトルはこのようにした。

f:id:studio3104:20201216144305p:plain f:id:studio3104:20201216144159p:plain

1年間で LeetCode の問題を290問解いてみて

ということで改めて。@sugyan と @fushiroyama *1 に影響されて始めたんだが、続ければ続くものですね。

自分は "コードの書けないインフラエンジニア" として IT エンジニアのキャリアが始まりました。Computer Science とかは履修してません。"コードの書けない" だったはずが "コーディングは自分の仕事じゃない" に気付かずうちに変わっていっていて、あるとき「あれ、これでいいんだっけ...?」ってなってちょっとずつレイヤーを上げて周囲に助けられながら学習して守備範囲を広げていったらそっちのほうが楽しくなっちゃったみたいな感じだった。
ただ楽しくやっている中でもジレンマみたいなものはあって、「アルゴリズムとかデータ構造とかそういうのまったくわかってないけどいいんかな。。まあ楽しいしとりあえずなんとかなってるしいいか。え、ホントにいいんか？」みたいな感じだった。ソートアルゴリズムの名前とか1個も言えない。名前だけ聞いたことあるけど内容がまったくわからないアルゴリズムとかたくさんある。深さ/幅優先探索とか。
そろそろやりどきかな、、となって始めたのが LeetCode だった。

たとえば Two Sum

LeetCode の問題番号1番にもなっているような定番の基礎問題。たぶん。わからんけど。
数値の配列の中から指定の数値が和になるような組み合わせを探すという問題。

愚直に全通りをチェックするとこうなる。 LeetCode 上のこの問題の制約では nums のサイズは最大でも103件なので最悪のケースでも106回ループすれば答えにたどり着ける。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(len(nums)):
                if i == j:
                    continue
                if nums[i] + nums[j] == target:
                    return [i, j]

ちょっとだけ工夫してこうすると最大 500,500 回のループまで削減出来る。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

とはいえ数列を2重にループするのは何か無駄っぽいというのはわかる。でもじゃあ効率的にやるにはどうしたらいいのかはスッとはわからない、in とか使ったらええんか？みたいなのが最初だった。気がする。あんま覚えてない。(list に対しての in も結局最悪のケースでは全要素をチェックするので2重ループと同じということもこのときにはちゃんと考えられていなかったかも知れない。恥ずかしい。)
ループ回数を最小限に抑えるにはこんな感じになる。HashMap (dict) にメモしながら数列をナメていって、和を成す相手が既出だったらそこで答えを返す。HashMap のキーに対しての探索は1回で済むのでループ内で非効率な再探索が行われることはなく、ループ回数は最悪でも103回で済む。スッとは出来なかったもののたぶんこれは自力でたどり着けたと思う。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        memo = {}
        
        for i, n in enumerate(nums):
            t = target - n
            
            if t in memo:
                return [memo[t], i]
            
            memo[n] = i

とはいえこの問題の制約はかなりゆるいので全パターンをナメる Brute Force アプローチでも余裕で現実的な時間内に解答が得られてしまう。しかしながらそんなゆるい制約の問題ばかりなワケはなくて、問題をただ解いていくだけのスタイルだとすぐに限界が来てしまうことになる。

毎日問題に取り組みながら並行して読んだ本

ということで本を何冊が読んだ。読みながら写経したりとかもした。ビッグオーもまったくわかってなかったので本で学んだ。
メモったりページ戻ったりがやりやすいかなと思って本は全部物理で買った。

アルゴリズム図鑑 絵で見てわかる26のアルゴリズム

アルゴリズム図鑑 絵で見てわかる26のアルゴリズム

なっとく！アルゴリズム

なっとく！アルゴリズム

世界で闘うプログラミング力を鍛える本 コーディング面接189問とその解法

世界で闘うプログラミング力を鍛える本 コーディング面接189問とその解法

Elements of Programming Interviews in Java: The Insiders' Guide

Elements of Programming Interviews in Java: The Insiders' Guide

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

こんなもんか？他にもあったかも。アルゴリズム図鑑はめっちゃ良くて完全に絵本。実装例とか一切載ってないんだけど絵でキレイに図解されているのでめちゃくちゃわかりやすいし、いまだにふとしたときに見返したりすることもある。

290問やった結果

LeetCode は難易度が三段階(Easy, Medium, Hard)あるんだが、Medium までなら割とスッと解けるようになってる。Hard はだいたい自力じゃ無理。Hard はマジハード。あと相変わらずずっとビット演算が苦手。。

来年もたぶん続ける

結構なんでもそうなんだけど Intermediate くらいのレベルになると Advanced を目指す前に飽きてしまいがちなんだけどたぶん来年も続けるかな。たぶん。
普段はとある Slack で進捗とかを共有しながらやっててるんだがソロでやってたら絶対もうやめてる。そこに @sugyanもいるんだけど彼はおれが始めるずっと前からずっと続けてるし、英語漬けで離脱してた間もずっと続けてた・・・マジすごい。あとなんかみんなホントに当たり前のようになんでも知っててすごいんだよなあ。来年35歳で定年だけどまだまだやっていかなければいけない。

番外編

12月は Advent of Code も毎日やってる。やってる人、 Private leaderboard でお待ちしておりますよ！

ちなみにこれの Day1 の問題は前述の Two Sum と発展の Three Sum で解くような問題でした。

*1:[2020/12/17 追記]: @fushiroyama さんは競技プログラミングを勧めてくれていた。 LeetCode 推しということではない。