思ったより難しいDFSアルゴリズム?
頻出問題のパターンで効率よく学習しましょう!
このようなお悩みはありませんか?
🤔
この問題をDFSで解くべきだと、どうすれば分かりますか?
🥲
DFSだと分かっても、毎回途方に暮れてしまいます。共通する解法はないのでしょうか?
😥
再帰関数が頭の中でイメージできません。どのように整理すれば理解できるでしょうか?
非専攻者のための、8年目の開発者による
DFSアルゴリズム講義 🪢
DFS(Depth First Search)
グラフ全体を探索する方法の一つで、「深さ」を優先して探索するアルゴリズムです。
本講義はDFSアルゴリズムの入門講義で、最も頻出する問題を解きながら、DFS問題を実際に体験することを目標としています。核心となる概念を非常に短く整理した後、それぞれのタイプに該当する問題を解きながら、「この問題はDFS問題なんだ」と気づける視野を養い、すべての問題に共通する本質を扱うことでDFSを完全にマスターするために作った講義です :D
私が運営するYouTubeチャンネルに寄せられたコメントです。
DFSアルゴリズムを学んだけれど、よく理解できなかったり、自力で解法を思いつくのが難しかったりする方にとって、この講座は大いに役立つでしょう。文系出身で8年目の現役開発者が、非専攻者のために制作した講座ですので、どの講座よりもわかりやすいことをお約束します。
このような方におすすめです 🙋
Pythonの基本文法は知っているものの、コーディングテストの準備を初めてする方
DFS問題を一人で解いてみたものの、いまひとつコツがつかめない方
理論講義を受けても、いざ問題を見ると途方に暮れてしまう方
講義の特徴 ✨
1. DFS問題であるというヒントを整理します。
これまで講義をしてきて、受講生の皆さんから特によく聞いたのは、"DFSで解くべきだとは知りませんでした"という言葉でした。
そのため講義では、提示された問題をまず一緒に読みながら、「この問題では、どんなキーワードを見てDFSを思い浮かべるべきだったのだろうか?」という問いへの答えを探します。
2. プログラムの進行に伴って変化するデータ構造をお見せします。
この講義は、簡単な図で説明を済ませたり、コードを打ちながら口頭だけで説明したりする講義ではありません!データ構造をどのような大きさで定義し、どのように初期化すべきかというところから、段階ごとに値がどのように変化して答えを導き出せるのかまで、アニメーションを活用してわかりやすくお見せします。
3. 問題を貫く核心を整理します
問題ごとに実装の違いはありますが、DFSアルゴリズムを要求する問題の共通点は変わりません。講義を通して、DFSの問題をうまく解くためのポイントは何かをタイプ別に整理し、すべての問題で要点をしっかり固めながら整理する時間を設けます。
この過程を経ると、新しいDFS問題を見ても、どの部分が共通していて、どこが異なるのかを素早く判断し、DFS問題を自力で解けるようになります!
📚 厳選した12問の問題タイプを選び、整理します。
講義では、Baekjoonに登録されたDFS入門向け問題(シルバー4~2級)の中から、最も多くの人が解き、難しいと感じた問題を12問厳選しました。さらに、これらを2つの詳細なタイプに分類し、各タイプに必要な核心概念を整理します。詳しいタイプと問題は次のとおりです。
タイプ1.連結成分を探すタイプ
- ウイルス(2606) (無料公開)
- 連結成分の数(11724)
- アルゴリズム講座 - 深さ優先探索 1(24479)
- アルゴリズム授業 - 深さ優先探索 2(24480)
- DFSとBFS(1260)
- 親等計算(2644)
- 木の親を探す(11725)
タイプ2. 同じ種類を見つける
- 有機農キャベツ(1012)(無料公開)
- 侵透(13565)
- 島の数(4963)
- 床飾り(1388)
- ジャンプ王ゼリ(Small) (16173)
途方に暮れるお気持ちがわかるからこそ
より簡単な道を指し示します 🚩
こんにちは:) 経営・経済を専攻した文系学生としてスタートし、現在は8年目の大手企業の開発者として働いている、開発者として就職することです。
- 大手企業で8年目の開発者
- 開発者就職関連のコンテンツを扱うYouTubeクリエイター( https://www.youtube.com/@gaebal )
- プログラマースプラットフォーム C++入門講座講師
- エリスプラットフォームのアルゴリズムクイズチップのライブセッションおよび解説集の制作担当者(Python/Java/C++)
8年前に初めて開発を学んだ頃を思い返すと、本当に先が見えず大変だったように思いますが、自分なりの戦略や方法で整理し、問題を解いていくうちに、少し早く、よりうまく就職できたように思います。
特にコーディングテストをとても難しく感じている未経験者の方なら、未経験者が教えるこの講義を一度受講してみれば、きっと簡単に理解できると思います。よろしくお願いします! :)
一緒に見るとよい講義 📺
Q&A 💬
Q. 講義はなぜこんなに短いのですか?
問題をたくさん追加して1つの大きな講義にし、その分価格を上げるほうが、講師である私にとって最も有利です。しかし、段階ごとに必要な説明や内容は異なりますし、何より私の購読者・受講生のほとんどが収入のない就職活動中の方々であることを考慮すると、できるだけ小さな単位に分けて価格を下げるほうがよいと思い、他の講義と比べて短くコンパクトな構成にしました。
Q. 問題数があまり多くないのですが、DFSを理解できますか?
上記の理由から講義を小さく分けることにしました。そのため、入門講義に続いて、ゴールド等級やプラチナ等級を扱う応用講義と上級講義も準備しています。ですので、「この講義だけ受講すれば、すべてのDFS問題を解ける!」と言うのは、受講生を欺く行為だと思います。(結局、勉強には自分で悩み、考える時間が不可欠ですからね)。ただ、私がお約束できるのは、この講義ほど簡単にDFSを学び始められる講義はないということと、この講義を終えれば、DFSを一人でも勉強し、理解できるようになるということです。そのため、単なる解説動画ではなく、魚の釣り方を学びたい方に、自信を持っておすすめできます。
Q. YouTubeにも解説がありますが、同じではありませんか?
大きな流れは同じですが、YouTubeの特性上、動画を長くするわけにはいかないため、ほとんどの補足説明を省略しました。そのため、多くの購読者の方々からコメントで質問をいただいたり、物足りなさを表す声が寄せられたりもしました。こうした物足りなさを解消するため、オンライン講座を制作することになりました。
私が知っていることを、最も簡単かつ簡潔に理解していただけるよう内容をまとめました。実際、ウイルスや有機栽培の白菜の問題については、この講座で無料公開されているほか、YouTubeにも掲載されています。YouTubeで簡単にまとめた内容が、この講座ではどのようにより詳しく説明されているのか、実際にご覧いただくと判断しやすいかと思いますので、ぜひご参考ください!
Q. 質問をした場合、回答までどのくらいかかりますか?
特別なことがなければ、勤務時間を基準に24時間以内に回答し、どんなに遅くても72時間以内にはお答えします。私自身もオンライン講義をたくさん受講してきて感じたことですが、講師が早く回答してくれるほど勉強のペースも上がり、オフライン講義より効果的な場合もあると思っています。ただ、講師の回答が遅くなると、その分勉強に対するモチベーションも下がってしまうこともよくわかっているので、毎日コメントを確認し、質問にお答えしています!
Q. してはいけない質問もありますか?
動画ごとにお伝えしていますが、どんな質問でもいつでも歓迎です。多くの場合、自分が疑問に思ったことは、ほかの受講生も疑問に思っているはずだからです。ただし、いくつかルールを決めておくと、皆さんにとって有益な質問になると思います。
1. 質問に関連する動画に質問を残してください!
- 動画ごとに扱っている内容が異なるため、お互いに役立つよう、該当する動画に質問を投稿していただけると、皆にとって有益な質問になると思います。
2. 人生相談/就職関連の質問などは、メンタリングセクションからお問い合わせください。
- このような質問は、それぞれ置かれている状況によって回答が異なる可能性があるため、より個別に質問していただければ、私も正確なガイドをご提供できます。公開質問でお答えしようとすると曖昧な回答しかできないため、このような内容はメンタリングセクションに残していただければ、誠心誠意お答えいたします。
- メンタリングリンク:https://inf.run/kCsp
3. "なぜできないの?"といった質問もメンタリングセクションを通じてお問い合わせください。
- あまりにももどかしい気持ちから、コード全体をコピー&ペーストして見てほしいとお願いされる場合があります。このような質問は他の方の役に立ちにくく、質問された方ごとに置かれている状況も異なるため、メンタリングセクションを通じて個別にお問い合わせいただければ、どこが間違っていて、なぜ間違っているのか、どのように修正すればよいのかまでご説明しています!
- メンタリングリンク:https://inf.run/kCsp
- 実習環境としては、どのOS/IDEを使用しても構いません。私はWindows 11でVS Codeを使用してコードを書いています。
- ただし、あらかじめ自分でコードを記述し、Build/Debugできる環境を整えてから受講すると、スムーズに講義を受けられます。
- 講義で使用するPPTをPDF形式で提供いたします。
- Pythonの基本文法は理解しているものと仮定して講義を進めます。DFSを一度でも経験したことがある方ならよりスムーズですが、DFSを知らない方のための基本的な説明も簡単にありますので、ご安心ください!