アルゴリズム

アルゴリズムを学ぼう

川中真耶、杵渕朋彦、椎名俊輔
アスキー・メディアワークス

はじめに

第0講 はじまり

  • 明日木大学、入学式!
  • キャラクター紹介
    • 伯方涼子(はかた りょうこ)
    • 日比野萌来(ひびの めぐる)
    • 澤戸うい(さわど うい)
    • 倉科莉紗(くらしな りさ)

第1講 アルゴリズムと計算量

  1. アルゴリズムをはじめよう!
  2. アルゴリズムとは?
  3. アルゴリズムを学ぶことの重要性
  4. まずは肩慣らしの問題
    • 二分探索
  5. 計算量
  6. 計算量の表し方
  7. 計算量の求め方
  8. ようこそ!技育部へ!

第2講 データ構造 - 初級編

  1. アルゴリズム温泉!
  2. 基礎的なデータ構造
  3. 配列(Array)とベクター(Vector)
    1. ベクター(Vector)
    2. ベクターの挙動
      1. 戦略1:10だけ大きくした配列を作る戦略
      2. 戦略2:2倍の大きさの配列を作る場合
      3. 戦略の比較
      4. 末尾以外に要素を追加する場合
    3. 配列・ベクター中の検索
  4. 連結リスト(Linked List)
    1. 連結リストの表し方
    2. 連結リストへの要素の挿入
  5. スタック、キュー
    1. 二分木(Binary Tree)
    2. 二分探索木
      • 二分探索木の検索
      • 二分探索木への挿入
  6. 連なる花火はアルゴリズムの味

第3講 ソート

  1. エアコン求めて三千里
  2. 並び替えのアルゴリズム
  3. いろいろなソート
    • バブルソート
    • 選択ソート
    • 挿入ソート
  4. マージソート
    • 分割統治法
  5. クイックソート
    • ピボット選択
  6. ヒープソート
    • ヒープ
  7. 炎天下の延長戦・・・?

第5章 全探索
みんなが楽しいパーティ

  • 問題の解説
  • 応用技
  • 数学的問題に対する全探索

暗号文

  • 問題の解説
  • 応用技

おもしろい数学

  • 問題の解説
  • 応用技
  • さまざまな種類の全探索

山本山

  • 問題の解説
  • 強固なイメージをもつための「グラフ」

友達の数

  • 問題の解説

さまざまなタイプの全探索

  • さなざなばタイプの探索
  • 深さ優先探索と幅優先探索
  • たいていの物事はグラフに変換できる
  • ダイクストラ法
  • 枝刈り
  • 探索の実装
  • 深さ優先探索のイメージ
  • 幅優先探索のイメージ
  • データ構造
  • 再帰関数
  • 深さ優先探索の実装
  • 幅優先探索の実装
  • 深さ優先探索と幅優先探索の違い

壊れたロボット

  • 問題の解説

迷路づくり名人

  • 問題の解説
  • bit全探索

ナンバーマジック

  • 問題の解説1
  • 問題の解説2
  • 問題の解説3

中級編

第6章 計算量
計算時間、メモリ使用量を予測するために

  • プログラム実行に関する制約事項と計算量
  • 時間計算量
  • 計算量の計算が難しいケース
  • 計算量の大きい関数を呼びだしている場合
  • 空間計算量

第7章 動的計画法・メモ化
動的計画法の基本

  • 経路の探索
  • 探索を使った解法
  • 数学的解法
  • メモ化再帰を使った解法
  • 動的計画法らしい解法
  • ナップザック問題
  • 探索を使った解法
  • メモ化再帰を使った解法
  • 動的計画法を使った解法
  • 動的計画法

会社の組織と給与

  • 問題の解説(探索)
  • 問題の解説(動的計画法)

仲の悪い隣人たち

  • 問題の解説(動的計画法)

キングとナイト

  • 問題の解説(動的計画法)

ビジネス握手

  • 問題の解説

第8章 探索範囲を狭めるアルゴリズム
カラフルボックス&ボール

  • 問題の解説

貪欲法

  • 動的計画法は万能なのか
  • なじみ深いようで意外と難しい「貪欲法」

株式投資シミュレーション

  • 問題の解説

バッチシステム

  • 問題の解説

自動車ローン

  • 問題の解説

数学的アプローチ円の国家群

  • 問題の解説

ハミルトン路

  • 問題の解説

上級編

第9章 応用問題
バイナリフリップ

  • 問題の解説1
  • 問題の解説2
  • 問題の解説3
  • 問題の解説4
  • 問題の解説5
  • この問題のまとめ

カントールの塵

  • 問題の解説
  • この問題のまとめ

Not Two

  • 問題の解説
  • この問題のまとめ

棒の切断

  • 問題の解説
  • 二分探索の終了条件について
  • この問題のまとめ

無限数列

  • 問題の解説1
  • 問題の解説2
  • 問題の解説3
  • 問題の解説4
  • 問題の解説5
  • 問題の解説6
  • この問題のまとめ

床板

  • 問題の解説1
  • 問題の解説2
  • この問題のまとめ

第10章 整列
連結判定

  • 単純な探索を利用した連結判定
  • Union-Find

有向グラフと無向グラフ重み付きグラフ

  • 重み付きグラフ
  • 重み付きグラフの最短経路問題

ダイクストラ法

  • ダイクストラ法
  • 優先度付きキュー
  • これまで説明した動的計画法とダイクストラ法の大きな違い

最小全域木

  • 最小全域木
  • 愚直な全探索
  • プリム法
  • クラスカル法

辺にさまざまな情報があるグラフ

  • 辺にさまざまな情報があるグラフ
  • 頂点を増やすことによって簡単に表せるグラフ

第11章 数学問題対策
素数

  • 素数
  • 素数判定
  • O√nの方針
  • その他の素数判定法
  • 素数列挙

最大公約数、最小公倍数

  • 最大公約数、最小公倍数
  • 愚直な実装
  • ユークリッドの互除法
  • 拡張ユークリッドの互除法

索引
TopCoder問題一覧
カテゴリ別問題一覧
難易度別問題一覧