50分で学ぶアルゴリズム / Algorithms in 50 minutes

E869120

November 30, 2021

Tweet Share

Transcript

1. 50分で学ぶアルゴリズム Algorithms in 50 minutes 東京大学 1 年 E869120 最終更新：2021

   年 12 月 1 日

2. 自己紹介 E869120 主な経歴について • 2002年生まれ • 2021年東京大学理科一類入学 • AtCoder 赤

   （max. 2950） • 国際情報オリンピック （IOI） ‘18, ’19, ’20 金メダル 2 最近の活動 • 「競プロ典型90問」作者 • 競プロの作問 （ARC117／ARC119） • Qiita にアルゴリズム関連記事を投稿 （1.7万 Contribution） • ?????

3. • アルゴリズムを学ぶと、いろいろな問題を（特にプログラミングを用いて）解決するた めの手段を身に付けることができます。 • 本スライドでは、有名なアルゴリズムを概観し、アルゴリズムに興味を持っていただく ことを目標にします。難しい数式などを使わないため、中学生レベルの数学的知識があ れば理解できる構成となっています。 はじめに 3 注意事項

   本スライドは、50 分程度の分量にまとめるため、具体的なアルゴリズムの説明が省略されている箇所も 多いです。より深く知りたい人は、スライドの最後に記されている「参考文献」やインターネットなど で調べてみてください。

4. 本スライドの構成 4 第 1 部 アルゴリズムとは 第 2 部 学年を当ててみよう

   第 3 部 代表的なアルゴリズム問題 第 4 部 コンピュータとアルゴリズム スライドの最初に、アルゴリズムとは 一体どういうものなのかについて解説 します。 アルゴリズムを使った身近な問題の例と して、学年を当てるゲームを紹介します。 線形探索法と二分探索法のアイデアを学 びます。 より良いアルゴリズムを設計すると解ける問題 はたくさんあります。第 3 部では身近な問題を 6 つピックアップし、アルゴリズムへの興味を 持っていただくことを目標にします。 最後に、計算の速いコンピュータでもより良い アルゴリズムが求められる理由と、アルゴリズ ムを学ぶ意義について記します。

5. 第 1 部 アルゴリズムとは

6. • アルゴリズムとは、問題を解く手順のことを指します。 • アルゴリズムには良し悪しがあり、素早く問題を解ける方が良いとされることが多いです。 • たとえば以下の問題を考えてみましょう。 6 アルゴリズムとは 問題 1

   から 100 までの整数をすべて足した値を計算してください。

7. • 単純な方法として、1 つずつ足していくことが考えられます。 • 小学校 3 年生で習う足し算のみを使っていますが、アルゴリズムは「問題を解く手順」 なので、これもれっきとしたアルゴリズムです。 • しかし、99

   回の足し算を行う必要があり、面倒です。（効率の悪いアルゴリズム） 7 アルゴリズムとは 1 3 6 10 15 21 28 36 45 55 + + + + + + + + + + 2 3 4 5 6 7 8 9 10 11 = = = = = = = = = = 3 6 10 15 21 28 36 45 55 66 66 78 91 105 120 136 153 171 190 210 + + + + + + + + + + 12 13 14 15 16 17 18 19 20 21 = = = = = = = = = = 78 91 105 120 136 153 171 190 210 231 231 253 276 300 325 351 378 406 435 465 + + + + + + + + + + 22 23 24 25 26 27 28 29 30 31 = = = = = = = = = = 253 276 300 325 351 378 406 435 465 496 496 528 561 595 630 666 703 741 780 820 + + + + + + + + + + 32 33 34 35 36 37 38 39 40 41 = = = = = = = = = = 528 561 595 630 666 703 741 780 820 861 861 903 946 990 1035 1081 1128 1176 1225 1275 + + + + + + + + + + 42 43 44 45 46 47 48 49 50 51 = = = = = = = = = = 903 946 990 1035 1081 1128 1176 1225 1275 1326 4186 4278 4371 4465 4560 4656 4753 4851 4950 + + + + + + + + + 92 93 94 95 96 97 98 99 100 = = = = = = = = = 4278 4371 4465 4560 4656 4753 4851 4950 5050 …

