思ったより難しいDFSアルゴリズムを、
頻出問題を通して学びましょう 💡
こんな悩みを抱えたことはありませんか?
🤔 この問題をDFSで解くべきだと、どうすれば判断できますか?
🥲 DFSだと分かっていても毎回途方に暮れてしまいます。共通する解法はないのでしょうか?
🫠 再帰関数が頭の中でイメージできません。どう整理すれば理解できるでしょうか?
未経験者向け8年目の開発者による
DFSアルゴリズム講座 🪢
DFS(Depth First Search)はグラフ全体を探索する方法の一つで、「深さ」を優先して探索するアルゴリズムです。
本講義はDFSアルゴリズムの入門講義で、最も頻出する問題を解きながら、DFSの問題を実際に体験することを目標としています。核心となる概念を非常に短くまとめた後、各タイプに該当する問題を解きながら、「この問題はDFSの問題なんだ」と気づける視点を身につけ、すべての問題に通じる核心を扱って DFSを攻略するために作られた講義です :D
DFSアルゴリズムを勉強したものの、よく理解できなかったり、自力で解法を思いつくのが難しかったりする方にとって、この講義は大きな助けになるでしょう。文系出身の現役8年目の開発者が、非専攻者のために制作した講義ですので、どの講義よりも分かりやすいとお約束します。以下は、私が運営しているYouTubeチャンネルに寄せられたコメントです。
このような方におすすめです 🙋
Javaの基本文法はわかるけれど、コーディングテストの準備を初めてする方
DFS問題を一人で解いてみたものの、いまいち感覚がつかめない方々
理論講義を受けても、いざ問題を見ると途方に暮れてしまう方々
講義の特徴 ✨
#1.
DFS問題だという
ヒントを整理します。
講義をしていて受講生の方々がよくおっしゃっていたのは、"DFSで解くべきだとは知りませんでした"ということです。そこで問題文を一緒に読みながら、"この問題はどんなキーワードを見てDFSを思い浮かべるべきだったのか?"という問いに答えます。
#2.
プログラムの進行に伴って
変化するデータ構造を
お見せします。
この講義は、簡単な図で説明を済ませたり、コードを打ちながら口頭だけで説明したりする講義ではありません!
データ構造をどのようなサイズで定義し、どのように初期化すべきかから、段階ごとに値がどのように変化して答えを導き出せるのかまで、アニメーションを活用してお見せします。
#3.
問題を貫く
核心をまとめます。
問題ごとに実装の違いはありますが、DFSアルゴリズムを求める問題に共通する点は変わりません。講義を通してDFS問題を解くための核心が何かをタイプ別に整理し、すべての問題で要点をしっかり確認しながらまとめる時間を設けます。
この過程を経ると、新しいDFS問題を見ても、どの部分が共通していて、どこが異なるのかを素早く判断し、DFS問題を自力で解けるようになります!
学習内容 📚
講義では、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)
想定質問 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
受講前の注意事項 📢
実習環境
- 私はWindows 11でVS Codeを使用してコードを作成しています。
- 受講生の皆さんは、どのOS/IDEをお使いでも構いません。
- ただし、ご自身でコードを記述し、Build/Debugできる環境をあらかじめ用意してから受講すると、スムーズに講義を受けられます。
- 細かな設定が面倒だったり難しかったりする方には、Eclipseの使用をお勧めします。(https://www.eclipse.org/downloads/)
学習資料
前提知識および注意事項
- Javaの基本文法はご理解いただいているものとして、講義を進めます。
- DFSを一度でも経験したことのある方なら、よりスムーズに理解できると思いますが、DFSを知らない方のための基本的な説明も簡単にありますので、ご安心ください!
知識共有者の紹介 ✒️
こんにちは:) 私は経営・経済を専攻した文系学生としてスタートし、現在は大手企業で8年目の開発者として働いている「開発者として就職する」です。8年前に初めて開発を学んだ頃を思い返すと、とても途方に暮れ、苦労していたように思いますが、自分なりの戦略や方法で整理し、問題を解いていくうちに、少し早く、よりうまく就職できたように思います。特にコーディングテストをとても難しく感じている未経験者の方であれば、未経験者が教えるこの講座を一度受講してみると、きっと簡単に理解できるでしょう。どうぞよろしくお願いします! :)
経歴/ポートフォリオ/個人動画