computer-science-tutor

コンピュータサイエンス科目エキスパート

コンピュータサイエンスの学習、問題解決、ノート作成のための専門知識。

トピックの範囲

mindmap
  root((Computer Science))
    Algorithms
      Sorting
      Searching
      Graph Algorithms
      Dynamic Programming
    Data Structures
      Arrays & Lists
      Trees & Graphs
      Hash Tables
      Heaps & Queues
    Systems
      Operating Systems
      Networks
      Databases
    Theory
      Complexity
      Automata
      Computability

---

クイックリファレンスリンク

• アルゴリズムパターン: algorithms.md を参照
• データ構造: data-structures.md を参照
• Big-O 解析: big-o.md を参照

---

図のパターン

アルゴリズムのフローチャート

flowchart TB
    A[Start] --> B{Condition?}
    B -->|Yes| C[Process A]
    B -->|No| D[Process B]
    C --> E[End]
    D --> E

データ構造の可視化

graph TB
    subgraph "Binary Search Tree"
        A((8)) --> B((3))
        A --> C((10))
        B --> D((1))
        B --> E((6))
        C --> F((14))
    end

シーケンス図 (API/プロセス)

sequenceDiagram
    Client->>Server: Request
    Server->>Database: Query
    Database-->>Server: Results
    Server-->>Client: Response

---

問題解決のフレームワーク

アルゴリズム設計の手順

1. 理解 - 入力、出力、制約を明確にする
2. 例 - 2〜3 個の例を手作業で解いてみる
3. 力任せ法 - まず明白な O(n²) または O(n!) の解法から始める
4. 最適化 - パターン (二本指、スライディングウィンドウなど) を適用する
5. 実装 - クリーンでモジュール化されたコードを書く
6. テスト - エッジケース (空、単一要素、重複)

よく使うパターン

パターン	使用する場面	例
二本指	ソート済み配列、ペアの探索	Two Sum (ソート済み)
スライディングウィンドウ	連続する部分配列	最大和部分配列
ハッシュマップ	O(1) の検索が必要	Two Sum (未ソート)
BFS	最短経路 (重みなし)	迷路の解法
DFS	すべての経路の探索	順列
二分探索	ソート済みデータ、要素の探索	回転配列の探索
動的計画法	部分問題の重複	フィボナッチ、ナップサック

---

コードテンプレートのパターン

二分探索

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1  # Not found

BFS テンプレート

from collections import deque

def bfs(start, target):
    queue = deque([start])
    visited = {start}
    while queue:
        node = queue.popleft()
        if node == target:
            return True
        for neighbor in get_neighbors(node):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return False

DFS テンプレート

def dfs(node, visited):
    if node in visited:
        return
    visited.add(node)
    # Process node
    for neighbor in get_neighbors(node):
        dfs(neighbor, visited)

---

計算量クイックリファレンス

操作	配列	連結リスト	ハッシュテーブル	BST (平均)
アクセス	O(1)	O(n)	O(1)	O(log n)
検索	O(n)	O(n)	O(1)	O(log n)
挿入	O(n)	O(1)	O(1)	O(log n)
削除	O(n)	O(1)	O(1)	O(log n)