8. • そこで、1 から 100 までの整数は「1+100」「2+99」「3+98」といったように、和が 101 となる 50 個のペアに分割することができます。 •

   答えは 101 × 50 = 5050 です。 • たったの 1 回で計算できました。（効率の良いアルゴリズム） 8 アルゴリズムとは 1 2 3 4 99 100 1 100 2 99 51 50 … 98 5 6 7 8 … 101 × 50 = 5050 … 和が 101 … 和が 101 … 和が 101

9. • このように、アルゴリズムを変えてみるだけで、大幅に効率が良くなることがあります。 • 今回の場合は 99 回対 1 回ですが、1 から 1000

   までの整数をすべて足す問題では 999 回対 1 回となり、さらに差が広がります。 9 アルゴリズムとは 1 3 6 10 15 21 28 36 45 55 + + + + + + + + + + 2 3 4 5 6 7 8 9 10 11 = = = = = = = = = = 3 6 10 15 21 28 36 45 55 66 66 78 91 105 120 136 153 171 4950 + + + + + + + + + 12 13 14 15 16 17 18 19 : 100 = = = = = = = = = 78 91 105 120 136 153 171 190 5050 アルゴリズム 1 アルゴリズム 2 101 × 50 = 5050 計算回数 99回 計算回数 1回

10. • アルゴリズムは、問題を解くための手順のことです。 • 少しアルゴリズムを変更するだけで、問題を解くのにかかる時間が大幅に短縮されるこ とがあります。 • 第 2 部・第 3

    部では、アルゴリズムが使える身近な問題の例を紹介します。 10 第 1 部のまとめ

11. 学年を当ててみよう 第 2 部

12. • アルゴリズムは、実はとても身近にあるものです。 • 例として、以下の問題を考えてみましょう。 12 学年当てゲームを解こう 問題（学年当てゲーム） サクラさんは、大学 1 年・2

    年・3 年・4 年のいずれかです。 Yes/No で答えられる質問を何回か行うことで、彼女の学年を特定して ください。 ただし、失礼のないようにするため、質問回数は少ない方が良いです。

13. • 単純な方法として、「1 年生ですか？」「2 年生ですか？」のように順番に質問してい くことが考えられます。 • このような方法を線形探索法といいます。 • しかし、もし 4

    年生だった場合は 4 回の質問を必要とし、やや失礼です。 13 学年当てゲーム：単純な方法 1 年生 ですか？ 2 年生 ですか？ 3 年生 ですか？ 4 年生 ですか？ 1 年生 2 年生 3 年生 4 年生 Yes Yes Yes Yes No No No

14. • そこで、最初に「2 年生以下ですか？」という質問をすることを考えます。 • 真ん中で区切る質問をするというアイデアです。 14 学年当てゲーム：改良した方法 1年 生 2年

    生 3年 生 4年 生 1年 生 2年 生 3年 生 4年 生 1年 生 2年 生 3年 生 4年 生 Yes No 2 年生以下 ですか？

15. • Yes だった場合は「1 年生以下ですか？」という質問をすると 1 回で当てられます。 • No だった場合は「3 年生以下ですか？」という質問をすると

    1 回で当てられます。 • 合計質問回数は 2 回です。なお、このようなアルゴリズムは二分探索法といいます。 15 学年当てゲーム：改良した方法 1年 生 2年 生 3年 生 4年 生 1年 生 2年 生 3年 生 4年 生 1年 生 2年 生 3年 生 4年 生 1年 生 2年 生 3年 生 4年 生 1年 生 2年 生 3年 生 4年 生 1年 生 2年 生 3年 生 4年 生 1年 生 2年 生 3年 生 4年 生 Yes No Yes No Yes No

16. • 次に、ルールを少し変えた学年当てゲームを考えましょう。 • 選択肢が 4 つから 8 つに増えました。 16 学年当てゲームの拡張

    問題（学年当てゲーム） リエさんは、小学校 1 年から中学校 2 年までのいずれかです（それぞ れ 1 年生、2 年生、…、8 年生とします） Yes/No で答えられる質問を何回か行うことで、彼女の学年を特定して ください。

17. • これも単純な方法として 1 つずつ調べることが考えられます • しかし、8 年生の場合は 8 回の質問が必要です。 •

    このままではリエさんに失礼です。 17 学年当てゲームの拡張：単純な方法 1年生 か？ 1 年生 Yes No 2年生 か？ 3年生 か？ 4年生 か？ 5年生 か？ 6年生 か？ 7年生 か？ 8年生 か？ 2 年生 Yes 3 年生 Yes 4 年生 5 年生 6 年生 7 年生 8 年生 Yes Yes Yes Yes Yes No No No No No No

18. • そこで、いま考えられる選択肢の真 ん中で区切る質問をすることを考え ましょう。 • そうすると、1 回の質問で選択肢が 8 → 4

    → 2 → 1 と半分ずつに減り ます。 • 質問回数は 3 回です。 18 学年当てゲームの拡張：改良した方法 1年生 2年生 3年生 4年生 5年生 6年生 7年生 8年生 4 年生以下か？

19. • そこで、いま考えられる選択肢の真 ん中で区切る質問をすることを考え ましょう。 • そうすると、1 回の質問で選択肢が 8 → 4

    → 2 → 1 と半分ずつに減り ます。 • 質問回数は 3 回です。 19 学年当てゲームの拡張：改良した方法 1年生 2年生 3年生 4年生 5年生 6年生 7年生 8年生 1年生 2年生 3年生 4年生 5年生 6年生 7年生 8年生 4 年生以下か？ 6 年生以下か？

20. • そこで、いま考えられる選択肢の真 ん中で区切る質問をすることを考え ましょう。 • そうすると、1 回の質問で選択肢が 8 → 4

    → 2 → 1 と半分ずつに減り ます。 • 質問回数は 3 回です。 20 学年当てゲームの拡張：改良した方法 1年生 2年生 3年生 4年生 5年生 6年生 7年生 8年生 1年生 2年生 3年生 4年生 5年生 6年生 7年生 8年生 1年生 2年生 3年生 4年生 5年生 6年生 7年生 8年生 4 年生以下か？ 6 年生以下か？ 5 年生以下か？

21. • そこで、いま考えられる選択肢の真 ん中で区切る質問をすることを考え ましょう。 • そうすると、1 回の質問で選択肢が 8 → 4

    → 2 → 1 と半分ずつに減り ます。 • 質問回数は 3 回です。 21 学年当てゲームの拡張：改良した方法 1年生 2年生 3年生 4年生 5年生 6年生 7年生 8年生 1年生 2年生 3年生 4年生 5年生 6年生 7年生 8年生 1年生 2年生 3年生 4年生 5年生 6年生 7年生 8年生 1年生 2年生 3年生 4年生 5年生 6年生 7年生 8年生 4 年生以下か？ 6 年生以下か？ 5 年生以下か？

22. • 学年当てゲームでは、以下の 2 つのアルゴリズムを紹介しました。 • 線形探索法：「1 年生ですか？」「2 年生ですか？」と 1 つずつ聞いていく

    • 二分探索法：いま考えられる選択肢の真ん中で区切る質問を繰り返す • この 2 つの方法は、質問回数（最悪ケース）が大幅に異なります。 • 選択肢が 4 つのとき：4 回 vs. 2 回 • 選択肢が 8 つのとき：8 回 vs. 3 回 22 第 2 部のまとめ（1/2）

23. • このアイデアは、辞書で単語を探すときにも使うことができます。 • たとえば a → aardbark → abacus →

    … と 1 つずつ調べると時間がかかり ます。 • そこで「真ん中を見て、それより前か後かを調べること」を繰り返すと、目 的の単語を効率よく探すことができます。400 ページの辞書の場合、最初は 200 ページ目と比べれば良いです。 23 第 2 部のまとめ（2/2）

24. 代表的なアルゴリズム問題 第 3 部

25. 25 第 3 部の内容について • 第 3 部では、アルゴリズムが使える 6 つの代表的な問題を紹介します。

    • 問題はすべて生活と関わるものになっています。どれか 1 つでも興味を持っていただけ ると、大変嬉しく思います。 • スライド枚数の都合上、詳しいアルゴリズムの説明は省略しています。興味のある人は、 本スライド最後に掲載している参考文献をご覧ください。

26. • 単純な方法として、以下が考えられます。 a. 一番大きい値を探す。 b. a. 以外で一番大きい値を探す。 c. a./b. 以外で一番大きい値を探す。

    d. 以下同様。 26 問題例 (1)：ソート いくつかの値を指定された順序でソート（整 列）する方法を考えてください。 たとえば、期末試験の成績が与えられたとき、 高い順に並び替えてみてください。 氏名 点数 佐藤 83 田中 100 中村 1 渡辺 55 氏名 点数 田中 100 佐藤 83 渡辺 55 中村 1 • このアルゴリズムは選択ソートといいま すが、クイックソートやマージソートを 使うと、さらに効率よく解けます。

27. • この問題を解く方法として、ダイクスト ラ法などが知られています。 • 迷路のようにすべての長さ（110kmなど の値）が同じ場合、幅優先探索などが適 しています。 27 問題例 (2)：最短経路問題

    以下のような地図が与えられるので、2 つの 都市間の最短距離を求めてください。 また、どのように移動すれば最短距離になる かを求めてください。 東京 大阪 名古屋 仙台 長野 300km 150km 250km 130km 110km 220km

28. • 実は、「いま見れる映画の中で上映終了 時刻が一番早いものを選ぶ」という方針 で選ぶと、最適であることが知られてい ます。 • このように、次の手（この場合は次の映 画）だけを考えて答えを出すアルゴリズ ムを貪欲法といいます。 28

    問題例 (3)：区間スケジューリング問題 今日はいくつかの映画が上映されます。最大 で何本の映画を見れるか、そしてそれを実現 する方法を求めてください。 ただし、同時に 2 つ以上の映画を見ることは できないものとします。 0 5 10 映画 1 映画 2 映画 4 映画 3 映画 5 映画 6

29. • 品物の数が少ない場合、すべての選び方 を調べること（全探索）が自然です。 • そうでない場合は、動的計画法（漸化式 を立てて問題を解く方法）を使うと効率 的です。 29 問題例 (4)：ナップザック問題

    コンビニにはいくつかの品物が売られていま す。500 円以内の買い物で、最大何 kcal を摂 取することができますか。 120円 217kcal 180円 368kcal 320円 661kcal 400円 107kcal 230円 436kcal 動的計画法のイメージ（興味のある人は参考文献を参照）

30. • 人間には簡単（直感的に解ける問題）で すが、プログラムを書いてコンピュータ に解かせるのは難しいタイプの問題です。 • たとえば k-means 法などのアルゴリズム が知られています。 30

    問題例 (5)：クラスタリング いくつかのデータが与えられるので、これを 適切にグループ分けしてください。 たとえば、以下のような家の分布が与えられ るとき、できるだけ自然になるように 3 つの 地区に分割してください。

31. • 「2 は素数か？」「3 は素数か？」と 1 つずつ調べると、少し時間がかかってし まいます。 • 以下のアルゴリズムを使うと、効率よく 問題が解けます。エラトステネスのふる

    いと呼ばれています。 • 2 以外の 2 の倍数を消す。 • 3 以外の 3 の倍数を消す。 • 5 以外の 5 の倍数を消す。 • 7 以外の 7 の倍数を消す。（以下略） 31 問題例 (6)：素数の列挙 ある一定（たとえば 50）以下の素数を列挙し てください。 ただし、素数は 1 と自分自身以外で割り切れ ない数のことを指します。 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

32. 32 第 3 部のまとめ • 第 3 部では、以下の 6 つの代表的な問題を紹介しました。詳しくは、参考文献で調べて

    みてください。 • なお、その他にもいろいろな有名問題があります。 • 編集距離、最小全域木問題、最大フロー問題、最大マッチング問題、線形計画問題、最近点対 問題、素数判定、最大公約数の計算、多倍長整数の計算、etc… • ソート • 最短経路問題 • 区間スケジューリング問題 • ナップザック問題 • クラスタリング • 素数の列挙

33. コンピュータとアルゴリズム 第 4 部

34. 34 アルゴリズムは役に立つのか？ Q. 計算が速いコンピュータがあっても アルゴリズムの改善は必要か？

35. • コンピュータは、どんなに大量の計算でも一瞬でこなすイメージがあるかもしれません。 • しかし、コンピュータにも限界があり、標準的な家庭用 PC の場合は、素直なプログラ ムだと 1 秒に約 10

    億回しか四則演算を行うことができません。家庭用 PC を使っても 無理な例として、以下の問題を考えましょう。 35 コンピュータとアルゴリズム 問題（第 3 部の 4 問目） 以下の 60 個の商品がコンビニに売られています。500 円以内で最大何 kcal 得られますか？ 商品1 商品2 商品3 … 商品60 値段 110円 180円 230円 … 90円 カロリー 217kcal 368kcal 436kcal … 195kcal

36. • 単純な解法として、全部の選び方を試す方法（全探索）が考えられます。 • しかし、商品の数が 1 個増えると、調べるべきパターンの数が 2 倍になります。 36 コンピュータとアルゴリズム

    商品 1 個 品物 1 品物 1 2 通り

37. • 単純な解法として、全部の選び方を試す方法（全探索）が考えられます。 • しかし、商品の数が 1 個増えると、調べるべきパターンの数が 2 倍になります。 37 コンピュータとアルゴリズム

    商品 1 個 商品 2 個 品物 1 品物 1 品物 1 品物 2 品物 1 品物 2 品物 1 品物 2 品物 1 品物 2 2 通り 4 通り

38. • 単純な解法として、全部の選び方を試す方法（全探索）が考えられます。 • しかし、商品の数が 1 個増えると、調べるべきパターンの数が 2 倍になります。 38 コンピュータとアルゴリズム

    商品 1 個 商品 2 個 商品 3 個 品物 1 品物 1 品物 1 品物 2 品物 1 品物 2 品物 1 品物 2 品物 1 品物 2 品物 1 品物 2 品物 1 品物 2 品物 1 品物 2 品物 1 品物 2 品物 3 品物 3 品物 3 品物 3 品物 1 品物 2 品物 1 品物 2 品物 1 品物 2 品物 1 品物 2 品物 3 品物 3 品物 3 品物 3 2 通り 4 通り 8 通り

39. • そして商品が 60 個となると、260 通り（約 115 京通り）を調べることになります。 • 人間はもちろん、家庭用 PC

    でも全部調べるの は難しいです。 • このような問題を解くためには、より良いアル ゴリズムを思いつく必要があります。（例えば 今回の場合は動的計画法が使えます） 39 コンピュータとアルゴリズム 21 = 22 = 23 = 24 = 25 = 26 = 27 = : 230 = : 260 = 2 4 8 16 32 64 128 : 1,073,741,824 : 1,152,921,504,606,846,976

40. 40 アルゴリズムを学ぶ意義 では、アルゴリズムを学ぶと どんなことが起こるのでしょうか。

41. 41 アルゴリズムを学ぶ意義 1 点目 2 点目 3 点目 解法の選択肢が広がる 計算量の感覚が身につく

    論理的思考力が身につく O(log N) O(N) O(N2) O(2N)

42. 42 アルゴリズムを学ぶ意義 1 点目 2 点目 3 点目 解法の選択肢が広がる 計算量の感覚が身につく

    論理的思考力が身につく O(log N) O(N) O(N2) O(2N) • 世の中の多くの問題は、いくつかの「典型的なアル ゴリズム」を応用することで解けます。 • したがって、アルゴリズム学習により、プログラミ ングを用いた問題解決が得意になるでしょう。

43. 43 アルゴリズムを学ぶ意義 1 点目 2 点目 3 点目 解法の選択肢が広がる 計算量の感覚が身につく

    論理的思考力が身につく O(log N) O(N) O(N2) O(2N) • アルゴリズムを知ると、どこ かで「計算量」を学びます。 • 計算量を知ると実行時間の感 覚が身につくため、実行が終 わらないプログラムを書く失 敗が減ります。

44. 44 アルゴリズムを学ぶ意義 1 点目 2 点目 3 点目 解法の選択肢が広がる 計算量の感覚が身につく

    論理的思考力が身につく O(log N) O(N) O(N2) O(2N) • アルゴリズムを勉強すると、複雑なものをシンプル に整理する能力が身につきます。 • そのため、以下のような副次的効果も期待できます。 • プログラムを書く速度が上がる。 • 物事の原因を突き止める力が上がる。 • 数学の問題が解けるようになる。

45. • アルゴリズムを学ぶ方法はさまざまですが、実践 的に学びたい場合は問題を解くことをおすすめし ます。 • アルゴリズムの問題を無料で解けるサービスとし て、AtCoder やアルゴ式などが有名です。 • 競争が好きな人は、競技プログラミングに参加し

    ても良いかもしれません。 45 アルゴリズムを学ぶ方法 https://atcoder.jp/ https://algo-method.com/

46. スライドのまとめ

47. • アルゴリズムは「問題を解く手順」のことです。 • アルゴリズムによって、問題を解く効率が大きく異なる場合があります。 • 第 2 部では「学年当てゲーム」を紹介しました。 • 線形探索法と二分探索法で、質問回数が大幅に異なることを解説しました。

    • アルゴリズムが使える問題は、ほかにもたくさんあります。 • 第 3 部では、ソート・最短経路問題・区間スケジューリング問題・ナップザック問題・クラ スタリング・素数の列挙の 6 つを取り上げました。 • ほかにも多数の有名問題があります。参考文献などで調べてみてください。 47 50 分のまとめ（1/2）

48. • コンピュータであっても、どんなに大量の計算処理を一瞬で行えるとは限りません。 • したがって、さまざまなアルゴリズムを知り、より少ない計算処理で問題を解決するス キルを身に付けることが大切です。 • 皆さんも、たのしいアルゴリズムの世界に入っていきましょう。 48 50 分のまとめ（2/2）

49. 1. T.コルメン、R.リベスト、C.シュタイン、C.ライザーソン：「アルゴリズムイントロダクション 第3版総合版」、近 代科学社（2013） 2. 大槻兼資：「問題解決力を鍛える！アルゴリズムとデータ構造」、講談社（2020） 3. 渡部有隆：「プログラミングコンテスト攻略のための アルゴリズムとデータ構造」、マイナビ出版（2015） 4.

    石田保輝、宮崎修一：「アルゴリズム図鑑 絵で見てわかる 26 のアルゴリズム」、翔泳社（2017） 5. 梅谷俊治：「60分で学ぶ数理最適化」（https://speakerdeck.com/umepon/mathematical-optimization-in-60- minutes） 6. AtCoder（https://atcoder.jp/） 7. 実生活に学ぶアルゴリズム【第1回：セブンイレブンでは 500 円で何カロリー得られるか？】 （https://qiita.com/e869120/items/5d9d0fcbb6dc7dbf87f9） 8. いらすとやの画像を利用 49 参考文献