Algorithms and Data Structures
アルゴリズムとデータ構造 完全ガイド
1. イントロダクション
1.1 アルゴリズムとは何か
アルゴリズムとは、ある問題を解決するための手順を明確に定義した有限の命令列である。日常生活においても、料理のレシピや道順の説明など、アルゴリズム的な思考は随所に見られる。コンピュータサイエンスにおいては、データの処理・検索・ソート・最適化など、あらゆる計算処理の基盤となる概念である。
良いアルゴリズムの条件は以下の通りである。
- 正確性（Correctness）: すべての入力に対して正しい出力を返す
- 効率性（Efficiency）: 時間的・空間的リソースを最小限に抑える
- 有限性（Finiteness）: 有限のステップで必ず終了する
- 明確性（Definiteness）: 各ステップが曖昧さなく定義されている
1.2 データ構造とは何か
データ構造とは、データを効率的に格納・管理・アクセスするための体系的な方法である。アルゴリズムの効率はデータ構造の選択に大きく依存する。適切なデータ構造を選択することで、アルゴリズムの時間計算量を劇的に改善できる場合がある。
データ構造は大きく以下のように分類される。
| 分類 | 例 |
|---|---|
| 線形データ構造 | 配列、連結リスト、スタック、キュー |
| 非線形データ構造 | ツリー、グラフ |
| ハッシュベース | ハッシュテーブル、ハッシュマップ |
| 特殊構造 | トライ木、セグメント木、Union-Find |
1.3 計算量（Big-O記法）
アルゴリズムの効率を評価する上で最も重要な概念が計算量分析である。Big-O記法は、入力サイズ n に対するアルゴリズムの実行時間や使用メモリの増加率の上限を表す。
1.3.1 時間計算量の代表的なオーダー
| 記法 | 名称 | 例 |
|---|---|---|
| O(1) | 定数時間 | 配列のインデックスアクセス |
| O(log n) | 対数時間 | 二分探索 |
| O(n) | 線形時間 | 線形探索 |
| O(n log n) | 準線形時間 | マージソート、クイックソート（平均） |
| O(n^2) | 二乗時間 | バブルソート、選択ソート |
| O(n^3) | 三乗時間 | 行列の乗算（ナイーブ） |
| O(2^n) | 指数時間 | 部分集合の列挙 |
| O(n!) | 階乗時間 | 順列の全列挙 |
1.3.2 Big-O記法の数学的定義
f(n) = O(g(n)) とは、ある正の定数 c と n₀ が存在して、すべての n ≧ n₀ に対して f(n) ≦ c・g(n) が成り立つことを意味する。
直感的には、「入力サイズが十分に大きいとき、f(n) の増加率は g(n) の定数倍以下である」ということである。
1.3.3 計算量の計算例
# O(1) - 定数時間
def get_first(arr):
return arr[0]
# O(n) - 線形時間
def find_max(arr):
max_val = arr[0]
for x in arr: # n回のループ
if x > max_val:
max_val = x
return max_val
# O(n^2) - 二乗時間
def has_duplicate(arr):
n = len(arr)
for i in range(n): # n回
for j in range(i+1, n): # 最大n-1回
if arr[i] == arr[j]:
return True
return False
# O(log n) - 対数時間
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi: # 毎回半分に絞る → log n 回
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
1.3.4 空間計算量
時間計算量と同様に、アルゴリズムが使用するメモリ量も重要な指標である。
# 空間計算量 O(1) - 入力以外に追加メモリを使わない
def reverse_in_place(arr):
left, right = 0, len(arr) - 1
while left < right:
arr[left], arr[right] = arr[right], arr[left]
left += 1
right -= 1
# 空間計算量 O(n) - 入力と同じサイズのメモリが必要
def reverse_copy(arr):
return arr[::-1]
1.3.5 最良・平均・最悪計算量
アルゴリズムの計算量は入力によって異なる場合がある。
| ケース | 説明 | 例（クイックソート） |
|---|---|---|
| 最良ケース（Best Case） | 最も有利な入力 | O(n log n) |
| 平均ケース（Average Case） | 典型的な入力 | O(n log n) |
| 最悪ケース（Worst Case） | 最も不利な入力 | O(n^2) |
1.4 なぜアルゴリズムとデータ構造が重要か
パフォーマンスへの直接的影響
100万件のデータからある要素を検索するケースを考える。
- 線形探索 O(n): 最悪100万回の比較
- 二分探索 O(log n): 最大約20回の比較
この差は、システムの応答速度やスケーラビリティに直結する。
ソフトウェアエンジニアとしての必須知識
- 技術面接: FAANG（Google, Amazon, Meta等）をはじめとする多くの企業で、アルゴリズムとデータ構造の知識は面接の重要項目である
- システム設計: 適切なデータ構造の選択は、大規模システムの設計において不可欠である
- 問題解決能力: アルゴリズム的思考は、複雑な問題を分解して解決する能力を養う
- 競技プログラミング: AtCoder、Codeforces、LeetCode等の競技プログラミングでは必須のスキルである
1.5 本記事の構成
本記事では、以下の内容を体系的に解説する。
- 基本データ構造: 配列、連結リスト、スタック、キュー、デック
- ツリー構造: 二分木から高度な平衡木、セグメント木まで
- ハッシュテーブルとグラフ: ハッシュの仕組みとグラフアルゴリズム
- ソートアルゴリズム: 基本的なソートから高効率なソートまで
- 探索と動的計画法: 探索手法とDPによる最適化
- 高度なアルゴリズム: 貪欲法、分割統治、文字列アルゴリズム等
- 実践ガイド: 競技プログラミングや実務での活用法
各トピックについて、理論的な解説に加えて、Python・Java・TypeScriptでの具体的な実装例を提示する。
2. 基本データ構造
2.1 配列（Array）
配列は、同じ型の要素をメモリ上に連続して格納するデータ構造である。インデックスを用いたランダムアクセスが O(1) で可能な点が最大の特徴である。
計算量
| 操作 | 静的配列 | 動的配列 |
|---|---|---|
| インデックスアクセス | O(1) | O(1) |
| 末尾への追加 | N/A | 償却 O(1) |
| 先頭への挿入 | O(n) | O(n) |
| 任意位置への挿入 | O(n) | O(n) |
| 末尾からの削除 | N/A | O(1) |
| 任意位置の削除 | O(n) | O(n) |
| 探索（未ソート） | O(n) | O(n) |
Python実装例
# Pythonのリストは動的配列として実装されている
# 基本操作
arr = [1, 2, 3, 4, 5]
# インデックスアクセス O(1)
print(arr[2]) # 3
# 末尾への追加 償却O(1)
arr.append(6) # [1, 2, 3, 4, 5, 6]
# 任意位置への挿入 O(n)
arr.insert(2, 10) # [1, 2, 10, 3, 4, 5, 6]
# 削除 O(n)
arr.pop(2) # [1, 2, 3, 4, 5, 6]
# 動的配列の自作実装
class DynamicArray:
def __init__(self):
self._capacity = 4
self._size = 0
self._data = [None] * self._capacity
def __len__(self):
return self._size
def __getitem__(self, index):
if index < 0 or index >= self._size:
raise IndexError("Index out of range")
return self._data[index]
def append(self, value):
if self._size == self._capacity:
self._resize(self._capacity * 2)
self._data[self._size] = value
self._size += 1
def pop(self):
if self._size == 0:
raise IndexError("Pop from empty array")
self._size -= 1
val = self._data[self._size]
self._data[self._size] = None
if self._size > 0 and self._size <= self._capacity // 4:
self._resize(self._capacity // 2)
return val
def _resize(self, new_capacity):
new_data = [None] * new_capacity
for i in range(self._size):
new_data[i] = self._data[i]
self._data = new_data
self._capacity = new_capacity
Java実装例
import java.util.ArrayList;
import java.util.Arrays;
public class ArrayExample {
// 静的配列
public static void staticArrayExample() {
int[] arr = new int[]{1, 2, 3, 4, 5};
System.out.println(arr[2]); // 3
}
// 動的配列 (ArrayList)
public static void dynamicArrayExample() {
ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.get(1); // O(1)
list.add(1, 10); // O(n) - インデックス1に挿入
list.remove(1); // O(n)
}
// 動的配列の自作実装
static class DynamicArray<T> {
private Object[] data;
private int size;
private int capacity;
public DynamicArray() {
this.capacity = 4;
this.size = 0;
this.data = new Object[capacity];
}
@SuppressWarnings("unchecked")
public T get(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException();
return (T) data[index];
}
public void add(T value) {
if (size == capacity) resize(capacity * 2);
data[size++] = value;
}
@SuppressWarnings("unchecked")
public T removeLast() {
if (size == 0) throw new RuntimeException("Empty");
T val = (T) data[--size];
data[size] = null;
if (size > 0 && size <= capacity / 4) resize(capacity / 2);
return val;
}
private void resize(int newCapacity) {
data = Arrays.copyOf(data, newCapacity);
capacity = newCapacity;
}
public int size() { return size; }
}
}
TypeScript実装例
// TypeScriptの配列は動的配列
const arr: number[] = [1, 2, 3, 4, 5];
// インデックスアクセス O(1)
console.log(arr[2]); // 3
// 末尾への追加 償却O(1)
arr.push(6);
// 先頭への挿入 O(n)
arr.unshift(0);
// 動的配列の自作実装
class DynamicArray<T> {
private data: (T | undefined)[];
private _size: number;
private capacity: number;
constructor() {
this.capacity = 4;
this._size = 0;
this.data = new Array(this.capacity);
}
get(index: number): T {
if (index < 0 || index >= this._size) {
throw new Error("Index out of range");
}
return this.data[index] as T;
}
push(value: T): void {
if (this._size === this.capacity) {
this.resize(this.capacity * 2);
}
this.data[this._size++] = value;
}
pop(): T {
if (this._size === 0) throw new Error("Empty");
const val = this.data[--this._size] as T;
this.data[this._size] = undefined;
if (this._size > 0 && this._size <= this.capacity / 4) {
this.resize(this.capacity / 2);
}
return val;
}
get size(): number { return this._size; }
private resize(newCapacity: number): void {
const newData = new Array(newCapacity);
for (let i = 0; i < this._size; i++) {
newData[i] = this.data[i];
}
this.data = newData;
this.capacity = newCapacity;
}
}
2.2 連結リスト（Linked List）
連結リストは、各要素（ノード）がデータと次のノードへの参照（ポインタ）を持つデータ構造である。メモリ上で連続している必要がないため、挿入・削除が効率的に行える。
種類
- 単方向連結リスト（Singly Linked List）: 各ノードが次のノードへの参照のみを持つ
- 双方向連結リスト（Doubly Linked List）: 各ノードが前後のノードへの参照を持つ
- 循環連結リスト（Circular Linked List）: 末尾のノードが先頭を指す
計算量
| 操作 | 単方向 | 双方向 |
|---|---|---|
| 先頭への挿入 | O(1) | O(1) |
| 末尾への挿入 | O(n) / O(1)* | O(1) |
| 任意位置への挿入 | O(n) | O(n) |
| 先頭の削除 | O(1) | O(1) |
| 末尾の削除 | O(n) | O(1) |
| 探索 | O(n) | O(n) |
| インデックスアクセス | O(n) | O(n) |
*末尾ポインタを保持している場合
Python実装例（双方向連結リスト）
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self):
# センチネルノードを使用
self.head = Node(None) # ダミーヘッド
self.tail = Node(None) # ダミーテール
self.head.next = self.tail
self.tail.prev = self.head
self._size = 0
def __len__(self):
return self._size
def is_empty(self):
return self._size == 0
def push_front(self, data):
"""先頭に挿入 O(1)"""
new_node = Node(data)
new_node.next = self.head.next
new_node.prev = self.head
self.head.next.prev = new_node
self.head.next = new_node
self._size += 1
def push_back(self, data):
"""末尾に挿入 O(1)"""
new_node = Node(data)
new_node.prev = self.tail.prev
new_node.next = self.tail
self.tail.prev.next = new_node
self.tail.prev = new_node
self._size += 1
def pop_front(self):
"""先頭を削除 O(1)"""
if self.is_empty():
raise IndexError("List is empty")
node = self.head.next
self.head.next = node.next
node.next.prev = self.head
self._size -= 1
return node.data
def pop_back(self):
"""末尾を削除 O(1)"""
if self.is_empty():
raise IndexError("List is empty")
node = self.tail.prev
self.tail.prev = node.prev
node.prev.next = self.tail
self._size -= 1
return node.data
def find(self, data):
"""探索 O(n)"""
current = self.head.next
while current != self.tail:
if current.data == data:
return current
current = current.next
return None
def remove(self, node):
"""ノードの削除 O(1) ※ノード参照がある場合"""
node.prev.next = node.next
node.next.prev = node.prev
self._size -= 1
return node.data
def to_list(self):
result = []
current = self.head.next
while current != self.tail:
result.append(current.data)
current = current.next
return result
# 使用例
dll = DoublyLinkedList()
dll.push_back(1)
dll.push_back(2)
dll.push_back(3)
dll.push_front(0)
print(dll.to_list()) # [0, 1, 2, 3]
dll.pop_front() # 0を削除
dll.pop_back() # 3を削除
print(dll.to_list()) # [1, 2]
Java実装例（単方向連結リスト）
public class SinglyLinkedList<T> {
private static class Node<T> {
T data;
Node<T> next;
Node(T data) { this.data = data; this.next = null; }
}
private Node<T> head;
private int size;
public SinglyLinkedList() {
head = null;
size = 0;
}
public void pushFront(T data) {
Node<T> newNode = new Node<>(data);
newNode.next = head;
head = newNode;
size++;
}
public T popFront() {
if (head == null) throw new RuntimeException("Empty list");
T data = head.data;
head = head.next;
size--;
return data;
}
public void pushBack(T data) {
Node<T> newNode = new Node<>(data);
if (head == null) {
head = newNode;
} else {
Node<T> current = head;
while (current.next != null) current = current.next;
current.next = newNode;
}
size++;
}
public boolean contains(T data) {
Node<T> current = head;
while (current != null) {
if (current.data.equals(data)) return true;
current = current.next;
}
return false;
}
public void reverse() {
Node<T> prev = null;
Node<T> current = head;
while (current != null) {
Node<T> next = current.next;
current.next = prev;
prev = current;
current = next;
}
head = prev;
}
public int size() { return size; }
}
TypeScript実装例（双方向連結リスト）
class ListNode<T> {
data: T;
prev: ListNode<T> | null = null;
next: ListNode<T> | null = null;
constructor(data: T) { this.data = data; }
}
class DoublyLinkedList<T> {
private head: ListNode<T>;
private tail: ListNode<T>;
private _size = 0;
constructor() {
this.head = new ListNode<T>(null as any); // sentinel
this.tail = new ListNode<T>(null as any); // sentinel
this.head.next = this.tail;
this.tail.prev = this.head;
}
get size(): number { return this._size; }
pushFront(data: T): void {
const node = new ListNode(data);
node.next = this.head.next;
node.prev = this.head;
this.head.next!.prev = node;
this.head.next = node;
this._size++;
}
pushBack(data: T): void {
const node = new ListNode(data);
node.prev = this.tail.prev;
node.next = this.tail;
this.tail.prev!.next = node;
this.tail.prev = node;
this._size++;
}
popFront(): T {
if (this._size === 0) throw new Error("Empty");
const node = this.head.next!;
this.head.next = node.next;
node.next!.prev = this.head;
this._size--;
return node.data;
}
popBack(): T {
if (this._size === 0) throw new Error("Empty");
const node = this.tail.prev!;
this.tail.prev = node.prev;
node.prev!.next = this.tail;
this._size--;
return node.data;
}
toArray(): T[] {
const result: T[] = [];
let current = this.head.next;
while (current !== this.tail) {
result.push(current!.data);
current = current!.next;
}
return result;
}
}
2.3 スタック（Stack）
スタックは、LIFO（Last In, First Out: 後入れ先出し） の原則に従うデータ構造である。最後に追加された要素が最初に取り出される。
主な操作と計算量
| 操作 | 計算量 | 説明 |
|---|---|---|
| push | O(1) | 要素を上に積む |
| pop | O(1) | 上の要素を取り出す |
| peek/top | O(1) | 上の要素を参照（取り出さない） |
| isEmpty | O(1) | 空かどうかの判定 |
典型的な活用場面
- 関数呼び出しスタック
- 括弧の対応チェック
- ブラウザの「戻る」機能
- 深さ優先探索（DFS）
- 逆ポーランド記法の計算
Python実装例
class Stack:
def __init__(self):
self._data = []
def push(self, value):
self._data.append(value)
def pop(self):
if self.is_empty():
raise IndexError("Stack is empty")
return self._data.pop()
def peek(self):
if self.is_empty():
raise IndexError("Stack is empty")
return self._data[-1]
def is_empty(self):
return len(self._data) == 0
def __len__(self):
return len(self._data)
# 活用例: 括弧の対応チェック
def is_valid_parentheses(s: str) -> bool:
stack = Stack()
mapping = {')': '(', '}': '{', ']': '['}
for char in s:
if char in '({[':
stack.push(char)
elif char in ')}]':
if stack.is_empty() or stack.pop() != mapping[char]:
return False
return stack.is_empty()
print(is_valid_parentheses("({[]})")) # True
print(is_valid_parentheses("({[})")) # False
# 活用例: 逆ポーランド記法の計算
def eval_rpn(tokens: list) -> int:
stack = Stack()
ops = {
'+': lambda a, b: a + b,
'-': lambda a, b: a - b,
'*': lambda a, b: a * b,
'/': lambda a, b: int(a / b),
}
for token in tokens:
if token in ops:
b = stack.pop()
a = stack.pop()
stack.push(ops[token](a, b))
else:
stack.push(int(token))
return stack.pop()
print(eval_rpn(["2", "1", "+", "3", "*"])) # 9 = (2+1)*3
Java実装例
import java.util.ArrayDeque;
import java.util.Deque;
public class StackExample {
// Javaでは Deque をスタックとして使うのが推奨
public static boolean isValidParentheses(String s) {
Deque<Character> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '{' || c == '[') {
stack.push(c);
} else {
if (stack.isEmpty()) return false;
char top = stack.pop();
if ((c == ')' && top != '(') ||
(c == '}' && top != '{') ||
(c == ']' && top != '[')) {
return false;
}
}
}
return stack.isEmpty();
}
// 配列ベースのスタック実装
static class ArrayStack<T> {
private Object[] data;
private int top;
private int capacity;
public ArrayStack(int capacity) {
this.capacity = capacity;
this.data = new Object[capacity];
this.top = -1;
}
public void push(T value) {
if (top == capacity - 1) throw new RuntimeException("Stack overflow");
data[++top] = value;
}
@SuppressWarnings("unchecked")
public T pop() {
if (top == -1) throw new RuntimeException("Stack underflow");
T val = (T) data[top];
data[top--] = null;
return val;
}
@SuppressWarnings("unchecked")
public T peek() {
if (top == -1) throw new RuntimeException("Stack is empty");
return (T) data[top];
}
public boolean isEmpty() { return top == -1; }
public int size() { return top + 1; }
}
}
TypeScript実装例
class Stack<T> {
private data: T[] = [];
push(value: T): void { this.data.push(value); }
pop(): T {
if (this.isEmpty()) throw new Error("Stack is empty");
return this.data.pop()!;
}
peek(): T {
if (this.isEmpty()) throw new Error("Stack is empty");
return this.data[this.data.length - 1];
}
isEmpty(): boolean { return this.data.length === 0; }
get size(): number { return this.data.length; }
}
// 活用例: 最小値スタック
class MinStack {
private stack: number[] = [];
private minStack: number[] = [];
push(val: number): void {
this.stack.push(val);
const currentMin = this.minStack.length === 0
? val
: Math.min(val, this.minStack[this.minStack.length - 1]);
this.minStack.push(currentMin);
}
pop(): void {
this.stack.pop();
this.minStack.pop();
}
top(): number { return this.stack[this.stack.length - 1]; }
getMin(): number { return this.minStack[this.minStack.length - 1]; }
}
2.4 キュー（Queue）
キューは、FIFO（First In, First Out: 先入れ先出し） の原則に従うデータ構造である。最初に追加された要素が最初に取り出される。
主な操作と計算量
| 操作 | 計算量 | 説明 |
|---|---|---|
| enqueue | O(1) | 末尾に要素を追加 |
| dequeue | O(1) | 先頭の要素を取り出す |
| peek/front | O(1) | 先頭の要素を参照 |
| isEmpty | O(1) | 空かどうかの判定 |
Python実装例
from collections import deque
# dequeを使用したキュー（推奨）
class Queue:
def __init__(self):
self._data = deque()
def enqueue(self, value):
self._data.append(value)
def dequeue(self):
if self.is_empty():
raise IndexError("Queue is empty")
return self._data.popleft()
def peek(self):
if self.is_empty():
raise IndexError("Queue is empty")
return self._data[0]
def is_empty(self):
return len(self._data) == 0
def __len__(self):
return len(self._data)
# 循環バッファによるキュー実装
class CircularQueue:
def __init__(self, capacity):
self._data = [None] * capacity
self._capacity = capacity
self._front = 0
self._rear = 0
self._size = 0
def enqueue(self, value):
if self._size == self._capacity:
raise OverflowError("Queue is full")
self._data[self._rear] = value
self._rear = (self._rear + 1) % self._capacity
self._size += 1
def dequeue(self):
if self._size == 0:
raise IndexError("Queue is empty")
val = self._data[self._front]
self._data[self._front] = None
self._front = (self._front + 1) % self._capacity
self._size -= 1
return val
def peek(self):
if self._size == 0:
raise IndexError("Queue is empty")
return self._data[self._front]
def is_empty(self):
return self._size == 0
def is_full(self):
return self._size == self._capacity
# 優先度付きキュー
import heapq
class PriorityQueue:
def __init__(self):
self._heap = []
def push(self, priority, item):
heapq.heappush(self._heap, (priority, item))
def pop(self):
if not self._heap:
raise IndexError("Queue is empty")
return heapq.heappop(self._heap)
def peek(self):
if not self._heap:
raise IndexError("Queue is empty")
return self._heap[0]
def is_empty(self):
return len(self._heap) == 0
Java実装例
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
public class QueueExample {
public static void basicQueue() {
Queue<Integer> queue = new LinkedList<>();
queue.offer(1); // enqueue
queue.offer(2);
queue.offer(3);
queue.peek(); // 1 (先頭を参照)
queue.poll(); // 1 (先頭を取り出し)
}
// 循環キューの実装
static class CircularQueue<T> {
private Object[] data;
private int front, rear, size, capacity;
public CircularQueue(int capacity) {
this.capacity = capacity;
this.data = new Object[capacity];
this.front = 0;
this.rear = 0;
this.size = 0;
}
public void enqueue(T value) {
if (size == capacity) throw new RuntimeException("Full");
data[rear] = value;
rear = (rear + 1) % capacity;
size++;
}
@SuppressWarnings("unchecked")
public T dequeue() {
if (size == 0) throw new RuntimeException("Empty");
T val = (T) data[front];
data[front] = null;
front = (front + 1) % capacity;
size--;
return val;
}
public boolean isEmpty() { return size == 0; }
public boolean isFull() { return size == capacity; }
}
// 優先度付きキュー
public static void priorityQueueExample() {
PriorityQueue<int[]> pq = new PriorityQueue<>(
(a, b) -> a[0] - b[0] // 優先度の低い順
);
pq.offer(new int[]{3, 100});
pq.offer(new int[]{1, 200});
pq.offer(new int[]{2, 300});
// poll() は優先度1(最小)から取り出される
}
}
TypeScript実装例
class Queue<T> {
private data: Map<number, T> = new Map();
private head = 0;
private tail = 0;
enqueue(value: T): void {
this.data.set(this.tail, value);
this.tail++;
}
dequeue(): T {
if (this.isEmpty()) throw new Error("Queue is empty");
const val = this.data.get(this.head)!;
this.data.delete(this.head);
this.head++;
return val;
}
peek(): T {
if (this.isEmpty()) throw new Error("Queue is empty");
return this.data.get(this.head)!;
}
isEmpty(): boolean { return this.head === this.tail; }
get size(): number { return this.tail - this.head; }
}
2.5 デック（Deque / Double-Ended Queue）
デック（両端キュー）は、先頭と末尾の両方から要素の追加・削除が O(1) で行えるデータ構造である。スタックとキューの両方の機能を兼ね備える。
計算量
| 操作 | 計算量 |
|---|---|
| 先頭への追加 (pushFront) | O(1) |
| 末尾への追加 (pushBack) | O(1) |
| 先頭の削除 (popFront) | O(1) |
| 末尾の削除 (popBack) | O(1) |
| 先頭の参照 | O(1) |
| 末尾の参照 | O(1) |
Python実装例
from collections import deque
# Pythonのdequeは双方向連結リストで実装
dq = deque()
dq.append(1) # 末尾に追加
dq.append(2)
dq.appendleft(0) # 先頭に追加
print(list(dq)) # [0, 1, 2]
dq.pop() # 末尾から削除 → 2
dq.popleft() # 先頭から削除 → 0
# 活用例: スライディングウィンドウ最大値
def max_sliding_window(nums: list, k: int) -> list:
"""
サイズkのスライディングウィンドウの最大値をO(n)で求める
"""
dq = deque() # インデックスを格納（単調減少デック）
result = []
for i, num in enumerate(nums):
# ウィンドウ外の要素を削除
while dq and dq[0] < i - k + 1:
dq.popleft()
# 現在の要素より小さい要素をすべて削除
while dq and nums[dq[-1]] <= num:
dq.pop()
dq.append(i)
# ウィンドウが完成したら結果に追加
if i >= k - 1:
result.append(nums[dq[0]])
return result
print(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3))
# [3, 3, 5, 5, 6, 7]
Java実装例
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.ArrayList;
import java.util.List;
public class DequeExample {
// スライディングウィンドウ最大値
public static int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> dq = new ArrayDeque<>();
int[] result = new int[nums.length - k + 1];
int idx = 0;
for (int i = 0; i < nums.length; i++) {
while (!dq.isEmpty() && dq.peekFirst() < i - k + 1) {
dq.pollFirst();
}
while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) {
dq.pollLast();
}
dq.offerLast(i);
if (i >= k - 1) {
result[idx++] = nums[dq.peekFirst()];
}
}
return result;
}
}
TypeScript実装例
class Deque<T> {
private data: Map<number, T> = new Map();
private head = 0;
private tail = 0;
pushFront(value: T): void {
this.head--;
this.data.set(this.head, value);
}
pushBack(value: T): void {
this.data.set(this.tail, value);
this.tail++;
}
popFront(): T {
if (this.isEmpty()) throw new Error("Deque is empty");
const val = this.data.get(this.head)!;
this.data.delete(this.head);
this.head++;
return val;
}
popBack(): T {
if (this.isEmpty()) throw new Error("Deque is empty");
this.tail--;
const val = this.data.get(this.tail)!;
this.data.delete(this.tail);
return val;
}
peekFront(): T {
if (this.isEmpty()) throw new Error("Deque is empty");
return this.data.get(this.head)!;
}
peekBack(): T {
if (this.isEmpty()) throw new Error("Deque is empty");
return this.data.get(this.tail - 1)!;
}
isEmpty(): boolean { return this.head === this.tail; }
get size(): number { return this.tail - this.head; }
}
// スライディングウィンドウ最大値
function maxSlidingWindow(nums: number[], k: number): number[] {
const dq: number[] = []; // インデックスの単調減少デック
const result: number[] = [];
for (let i = 0; i < nums.length; i++) {
while (dq.length > 0 && dq[0] < i - k + 1) dq.shift();
while (dq.length > 0 && nums[dq[dq.length - 1]] <= nums[i]) dq.pop();
dq.push(i);
if (i >= k - 1) result.push(nums[dq[0]]);
}
return result;
}
2.6 基本データ構造の比較まとめ
| データ構造 | 主な用途 | アクセス | 挿入 | 削除 | 探索 |
|---|---|---|---|---|---|
| 配列 | ランダムアクセス | O(1) | O(n) | O(n) | O(n) |
| 連結リスト | 頻繁な挿入/削除 | O(n) | O(1)* | O(1)* | O(n) |
| スタック | LIFO処理 | O(1)top | O(1) | O(1) | O(n) |
| キュー | FIFO処理 | O(1)front | O(1) | O(1) | O(n) |
| デック | 両端操作 | O(1)両端 | O(1) | O(1) | O(n) |
*ノードの参照がある場合
3. ツリー構造
3.1 ツリーの基本概念
ツリー（木構造）は、ノードとエッジで構成される非線形の階層的データ構造である。一つのルート（根）ノードから始まり、各ノードは0個以上の子ノードを持つ。
用語定義
| 用語 | 説明 |
|---|---|
| ルート（Root） | ツリーの最上位ノード |
| 葉（Leaf） | 子を持たないノード |
| 深さ（Depth） | ルートからそのノードまでのエッジ数 |
| 高さ（Height） | そのノードから最も深い葉までのエッジ数 |
| 部分木（Subtree） | あるノードを根とするツリー |
| 次数（Degree） | ノードが持つ子の数 |
3.2 二分木（Binary Tree）
各ノードが最大2つの子（左の子、右の子）を持つツリー。
種類
- 完全二分木（Complete Binary Tree）: 最下段を除きすべてのレベルが満たされ、最下段は左詰め
- 満二分木（Full Binary Tree）: すべてのノードが0個または2個の子を持つ
- 完璧二分木（Perfect Binary Tree）: すべての内部ノードが2個の子を持ち、すべての葉が同じ深さ
走査（Traversal）
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 前順走査（Preorder）: 根 → 左 → 右
def preorder(node):
if node is None:
return []
return [node.val] + preorder(node.left) + preorder(node.right)
# 中順走査（Inorder）: 左 → 根 → 右
def inorder(node):
if node is None:
return []
return inorder(node.left) + [node.val] + inorder(node.right)
# 後順走査（Postorder）: 左 → 右 → 根
def postorder(node):
if node is None:
return []
return postorder(node.left) + postorder(node.right) + [node.val]
# レベル順走査（Level-order / BFS）
from collections import deque
def level_order(root):
if root is None:
return []
result = []
queue = deque([root])
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
# 反復的な中順走査（スタックを使用）
def inorder_iterative(root):
result = []
stack = []
current = root
while current or stack:
while current:
stack.append(current)
current = current.left
current = stack.pop()
result.append(current.val)
current = current.right
return result
Java実装例
import java.util.*;
public class BinaryTree {
static class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { this.val = val; }
}
// 中順走査（反復）
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode current = root;
while (current != null || !stack.isEmpty()) {
while (current != null) {
stack.push(current);
current = current.left;
}
current = stack.pop();
result.add(current.val);
current = current.right;
}
return result;
}
// レベル順走査
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(level);
}
return result;
}
}
3.3 二分探索木（Binary Search Tree: BST）
二分探索木は、以下の性質を持つ二分木である。
- 左部分木のすべてのノードの値 < 親ノードの値
- 右部分木のすべてのノードの値 > 親ノードの値
計算量
| 操作 | 平均 | 最悪（偏った木） |
|---|---|---|
| 探索 | O(log n) | O(n) |
| 挿入 | O(log n) | O(n) |
| 削除 | O(log n) | O(n) |
Python実装例
class BSTNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def insert(self, key):
self.root = self._insert(self.root, key)
def _insert(self, node, key):
if node is None:
return BSTNode(key)
if key < node.key:
node.left = self._insert(node.left, key)
elif key > node.key:
node.right = self._insert(node.right, key)
return node
def search(self, key):
return self._search(self.root, key)
def _search(self, node, key):
if node is None or node.key == key:
return node
if key < node.key:
return self._search(node.left, key)
return self._search(node.right, key)
def delete(self, key):
self.root = self._delete(self.root, key)
def _delete(self, node, key):
if node is None:
return None
if key < node.key:
node.left = self._delete(node.left, key)
elif key > node.key:
node.right = self._delete(node.right, key)
else:
# ケース1: 葉ノードまたは子が1つ
if node.left is None:
return node.right
if node.right is None:
return node.left
# ケース2: 子が2つ → 右部分木の最小値で置換
successor = self._find_min(node.right)
node.key = successor.key
node.right = self._delete(node.right, successor.key)
return node
def _find_min(self, node):
while node.left:
node = node.left
return node
def inorder(self):
result = []
self._inorder(self.root, result)
return result
def _inorder(self, node, result):
if node:
self._inorder(node.left, result)
result.append(node.key)
self._inorder(node.right, result)
# 使用例
bst = BST()
for key in [5, 3, 7, 1, 4, 6, 8]:
bst.insert(key)
print(bst.inorder()) # [1, 3, 4, 5, 6, 7, 8]
print(bst.search(4).key) # 4
bst.delete(3)
print(bst.inorder()) # [1, 4, 5, 6, 7, 8]
3.4 AVL木（AVL Tree）
AVL木は、各ノードにおいて左右の部分木の高さの差（バランスファクター）が -1, 0, 1 のいずれかであることを保証する自己平衡二分探索木である。
回転操作
バランスが崩れた場合、以下の回転操作で修正する。
- 右回転（LL回転）: 左の子が重い場合
- 左回転（RR回転）: 右の子が重い場合
- 左右回転（LR回転）: 左の子の右が重い場合
- 右左回転（RL回転）: 右の子の左が重い場合
Python実装例
class AVLNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1
class AVLTree:
def _height(self, node):
return node.height if node else 0
def _balance_factor(self, node):
return self._height(node.left) - self._height(node.right) if node else 0
def _update_height(self, node):
node.height = 1 + max(self._height(node.left), self._height(node.right))
def _rotate_right(self, y):
"""右回転"""
x = y.left
t = x.right
x.right = y
y.left = t
self._update_height(y)
self._update_height(x)
return x
def _rotate_left(self, x):
"""左回転"""
y = x.right
t = y.left
y.left = x
x.right = t
self._update_height(x)
self._update_height(y)
return y
def _balance(self, node):
self._update_height(node)
bf = self._balance_factor(node)
# 左が重い
if bf > 1:
if self._balance_factor(node.left) < 0:
node.left = self._rotate_left(node.left) # LR
return self._rotate_right(node) # LL
# 右が重い
if bf < -1:
if self._balance_factor(node.right) > 0:
node.right = self._rotate_right(node.right) # RL
return self._rotate_left(node) # RR
return node
def insert(self, root, key):
if root is None:
return AVLNode(key)
if key < root.key:
root.left = self.insert(root.left, key)
elif key > root.key:
root.right = self.insert(root.right, key)
else:
return root
return self._balance(root)
def delete(self, root, key):
if root is None:
return None
if key < root.key:
root.left = self.delete(root.left, key)
elif key > root.key:
root.right = self.delete(root.right, key)
else:
if root.left is None:
return root.right
if root.right is None:
return root.left
# 右部分木の最小値で置換
min_node = root.right
while min_node.left:
min_node = min_node.left
root.key = min_node.key
root.right = self.delete(root.right, min_node.key)
return self._balance(root)
# 使用例
avl = AVLTree()
root = None
for key in [10, 20, 30, 40, 50, 25]:
root = avl.insert(root, key)
# 木は自動的にバランスされる
Java実装例
public class AVLTree {
static class Node {
int key, height;
Node left, right;
Node(int key) {
this.key = key;
this.height = 1;
}
}
private int height(Node n) { return n == null ? 0 : n.height; }
private int balanceFactor(Node n) { return n == null ? 0 : height(n.left) - height(n.right); }
private void updateHeight(Node n) {
n.height = 1 + Math.max(height(n.left), height(n.right));
}
private Node rotateRight(Node y) {
Node x = y.left;
Node t = x.right;
x.right = y;
y.left = t;
updateHeight(y);
updateHeight(x);
return x;
}
private Node rotateLeft(Node x) {
Node y = x.right;
Node t = y.left;
y.left = x;
x.right = t;
updateHeight(x);
updateHeight(y);
return y;
}
private Node balance(Node node) {
updateHeight(node);
int bf = balanceFactor(node);
if (bf > 1) {
if (balanceFactor(node.left) < 0) node.left = rotateLeft(node.left);
return rotateRight(node);
}
if (bf < -1) {
if (balanceFactor(node.right) > 0) node.right = rotateRight(node.right);
return rotateLeft(node);
}
return node;
}
public Node insert(Node node, int key) {
if (node == null) return new Node(key);
if (key < node.key) node.left = insert(node.left, key);
else if (key > node.key) node.right = insert(node.right, key);
else return node;
return balance(node);
}
}
3.5 赤黒木（Red-Black Tree）
赤黒木は、以下の性質を持つ自己平衡二分探索木である。
- 各ノードは赤か黒のいずれか
- ルートは黒
- すべての葉（NIL）は黒
- 赤ノードの子は両方とも黒（赤が連続しない）
- 任意のノードからその子孫の葉までの各パスに含まれる黒ノードの数は同じ
AVL木と比較して、赤黒木は挿入・削除時の回転回数が少ないため、頻繁に更新が行われる場面で有利である。Java の TreeMap、C++ の std::map は赤黒木で実装されている。
計算量
| 操作 | 計算量 |
|---|---|
| 探索 | O(log n) |
| 挿入 | O(log n) |
| 削除 | O(log n) |
Python実装例（簡略版）
class RBColor:
RED = True
BLACK = False
class RBNode:
def __init__(self, key, color=RBColor.RED):
self.key = key
self.color = color
self.left = None
self.right = None
self.parent = None
class RedBlackTree:
def __init__(self):
self.NIL = RBNode(None, RBColor.BLACK)
self.root = self.NIL
def _rotate_left(self, x):
y = x.right
x.right = y.left
if y.left != self.NIL:
y.left.parent = x
y.parent = x.parent
if x.parent is None:
self.root = y
elif x == x.parent.left:
x.parent.left = y
else:
x.parent.right = y
y.left = x
x.parent = y
def _rotate_right(self, y):
x = y.left
y.left = x.right
if x.right != self.NIL:
x.right.parent = y
x.parent = y.parent
if y.parent is None:
self.root = x
elif y == y.parent.right:
y.parent.right = x
else:
y.parent.left = x
x.right = y
y.parent = x
def insert(self, key):
node = RBNode(key)
node.left = self.NIL
node.right = self.NIL
parent = None
current = self.root
while current != self.NIL:
parent = current
if key < current.key:
current = current.left
else:
current = current.right
node.parent = parent
if parent is None:
self.root = node
elif key < parent.key:
parent.left = node
else:
parent.right = node
self._fix_insert(node)
def _fix_insert(self, z):
while z.parent and z.parent.color == RBColor.RED:
if z.parent == z.parent.parent.left:
uncle = z.parent.parent.right
if uncle.color == RBColor.RED:
# Case 1: 叔父が赤
z.parent.color = RBColor.BLACK
uncle.color = RBColor.BLACK
z.parent.parent.color = RBColor.RED
z = z.parent.parent
else:
if z == z.parent.right:
# Case 2: 叔父が黒、zが右の子
z = z.parent
self._rotate_left(z)
# Case 3: 叔父が黒、zが左の子
z.parent.color = RBColor.BLACK
z.parent.parent.color = RBColor.RED
self._rotate_right(z.parent.parent)
else:
# 左右対称
uncle = z.parent.parent.left
if uncle.color == RBColor.RED:
z.parent.color = RBColor.BLACK
uncle.color = RBColor.BLACK
z.parent.parent.color = RBColor.RED
z = z.parent.parent
else:
if z == z.parent.left:
z = z.parent
self._rotate_right(z)
z.parent.color = RBColor.BLACK
z.parent.parent.color = RBColor.RED
self._rotate_left(z.parent.parent)
self.root.color = RBColor.BLACK
3.6 B木（B-Tree）
B木は、データベースやファイルシステムで広く使われる自己平衡探索木である。各ノードが複数のキーと子を持てるため、ディスクアクセスを最小化できる。
性質（次数 t のB木）
- 各ノードは最大 2t-1 個のキーを持つ
- 各ノードは最大 2t 個の子を持つ
- ルート以外の各ノードは最低 t-1 個のキーを持つ
- すべての葉は同じ深さ
Python実装例（簡略版）
class BTreeNode:
def __init__(self, t, leaf=True):
self.t = t # 最小次数
self.keys = [] # キーのリスト
self.children = [] # 子ノードのリスト
self.leaf = leaf
class BTree:
def __init__(self, t):
self.t = t
self.root = BTreeNode(t)
def search(self, node, key):
i = 0
while i < len(node.keys) and key > node.keys[i]:
i += 1
if i < len(node.keys) and key == node.keys[i]:
return (node, i)
if node.leaf:
return None
return self.search(node.children[i], key)
def insert(self, key):
root = self.root
if len(root.keys) == 2 * self.t - 1:
new_root = BTreeNode(self.t, leaf=False)
new_root.children.append(self.root)
self._split_child(new_root, 0)
self.root = new_root
self._insert_non_full(self.root, key)
def _split_child(self, parent, i):
t = self.t
child = parent.children[i]
new_node = BTreeNode(t, child.leaf)
parent.keys.insert(i, child.keys[t - 1])
parent.children.insert(i + 1, new_node)
new_node.keys = child.keys[t:]
child.keys = child.keys[:t - 1]
if not child.leaf:
new_node.children = child.children[t:]
child.children = child.children[:t]
def _insert_non_full(self, node, key):
i = len(node.keys) - 1
if node.leaf:
node.keys.append(None)
while i >= 0 and key < node.keys[i]:
node.keys[i + 1] = node.keys[i]
i -= 1
node.keys[i + 1] = key
else:
while i >= 0 and key < node.keys[i]:
i -= 1
i += 1
if len(node.children[i].keys) == 2 * self.t - 1:
self._split_child(node, i)
if key > node.keys[i]:
i += 1
self._insert_non_full(node.children[i], key)
3.7 トライ木（Trie / Prefix Tree）
トライ木は、文字列の集合を効率的に格納・検索するためのツリー構造である。各エッジが文字に対応し、ルートから葉までのパスが一つの文字列を表す。
計算量（文字列の長さを m とする）
| 操作 | 計算量 |
|---|---|
| 挿入 | O(m) |
| 探索 | O(m) |
| 前方一致探索 | O(m + k) ※k は結果数 |
Python実装例
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
self.count = 0 # この接頭辞を持つ文字列の数
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.count += 1
node.is_end = True
def search(self, word: str) -> bool:
node = self._find_node(word)
return node is not None and node.is_end
def starts_with(self, prefix: str) -> bool:
return self._find_node(prefix) is not None
def count_prefix(self, prefix: str) -> int:
node = self._find_node(prefix)
return node.count if node else 0
def _find_node(self, prefix: str):
node = self.root
for char in prefix:
if char not in node.children:
return None
node = node.children[char]
return node
def get_all_words(self, prefix: str = "") -> list:
"""前方一致するすべての文字列を返す"""
node = self._find_node(prefix)
if node is None:
return []
result = []
self._collect_words(node, prefix, result)
return result
def _collect_words(self, node, prefix, result):
if node.is_end:
result.append(prefix)
for char, child in node.children.items():
self._collect_words(child, prefix + char, result)
# 使用例
trie = Trie()
for word in ["apple", "app", "application", "banana", "band"]:
trie.insert(word)
print(trie.search("app")) # True
print(trie.search("ap")) # False
print(trie.starts_with("app")) # True
print(trie.count_prefix("app")) # 3
print(trie.get_all_words("app")) # ['apple', 'app', 'application']
TypeScript実装例
class TrieNode {
children: Map<string, TrieNode> = new Map();
isEnd = false;
}
class Trie {
private root = new TrieNode();
insert(word: string): void {
let node = this.root;
for (const ch of word) {
if (!node.children.has(ch)) {
node.children.set(ch, new TrieNode());
}
node = node.children.get(ch)!;
}
node.isEnd = true;
}
search(word: string): boolean {
const node = this.findNode(word);
return node !== null && node.isEnd;
}
startsWith(prefix: string): boolean {
return this.findNode(prefix) !== null;
}
private findNode(prefix: string): TrieNode | null {
let node = this.root;
for (const ch of prefix) {
if (!node.children.has(ch)) return null;
node = node.children.get(ch)!;
}
return node;
}
}
3.8 セグメント木（Segment Tree）
セグメント木は、配列の区間に対するクエリ（区間の合計、最小値、最大値など）と要素の更新を効率的に行うデータ構造である。
計算量
| 操作 | 計算量 |
|---|---|
| 構築 | O(n) |
| 区間クエリ | O(log n) |
| 要素の更新 | O(log n) |
Python実装例
class SegmentTree:
def __init__(self, data):
self.n = len(data)
self.tree = [0] * (4 * self.n)
self._build(data, 1, 0, self.n - 1)
def _build(self, data, node, start, end):
if start == end:
self.tree[node] = data[start]
else:
mid = (start + end) // 2
self._build(data, 2 * node, start, mid)
self._build(data, 2 * node + 1, mid + 1, end)
self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
def update(self, index, value):
"""index番目の要素をvalueに更新"""
self._update(1, 0, self.n - 1, index, value)
def _update(self, node, start, end, index, value):
if start == end:
self.tree[node] = value
else:
mid = (start + end) // 2
if index <= mid:
self._update(2 * node, start, mid, index, value)
else:
self._update(2 * node + 1, mid + 1, end, index, value)
self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
def query(self, left, right):
"""[left, right] の区間合計を返す"""
return self._query(1, 0, self.n - 1, left, right)
def _query(self, node, start, end, left, right):
if right < start or end < left:
return 0 # 区間外
if left <= start and end <= right:
return self.tree[node] # 完全に含まれる
mid = (start + end) // 2
return (self._query(2 * node, start, mid, left, right) +
self._query(2 * node + 1, mid + 1, end, left, right))
# 遅延伝播付きセグメント木（区間更新対応）
class LazySegTree:
def __init__(self, data):
self.n = len(data)
self.tree = [0] * (4 * self.n)
self.lazy = [0] * (4 * self.n)
self._build(data, 1, 0, self.n - 1)
def _build(self, data, node, start, end):
if start == end:
self.tree[node] = data[start]
else:
mid = (start + end) // 2
self._build(data, 2 * node, start, mid)
self._build(data, 2 * node + 1, mid + 1, end)
self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
def _push_down(self, node, start, end):
if self.lazy[node] != 0:
mid = (start + end) // 2
self._apply(2 * node, start, mid, self.lazy[node])
self._apply(2 * node + 1, mid + 1, end, self.lazy[node])
self.lazy[node] = 0
def _apply(self, node, start, end, val):
self.tree[node] += val * (end - start + 1)
self.lazy[node] += val
def range_update(self, left, right, val):
"""[left, right] の全要素にvalを加算"""
self._range_update(1, 0, self.n - 1, left, right, val)
def _range_update(self, node, start, end, left, right, val):
if right < start or end < left:
return
if left <= start and end <= right:
self._apply(node, start, end, val)
return
self._push_down(node, start, end)
mid = (start + end) // 2
self._range_update(2 * node, start, mid, left, right, val)
self._range_update(2 * node + 1, mid + 1, end, left, right, val)
self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
def query(self, left, right):
return self._query(1, 0, self.n - 1, left, right)
def _query(self, node, start, end, left, right):
if right < start or end < left:
return 0
if left <= start and end <= right:
return self.tree[node]
self._push_down(node, start, end)
mid = (start + end) // 2
return (self._query(2 * node, start, mid, left, right) +
self._query(2 * node + 1, mid + 1, end, left, right))
# 使用例
data = [1, 3, 5, 7, 9, 11]
seg = SegmentTree(data)
print(seg.query(1, 3)) # 3 + 5 + 7 = 15
seg.update(2, 10) # 5 → 10 に更新
print(seg.query(1, 3)) # 3 + 10 + 7 = 20
3.9 ツリー構造の比較まとめ
| 構造 | 探索 | 挿入 | 削除 | 特徴 |
|---|---|---|---|---|
| 二分探索木 | O(log n)~O(n) | O(log n)~O(n) | O(log n)~O(n) | 単純だが偏りうる |
| AVL木 | O(log n) | O(log n) | O(log n) | 厳密にバランス、探索が高速 |
| 赤黒木 | O(log n) | O(log n) | O(log n) | 挿入/削除の回転が少ない |
| B木 | O(log n) | O(log n) | O(log n) | ディスクアクセス最適化 |
| トライ木 | O(m) | O(m) | O(m) | 文字列操作に特化 |
| セグメント木 | O(log n) | O(log n) | - | 区間クエリに特化 |
4. ハッシュテーブルとグラフ
4.1 ハッシュテーブル（Hash Table）
ハッシュテーブルは、キーと値のペアを格納するデータ構造で、ハッシュ関数を用いてキーからインデックスを計算することで、平均 O(1) での検索・挿入・削除を実現する。
計算量
| 操作 | 平均 | 最悪 |
|---|---|---|
| 挿入 | O(1) | O(n) |
| 探索 | O(1) | O(n) |
| 削除 | O(1) | O(n) |
最悪ケースは、すべてのキーが同じハッシュ値に衝突した場合に発生する。
4.1.1 ハッシュ関数
良いハッシュ関数の条件:
- 決定性: 同じ入力に対して常に同じ出力
- 一様分布: 出力がバケット全体に均等に分散
- 高速: 計算が高速であること
# 簡単なハッシュ関数の例
def simple_hash(key: str, size: int) -> int:
"""文字列キーに対する単純なハッシュ関数"""
h = 0
for char in key:
h = (h * 31 + ord(char)) % size
return h
# Python の組み込みハッシュ
print(hash("hello")) # 整数値が返る
print(hash(42))
print(hash((1, 2, 3))) # タプルはハッシュ可能
4.1.2 衝突解決法
チェイニング（Chaining）: 各バケットに連結リストを格納する方法。
class HashTableChaining:
def __init__(self, capacity=16):
self.capacity = capacity
self.size = 0
self.buckets = [[] for _ in range(capacity)]
self.load_factor_threshold = 0.75
def _hash(self, key):
return hash(key) % self.capacity
def put(self, key, value):
index = self._hash(key)
bucket = self.buckets[index]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
bucket.append((key, value))
self.size += 1
if self.size / self.capacity > self.load_factor_threshold:
self._resize()
def get(self, key):
index = self._hash(key)
for k, v in self.buckets[index]:
if k == key:
return v
raise KeyError(key)
def remove(self, key):
index = self._hash(key)
bucket = self.buckets[index]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket.pop(i)
self.size -= 1
return v
raise KeyError(key)
def _resize(self):
old_buckets = self.buckets
self.capacity *= 2
self.buckets = [[] for _ in range(self.capacity)]
self.size = 0
for bucket in old_buckets:
for key, value in bucket:
self.put(key, value)
def __contains__(self, key):
index = self._hash(key)
return any(k == key for k, _ in self.buckets[index])
オープンアドレス法（Open Addressing）: 衝突時に別のバケットを探す方法。
class HashTableOpenAddressing:
EMPTY = object()
DELETED = object()
def __init__(self, capacity=16):
self.capacity = capacity
self.size = 0
self.keys = [self.EMPTY] * capacity
self.values = [None] * capacity
def _hash(self, key, attempt):
# 線形探索法
return (hash(key) + attempt) % self.capacity
def put(self, key, value):
if self.size >= self.capacity * 0.7:
self._resize()
for i in range(self.capacity):
index = self._hash(key, i)
if self.keys[index] is self.EMPTY or self.keys[index] is self.DELETED:
self.keys[index] = key
self.values[index] = value
self.size += 1
return
if self.keys[index] == key:
self.values[index] = value
return
raise RuntimeError("Hash table is full")
def get(self, key):
for i in range(self.capacity):
index = self._hash(key, i)
if self.keys[index] is self.EMPTY:
raise KeyError(key)
if self.keys[index] == key:
return self.values[index]
raise KeyError(key)
def remove(self, key):
for i in range(self.capacity):
index = self._hash(key, i)
if self.keys[index] is self.EMPTY:
raise KeyError(key)
if self.keys[index] == key:
self.keys[index] = self.DELETED
val = self.values[index]
self.values[index] = None
self.size -= 1
return val
raise KeyError(key)
def _resize(self):
old_keys = self.keys
old_values = self.values
self.capacity *= 2
self.keys = [self.EMPTY] * self.capacity
self.values = [None] * self.capacity
self.size = 0
for i in range(len(old_keys)):
if old_keys[i] is not self.EMPTY and old_keys[i] is not self.DELETED:
self.put(old_keys[i], old_values[i])
Java実装例
import java.util.*;
public class HashTableExample {
// JavaのHashMapの使用例
public static void hashMapExample() {
Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);
map.put("cherry", 3);
System.out.println(map.get("banana")); // 2
System.out.println(map.containsKey("apple")); // true
map.remove("cherry");
// 走査
for (Map.Entry<String, Integer> entry : map.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
}
// 簡易チェイニングハッシュテーブル
static class SimpleHashMap<K, V> {
private static final int DEFAULT_CAPACITY = 16;
private List<Map.Entry<K, V>>[] buckets;
private int size;
@SuppressWarnings("unchecked")
public SimpleHashMap() {
buckets = new LinkedList[DEFAULT_CAPACITY];
for (int i = 0; i < DEFAULT_CAPACITY; i++) {
buckets[i] = new LinkedList<>();
}
}
private int getBucketIndex(K key) {
return Math.abs(key.hashCode()) % buckets.length;
}
public void put(K key, V value) {
int index = getBucketIndex(key);
for (Map.Entry<K, V> entry : buckets[index]) {
if (entry.getKey().equals(key)) {
entry.setValue(value);
return;
}
}
buckets[index].add(new AbstractMap.SimpleEntry<>(key, value));
size++;
}
public V get(K key) {
int index = getBucketIndex(key);
for (Map.Entry<K, V> entry : buckets[index]) {
if (entry.getKey().equals(key)) return entry.getValue();
}
return null;
}
public int size() { return size; }
}
}
TypeScript実装例
class HashMap<K, V> {
private buckets: [K, V][][];
private _size = 0;
private capacity: number;
constructor(capacity = 16) {
this.capacity = capacity;
this.buckets = Array.from({ length: capacity }, () => []);
}
private hash(key: K): number {
const str = String(key);
let h = 0;
for (let i = 0; i < str.length; i++) {
h = (h * 31 + str.charCodeAt(i)) | 0;
}
return Math.abs(h) % this.capacity;
}
set(key: K, value: V): void {
const index = this.hash(key);
const bucket = this.buckets[index];
for (let i = 0; i < bucket.length; i++) {
if (bucket[i][0] === key) {
bucket[i][1] = value;
return;
}
}
bucket.push([key, value]);
this._size++;
}
get(key: K): V | undefined {
const index = this.hash(key);
for (const [k, v] of this.buckets[index]) {
if (k === key) return v;
}
return undefined;
}
has(key: K): boolean {
return this.get(key) !== undefined;
}
delete(key: K): boolean {
const index = this.hash(key);
const bucket = this.buckets[index];
for (let i = 0; i < bucket.length; i++) {
if (bucket[i][0] === key) {
bucket.splice(i, 1);
this._size--;
return true;
}
}
return false;
}
get size(): number { return this._size; }
}
4.2 グラフ（Graph）
グラフは、頂点（ノード）の集合と、頂点間を結ぶ辺（エッジ）の集合で構成されるデータ構造である。
4.2.1 グラフの種類
| 種類 | 説明 |
|---|---|
| 無向グラフ | 辺に方向がない |
| 有向グラフ | 辺に方向がある |
| 重み付きグラフ | 辺に重み（コスト）がある |
| 連結グラフ | すべての頂点間にパスが存在 |
| DAG | 有向非巡回グラフ |
4.2.2 グラフの表現方法
# 隣接行列（Adjacency Matrix）
# メモリ: O(V^2), 辺の存在確認: O(1)
class GraphMatrix:
def __init__(self, num_vertices):
self.V = num_vertices
self.matrix = [[0] * num_vertices for _ in range(num_vertices)]
def add_edge(self, u, v, weight=1):
self.matrix[u][v] = weight
self.matrix[v][u] = weight # 無向グラフの場合
def has_edge(self, u, v):
return self.matrix[u][v] != 0
def neighbors(self, v):
return [i for i in range(self.V) if self.matrix[v][i] != 0]
# 隣接リスト（Adjacency List）
# メモリ: O(V+E), 辺の存在確認: O(degree)
class GraphList:
def __init__(self, num_vertices):
self.V = num_vertices
self.adj = [[] for _ in range(num_vertices)]
def add_edge(self, u, v, weight=1):
self.adj[u].append((v, weight))
self.adj[v].append((u, weight)) # 無向グラフの場合
def neighbors(self, v):
return self.adj[v]
4.2.3 幅優先探索（BFS）
from collections import deque
def bfs(graph, start):
"""BFS: O(V + E)"""
visited = set()
queue = deque([start])
visited.add(start)
order = []
while queue:
vertex = queue.popleft()
order.append(vertex)
for neighbor, _ in graph.neighbors(vertex):
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return order
# BFSで最短経路（重みなしグラフ）
def bfs_shortest_path(graph, start, end):
visited = {start}
queue = deque([(start, [start])])
while queue:
vertex, path = queue.popleft()
if vertex == end:
return path
for neighbor, _ in graph.neighbors(vertex):
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, path + [neighbor]))
return None # パスが存在しない
Java BFS実装
import java.util.*;
public class GraphBFS {
private List<List<int[]>> adj;
private int V;
public GraphBFS(int V) {
this.V = V;
adj = new ArrayList<>();
for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
}
public void addEdge(int u, int v, int w) {
adj.get(u).add(new int[]{v, w});
adj.get(v).add(new int[]{u, w});
}
public List<Integer> bfs(int start) {
boolean[] visited = new boolean[V];
Queue<Integer> queue = new LinkedList<>();
List<Integer> order = new ArrayList<>();
visited[start] = true;
queue.offer(start);
while (!queue.isEmpty()) {
int v = queue.poll();
order.add(v);
for (int[] edge : adj.get(v)) {
if (!visited[edge[0]]) {
visited[edge[0]] = true;
queue.offer(edge[0]);
}
}
}
return order;
}
}
4.2.4 深さ優先探索（DFS）
def dfs_recursive(graph, start, visited=None):
"""再帰的DFS: O(V + E)"""
if visited is None:
visited = set()
visited.add(start)
order = [start]
for neighbor, _ in graph.neighbors(start):
if neighbor not in visited:
order.extend(dfs_recursive(graph, neighbor, visited))
return order
def dfs_iterative(graph, start):
"""反復的DFS（スタック使用）"""
visited = set()
stack = [start]
order = []
while stack:
vertex = stack.pop()
if vertex in visited:
continue
visited.add(vertex)
order.append(vertex)
for neighbor, _ in graph.neighbors(vertex):
if neighbor not in visited:
stack.append(neighbor)
return order
# DFSの応用: 閉路検出（有向グラフ）
def has_cycle_directed(graph):
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * graph.V
def dfs(v):
color[v] = GRAY
for neighbor, _ in graph.neighbors(v):
if color[neighbor] == GRAY:
return True # 閉路発見
if color[neighbor] == WHITE and dfs(neighbor):
return True
color[v] = BLACK
return False
for v in range(graph.V):
if color[v] == WHITE:
if dfs(v):
return True
return False
4.2.5 ダイクストラ法（Dijkstra's Algorithm）
重み付きグラフ（非負の重み）での単一始点最短経路を求めるアルゴリズム。
import heapq
def dijkstra(graph, start):
"""
ダイクストラ法: O((V + E) log V) （優先度付きキュー使用時）
"""
dist = [float('inf')] * graph.V
dist[start] = 0
prev = [-1] * graph.V
pq = [(0, start)] # (距離, 頂点)
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue # 既により短い経路が見つかっている
for v, weight in graph.neighbors(u):
new_dist = dist[u] + weight
if new_dist < dist[v]:
dist[v] = new_dist
prev[v] = u
heapq.heappush(pq, (new_dist, v))
return dist, prev
def reconstruct_path(prev, start, end):
"""最短経路の復元"""
path = []
current = end
while current != -1:
path.append(current)
current = prev[current]
path.reverse()
return path if path[0] == start else []
# 使用例
g = GraphList(6)
g.add_edge(0, 1, 4)
g.add_edge(0, 2, 2)
g.add_edge(1, 3, 5)
g.add_edge(2, 1, 1)
g.add_edge(2, 3, 8)
g.add_edge(3, 4, 2)
g.add_edge(4, 5, 6)
dist, prev = dijkstra(g, 0)
print(f"0から各頂点への最短距離: {dist}")
print(f"0から4への最短経路: {reconstruct_path(prev, 0, 4)}")
Java ダイクストラ実装
import java.util.*;
public class Dijkstra {
public static int[] dijkstra(List<List<int[]>> adj, int V, int start) {
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
// {距離, 頂点}
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
pq.offer(new int[]{0, start});
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int d = curr[0], u = curr[1];
if (d > dist[u]) continue;
for (int[] edge : adj.get(u)) {
int v = edge[0], w = edge[1];
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.offer(new int[]{dist[v], v});
}
}
}
return dist;
}
}
4.2.6 ベルマンフォード法（Bellman-Ford Algorithm）
負の重みを含むグラフでの単一始点最短経路を求める。負の閉路の検出も可能。
def bellman_ford(graph, start):
"""
ベルマンフォード法: O(V * E)
負の重みに対応、負の閉路を検出可能
"""
dist = [float('inf')] * graph.V
dist[start] = 0
prev = [-1] * graph.V
# V-1 回の緩和
for _ in range(graph.V - 1):
updated = False
for u in range(graph.V):
if dist[u] == float('inf'):
continue
for v, weight in graph.neighbors(u):
if dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
prev[v] = u
updated = True
if not updated:
break # 更新がなければ早期終了
# 負の閉路の検出
for u in range(graph.V):
if dist[u] == float('inf'):
continue
for v, weight in graph.neighbors(u):
if dist[u] + weight < dist[v]:
raise ValueError("負の閉路が存在します")
return dist, prev
TypeScript ベルマンフォード実装
interface Edge {
from: number;
to: number;
weight: number;
}
function bellmanFord(
V: number, edges: Edge[], start: number
): { dist: number[]; hasNegativeCycle: boolean } {
const dist = new Array(V).fill(Infinity);
dist[start] = 0;
for (let i = 0; i < V - 1; i++) {
let updated = false;
for (const { from, to, weight } of edges) {
if (dist[from] !== Infinity && dist[from] + weight < dist[to]) {
dist[to] = dist[from] + weight;
updated = true;
}
}
if (!updated) break;
}
// 負の閉路検出
for (const { from, to, weight } of edges) {
if (dist[from] !== Infinity && dist[from] + weight < dist[to]) {
return { dist, hasNegativeCycle: true };
}
}
return { dist, hasNegativeCycle: false };
}
4.2.7 最小全域木
クラスカル法（Kruskal's Algorithm）
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
return True
def kruskal(num_vertices, edges):
"""
クラスカル法: O(E log E)
edges: [(weight, u, v), ...]
"""
edges.sort() # 重みでソート
uf = UnionFind(num_vertices)
mst = []
total_weight = 0
for weight, u, v in edges:
if uf.union(u, v):
mst.append((u, v, weight))
total_weight += weight
if len(mst) == num_vertices - 1:
break
return mst, total_weight
# 使用例
edges = [(4, 0, 1), (2, 0, 2), (1, 1, 2), (5, 1, 3), (8, 2, 3), (2, 3, 4)]
mst, total = kruskal(5, edges)
print(f"MST: {mst}, 総重み: {total}")
プリム法（Prim's Algorithm）
import heapq
def prim(graph, start=0):
"""
プリム法: O((V + E) log V)
"""
visited = set()
mst = []
total_weight = 0
pq = [(0, start, -1)] # (重み, 頂点, 接続元)
while pq and len(visited) < graph.V:
weight, u, parent = heapq.heappop(pq)
if u in visited:
continue
visited.add(u)
if parent != -1:
mst.append((parent, u, weight))
total_weight += weight
for v, w in graph.neighbors(u):
if v not in visited:
heapq.heappush(pq, (w, v, u))
return mst, total_weight
4.3 最短経路アルゴリズムの比較
| アルゴリズム | 計算量 | 負の重み | 負の閉路検出 | 用途 |
|---|---|---|---|---|
| ダイクストラ | O((V+E) log V) | 不可 | 不可 | 非負の重みの最短経路 |
| ベルマンフォード | O(VE) | 可能 | 可能 | 負の重みを含む最短経路 |
| ワーシャルフロイド | O(V^3) | 可能 | 可能 | 全点対最短経路 |
ワーシャルフロイド法
def floyd_warshall(graph_matrix):
"""
ワーシャルフロイド法: O(V^3)
全頂点間の最短距離を求める
"""
V = len(graph_matrix)
dist = [row[:] for row in graph_matrix]
for k in range(V):
for i in range(V):
for j in range(V):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist
# 使用例
INF = float('inf')
graph = [
[0, 3, INF, 5],
[2, 0, INF, 4],
[INF, 1, 0, INF],
[INF, INF, 2, 0]
]
result = floyd_warshall(graph)
for row in result:
print(row)
5. ソートアルゴリズム
5.1 ソートアルゴリズム比較表
| アルゴリズム | 最良 | 平均 | 最悪 | 空間 | 安定性 | 備考 |
|---|---|---|---|---|---|---|
| バブルソート | O(n) | O(n^2) | O(n^2) | O(1) | 安定 | 教育用 |
| 選択ソート | O(n^2) | O(n^2) | O(n^2) | O(1) | 不安定 | 交換回数が少ない |
| 挿入ソート | O(n) | O(n^2) | O(n^2) | O(1) | 安定 | ほぼ整列済みに高速 |
| マージソート | O(n log n) | O(n log n) | O(n log n) | O(n) | 安定 | 安定で予測可能 |
| クイックソート | O(n log n) | O(n log n) | O(n^2) | O(log n) | 不安定 | 実用的に最速 |
| ヒープソート | O(n log n) | O(n log n) | O(n log n) | O(1) | 不安定 | インプレース |
| 基数ソート | O(nk) | O(nk) | O(nk) | O(n+k) | 安定 | 非比較ソート |
| 計数ソート | O(n+k) | O(n+k) | O(n+k) | O(k) | 安定 | 非比較ソート |
5.2 バブルソート（Bubble Sort）
隣接する要素を比較し、順序が逆なら交換する操作を繰り返す。
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped:
break # 交換がなければ早期終了
return arr
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) {
boolean swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
swapped = true;
}
}
if (!swapped) break;
}
}
function bubbleSort(arr: number[]): number[] {
const n = arr.length;
for (let i = 0; i < n; i++) {
let swapped = false;
for (let j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
swapped = true;
}
}
if (!swapped) break;
}
return arr;
}
5.3 選択ソート（Selection Sort）
未ソート部分から最小値を見つけ、先頭と交換する操作を繰り返す。
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) minIdx = j;
}
int tmp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = tmp;
}
}
function selectionSort(arr: number[]): number[] {
const n = arr.length;
for (let i = 0; i < n; i++) {
let minIdx = i;
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) minIdx = j;
}
[arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
}
return arr;
}
5.4 挿入ソート（Insertion Sort）
各要素を、ソート済み部分の適切な位置に挿入する。
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
function insertionSort(arr: number[]): number[] {
for (let i = 1; i < arr.length; i++) {
const key = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
return arr;
}
5.5 マージソート（Merge Sort）
配列を半分に分割し、再帰的にソートした後、マージする分割統治法ベースのアルゴリズム。
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= で安定ソート
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
# インプレース版マージソート
def merge_sort_inplace(arr, left=0, right=None):
if right is None:
right = len(arr) - 1
if left < right:
mid = (left + right) // 2
merge_sort_inplace(arr, left, mid)
merge_sort_inplace(arr, mid + 1, right)
merge_inplace(arr, left, mid, right)
def merge_inplace(arr, left, mid, right):
temp = []
i, j = left, mid + 1
while i <= mid and j <= right:
if arr[i] <= arr[j]:
temp.append(arr[i])
i += 1
else:
temp.append(arr[j])
j += 1
while i <= mid:
temp.append(arr[i])
i += 1
while j <= right:
temp.append(arr[j])
j += 1
for k in range(len(temp)):
arr[left + k] = temp[k]
public class MergeSort {
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
private static void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) temp[k++] = arr[i++];
else temp[k++] = arr[j++];
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
System.arraycopy(temp, 0, arr, left, temp.length);
}
}
function mergeSort(arr: number[]): number[] {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return mergeSorted(left, right);
}
function mergeSorted(left: number[], right: number[]): number[] {
const result: number[] = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) result.push(left[i++]);
else result.push(right[j++]);
}
return result.concat(left.slice(i), right.slice(j));
}
5.6 クイックソート（Quick Sort）
ピボットを選び、それより小さい要素と大きい要素に分割する分割統治法ベースのアルゴリズム。
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
# インプレース版（Lomutoパーティション）
def quick_sort_inplace(arr, low=0, high=None):
if high is None:
high = len(arr) - 1
if low < high:
pivot_idx = partition_lomuto(arr, low, high)
quick_sort_inplace(arr, low, pivot_idx - 1)
quick_sort_inplace(arr, pivot_idx + 1, high)
def partition_lomuto(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
# Hoareパーティション（交換回数が少ない）
def partition_hoare(arr, low, high):
pivot = arr[(low + high) // 2]
i, j = low - 1, high + 1
while True:
i += 1
while arr[i] < pivot:
i += 1
j -= 1
while arr[j] > pivot:
j -= 1
if i >= j:
return j
arr[i], arr[j] = arr[j], arr[i]
# 三つの中央値でピボット選択（最悪ケースの回避）
import random
def quick_sort_randomized(arr, low=0, high=None):
if high is None:
high = len(arr) - 1
if low < high:
# ランダムにピボットを選択
rand_idx = random.randint(low, high)
arr[rand_idx], arr[high] = arr[high], arr[rand_idx]
pivot_idx = partition_lomuto(arr, low, high)
quick_sort_randomized(arr, low, pivot_idx - 1)
quick_sort_randomized(arr, pivot_idx + 1, high)
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivotIdx = partition(arr, low, high);
quickSort(arr, low, pivotIdx - 1);
quickSort(arr, pivotIdx + 1, high);
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
}
}
int tmp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = tmp;
return i + 1;
}
}
function quickSort(arr: number[], low = 0, high = arr.length - 1): void {
if (low < high) {
const pivotIdx = partition(arr, low, high);
quickSort(arr, low, pivotIdx - 1);
quickSort(arr, pivotIdx + 1, high);
}
}
function partition(arr: number[], low: number, high: number): number {
const pivot = arr[high];
let i = low - 1;
for (let j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
return i + 1;
}
5.7 ヒープソート（Heap Sort）
二分ヒープを構築し、最大値を繰り返し取り出すことでソートする。
def heap_sort(arr):
n = len(arr)
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
# 最大ヒープの構築 O(n)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# 要素を一つずつ取り出す
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
heapify(arr, i, 0)
return arr
public class HeapSort {
public static void heapSort(int[] arr) {
int n = arr.length;
// 最大ヒープの構築
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 要素を一つずつ取り出す
for (int i = n - 1; i > 0; i--) {
int tmp = arr[0]; arr[0] = arr[i]; arr[i] = tmp;
heapify(arr, i, 0);
}
}
private static void heapify(int[] arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) largest = left;
if (right < n && arr[right] > arr[largest]) largest = right;
if (largest != i) {
int tmp = arr[i]; arr[i] = arr[largest]; arr[largest] = tmp;
heapify(arr, n, largest);
}
}
}
function heapSort(arr: number[]): number[] {
const n = arr.length;
function heapify(arr: number[], n: number, i: number): void {
let largest = i;
const left = 2 * i + 1;
const right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) largest = left;
if (right < n && arr[right] > arr[largest]) largest = right;
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
heapify(arr, n, largest);
}
}
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) heapify(arr, n, i);
for (let i = n - 1; i > 0; i--) {
[arr[0], arr[i]] = [arr[i], arr[0]];
heapify(arr, i, 0);
}
return arr;
}
5.8 基数ソート（Radix Sort）
各桁ごとに安定ソート（通常は計数ソート）を適用する非比較ソート。
def counting_sort_by_digit(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10
for num in arr:
index = (num // exp) % 10
count[index] += 1
for i in range(1, 10):
count[i] += count[i - 1]
for i in range(n - 1, -1, -1):
index = (arr[i] // exp) % 10
output[count[index] - 1] = arr[i]
count[index] -= 1
for i in range(n):
arr[i] = output[i]
def radix_sort(arr):
if not arr:
return arr
max_val = max(arr)
exp = 1
while max_val // exp > 0:
counting_sort_by_digit(arr, exp)
exp *= 10
return arr
5.9 計数ソート（Counting Sort）
要素の値の範囲が限定されている場合に使える非比較ソート。
def counting_sort(arr):
if not arr:
return arr
max_val = max(arr)
min_val = min(arr)
range_val = max_val - min_val + 1
count = [0] * range_val
output = [0] * len(arr)
for num in arr:
count[num - min_val] += 1
for i in range(1, range_val):
count[i] += count[i - 1]
for i in range(len(arr) - 1, -1, -1):
output[count[arr[i] - min_val] - 1] = arr[i]
count[arr[i] - min_val] -= 1
return output
public static int[] countingSort(int[] arr) {
if (arr.length == 0) return arr;
int max = Arrays.stream(arr).max().getAsInt();
int min = Arrays.stream(arr).min().getAsInt();
int range = max - min + 1;
int[] count = new int[range];
int[] output = new int[arr.length];
for (int num : arr) count[num - min]++;
for (int i = 1; i < range; i++) count[i] += count[i - 1];
for (int i = arr.length - 1; i >= 0; i--) {
output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
return output;
}
function countingSort(arr: number[]): number[] {
if (arr.length === 0) return arr;
const max = Math.max(...arr);
const min = Math.min(...arr);
const range = max - min + 1;
const count = new Array(range).fill(0);
const output = new Array(arr.length);
for (const num of arr) count[num - min]++;
for (let i = 1; i < range; i++) count[i] += count[i - 1];
for (let i = arr.length - 1; i >= 0; i--) {
output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
return output;
}
5.10 ソートの選択指針
| 状況 | 推奨アルゴリズム | 理由 |
|---|---|---|
| 小さい配列（n < 50） | 挿入ソート | オーバーヘッドが小さい |
| ほぼ整列済み | 挿入ソート | O(n) に近い |
| 安定ソートが必要 | マージソート | 安定で O(n log n) 保証 |
| メモリ制約あり | ヒープソート | O(1) 追加メモリ |
| 一般的な用途 | クイックソート | 平均的に最速 |
| 整数値の範囲が小さい | 計数ソート/基数ソート | O(n) で動作 |
6. 探索アルゴリズムと動的計画法
6.1 線形探索（Linear Search）
配列の先頭から順に要素を比較する最も単純な探索法。
def linear_search(arr, target):
"""O(n)"""
for i, val in enumerate(arr):
if val == target:
return i
return -1
public static int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) return i;
}
return -1;
}
function linearSearch(arr: number[], target: number): number {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) return i;
}
return -1;
}
6.2 二分探索（Binary Search）
ソート済み配列を半分に分割しながら探索する。
def binary_search(arr, target):
"""O(log n) — 配列はソート済みであること"""
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2 # オーバーフロー対策
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
# lower_bound: target以上の最小インデックス
def lower_bound(arr, target):
lo, hi = 0, len(arr)
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
# upper_bound: targetより大きい最小インデックス
def upper_bound(arr, target):
lo, hi = 0, len(arr)
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] <= target:
lo = mid + 1
else:
hi = mid
return lo
# 二分探索の応用: 答えに対する二分探索
def min_max_binary_search(arr, k):
"""
配列をk個のグループに分割したときの
各グループの合計の最大値を最小化する
"""
def can_split(max_sum):
count = 1
current_sum = 0
for num in arr:
if current_sum + num > max_sum:
count += 1
current_sum = num
if count > k:
return False
else:
current_sum += num
return True
lo = max(arr)
hi = sum(arr)
while lo < hi:
mid = lo + (hi - lo) // 2
if can_split(mid):
hi = mid
else:
lo = mid + 1
return lo
public class BinarySearch {
public static int binarySearch(int[] arr, int target) {
int lo = 0, hi = arr.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
public static int lowerBound(int[] arr, int target) {
int lo = 0, hi = arr.length;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (arr[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}
public static int upperBound(int[] arr, int target) {
int lo = 0, hi = arr.length;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (arr[mid] <= target) lo = mid + 1;
else hi = mid;
}
return lo;
}
}
function binarySearch(arr: number[], target: number): number {
let lo = 0, hi = arr.length - 1;
while (lo <= hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (arr[mid] === target) return mid;
else if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
function lowerBound(arr: number[], target: number): number {
let lo = 0, hi = arr.length;
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (arr[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}
6.3 動的計画法（Dynamic Programming）の基本概念
動的計画法（DP）は、重複する部分問題を持つ最適化問題を効率的に解くための手法である。
DPの2つの条件
- 最適部分構造（Optimal Substructure）: 問題の最適解がその部分問題の最適解から構成できる
- 重複部分問題（Overlapping Subproblems）: 同じ部分問題が繰り返し出現する
DPの2つのアプローチ
| アプローチ | 説明 | 方向 |
|---|---|---|
| メモ化再帰（Top-down） | 再帰 + キャッシュ | 上から下へ |
| テーブル（Bottom-up） | 小さい問題から順に解く | 下から上へ |
6.4 フィボナッチ数列（DPの入門例）
# 素朴な再帰 — O(2^n)
def fib_naive(n):
if n <= 1:
return n
return fib_naive(n - 1) + fib_naive(n - 2)
# メモ化再帰（Top-down） — O(n)
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_memo(n):
if n <= 1:
return n
return fib_memo(n - 1) + fib_memo(n - 2)
# テーブル（Bottom-up） — O(n), 空間O(n)
def fib_table(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
# 空間最適化 — O(n), 空間O(1)
def fib_optimized(n):
if n <= 1:
return n
prev2, prev1 = 0, 1
for _ in range(2, n + 1):
curr = prev1 + prev2
prev2, prev1 = prev1, curr
return prev1
6.5 ナップサック問題（Knapsack Problem）
0/1ナップサック問題
各アイテムを選ぶか選ばないかの二択。
def knapsack_01(weights, values, capacity):
"""
0/1ナップサック問題
O(n * capacity) 時間、O(n * capacity) 空間
"""
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
dp[i][w] = dp[i - 1][w] # i番目を選ばない
if weights[i - 1] <= w:
dp[i][w] = max(
dp[i][w],
dp[i - 1][w - weights[i - 1]] + values[i - 1]
)
return dp[n][capacity]
# 空間最適化版 O(capacity) 空間
def knapsack_01_optimized(weights, values, capacity):
n = len(weights)
dp = [0] * (capacity + 1)
for i in range(n):
for w in range(capacity, weights[i] - 1, -1): # 逆順!
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]
# 選んだアイテムの復元
def knapsack_01_with_items(weights, values, capacity):
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
dp[i][w] = dp[i - 1][w]
if weights[i - 1] <= w:
dp[i][w] = max(dp[i][w],
dp[i - 1][w - weights[i - 1]] + values[i - 1])
# アイテムの復元
items = []
w = capacity
for i in range(n, 0, -1):
if dp[i][w] != dp[i - 1][w]:
items.append(i - 1)
w -= weights[i - 1]
items.reverse()
return dp[n][capacity], items
# 使用例
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8
max_val, selected = knapsack_01_with_items(weights, values, capacity)
print(f"最大価値: {max_val}, 選んだアイテム: {selected}")
public class Knapsack {
public static int knapsack01(int[] weights, int[] values, int capacity) {
int n = weights.length;
int[] dp = new int[capacity + 1];
for (int i = 0; i < n; i++) {
for (int w = capacity; w >= weights[i]; w--) {
dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
}
}
return dp[capacity];
}
}
function knapsack01(
weights: number[], values: number[], capacity: number
): number {
const dp = new Array(capacity + 1).fill(0);
for (let i = 0; i < weights.length; i++) {
for (let w = capacity; w >= weights[i]; w--) {
dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
}
}
return dp[capacity];
}
6.6 最長共通部分列（LCS: Longest Common Subsequence）
2つの文字列の最長の共通部分列の長さを求める。
def lcs(s1, s2):
"""O(m * n)"""
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
# LCSの復元
result = []
i, j = m, n
while i > 0 and j > 0:
if s1[i - 1] == s2[j - 1]:
result.append(s1[i - 1])
i -= 1
j -= 1
elif dp[i - 1][j] > dp[i][j - 1]:
i -= 1
else:
j -= 1
result.reverse()
return dp[m][n], ''.join(result)
# 使用例
length, subsequence = lcs("ABCBDAB", "BDCAB")
print(f"LCS長: {length}, LCS: {subsequence}")
# LCS長: 4, LCS: BCAB
public class LCS {
public static int lcs(String s1, String s2) {
int m = s1.length(), n = s2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
}
6.7 編集距離（Edit Distance / Levenshtein Distance）
2つの文字列間の最小編集操作回数（挿入・削除・置換）を求める。
def edit_distance(s1, s2):
"""O(m * n)"""
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# ベースケース
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(
dp[i - 1][j], # 削除
dp[i][j - 1], # 挿入
dp[i - 1][j - 1] # 置換
)
return dp[m][n]
print(edit_distance("kitten", "sitting")) # 3
public static int editDistance(String s1, String s2) {
int m = s1.length(), n = s2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) dp[i][0] = i;
for (int j = 0; j <= n; j++) dp[0][j] = j;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],
Math.min(dp[i - 1][j], dp[i][j - 1]));
}
}
}
return dp[m][n];
}
function editDistance(s1: string, s2: string): number {
const m = s1.length, n = s2.length;
const dp: number[][] = Array.from(
{ length: m + 1 }, () => new Array(n + 1).fill(0)
);
for (let i = 0; i <= m; i++) dp[i][0] = i;
for (let j = 0; j <= n; j++) dp[0][j] = j;
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (s1[i - 1] === s2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + Math.min(
dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]
);
}
}
}
return dp[m][n];
}
6.8 最長増加部分列（LIS: Longest Increasing Subsequence）
# O(n^2) DP解法
def lis_dp(arr):
n = len(arr)
dp = [1] * n
for i in range(1, n):
for j in range(i):
if arr[j] < arr[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
# O(n log n) 二分探索解法
import bisect
def lis_binary_search(arr):
tails = [] # tails[i] = 長さi+1のLISの末尾の最小値
for num in arr:
pos = bisect.bisect_left(tails, num)
if pos == len(tails):
tails.append(num)
else:
tails[pos] = num
return len(tails)
print(lis_binary_search([10, 9, 2, 5, 3, 7, 101, 18])) # 4: [2, 3, 7, 101]
6.9 コイン問題（Coin Change）
def coin_change(coins, amount):
"""最小コイン数 O(n * amount)"""
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for a in range(coin, amount + 1):
dp[a] = min(dp[a], dp[a - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
def coin_change_count(coins, amount):
"""組み合わせ数 O(n * amount)"""
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
for a in range(coin, amount + 1):
dp[a] += dp[a - coin]
return dp[amount]
print(coin_change([1, 5, 10, 25], 30)) # 2 (25+5)
print(coin_change_count([1, 5, 10, 25], 30)) # 組み合わせ数
6.10 DPの典型パターンまとめ
| パターン | 例 | 漸化式の形 |
|---|---|---|
| 線形DP | フィボナッチ、階段 | dp[i] = f(dp[i-1], dp[i-2]) |
| 区間DP | 行列連鎖乗算 | dp[i][j] = f(dp[i][k], dp[k][j]) |
| ナップサック | 0/1ナップサック | dp[i][w] = f(dp[i-1][w], dp[i-1][w-wi]) |
| LCS/編集距離 | 文字列比較 | dp[i][j] = f(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) |
| 木DP | 木の最大独立集合 | dp[v] = f(dp[children(v)]) |
| ビットDP | 巡回セールスマン | dp[S][v] (S: 訪問済み集合) |
| 桁DP | N以下の条件付き数え上げ | dp[i][tight][state] |
7. 高度なアルゴリズム
7.1 貪欲法（Greedy Algorithm）
各ステップで局所的に最適な選択を行い、全体の最適解を求める手法。常に最適解が得られるわけではないが、特定の問題構造（貪欲選択性質とマトロイド構造）を持つ問題では最適解が保証される。
活動選択問題（Activity Selection）
def activity_selection(activities):
"""
終了時間が早い順に貪欲に選択
activities: [(start, end), ...]
O(n log n)
"""
activities.sort(key=lambda x: x[1])
selected = [activities[0]]
last_end = activities[0][1]
for start, end in activities[1:]:
if start >= last_end:
selected.append((start, end))
last_end = end
return selected
acts = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
print(activity_selection(acts))
# [(1, 4), (5, 7), (8, 11), (12, 16)]
ハフマン符号化（Huffman Coding）
import heapq
class HuffmanNode:
def __init__(self, char, freq):
self.char = char
self.freq = freq
self.left = None
self.right = None
def __lt__(self, other):
return self.freq < other.freq
def huffman_coding(text):
# 頻度カウント
freq = {}
for ch in text:
freq[ch] = freq.get(ch, 0) + 1
# 優先度付きキューの構築
heap = [HuffmanNode(ch, f) for ch, f in freq.items()]
heapq.heapify(heap)
# ハフマン木の構築
while len(heap) > 1:
left = heapq.heappop(heap)
right = heapq.heappop(heap)
merged = HuffmanNode(None, left.freq + right.freq)
merged.left = left
merged.right = right
heapq.heappush(heap, merged)
# 符号の生成
codes = {}
def build_codes(node, code=""):
if node is None:
return
if node.char is not None:
codes[node.char] = code if code else "0"
return
build_codes(node.left, code + "0")
build_codes(node.right, code + "1")
build_codes(heap[0])
return codes
codes = huffman_coding("abracadabra")
for ch, code in sorted(codes.items()):
print(f" '{ch}': {code}")
Java 貪欲法の例（フラクショナルナップサック）
import java.util.*;
public class GreedyKnapsack {
public static double fractionalKnapsack(
int[] weights, int[] values, int capacity) {
int n = weights.length;
Integer[] indices = new Integer[n];
for (int i = 0; i < n; i++) indices[i] = i;
// 単位重量あたりの価値でソート
Arrays.sort(indices, (a, b) ->
Double.compare(
(double) values[b] / weights[b],
(double) values[a] / weights[a]
)
);
double totalValue = 0;
int remaining = capacity;
for (int i : indices) {
if (remaining <= 0) break;
int take = Math.min(weights[i], remaining);
totalValue += (double) take / weights[i] * values[i];
remaining -= take;
}
return totalValue;
}
}
7.2 分割統治法（Divide and Conquer）
問題を小さな部分問題に分割し、それぞれを再帰的に解いて、結果を統合する手法。
最近点対問題（Closest Pair of Points）
import math
def closest_pair(points):
"""O(n log n)"""
points.sort() # x座標でソート
def distance(p1, p2):
return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)
def closest_rec(pts):
n = len(pts)
if n <= 3:
min_d = float('inf')
for i in range(n):
for j in range(i + 1, n):
min_d = min(min_d, distance(pts[i], pts[j]))
return min_d
mid = n // 2
mid_x = pts[mid][0]
d_left = closest_rec(pts[:mid])
d_right = closest_rec(pts[mid:])
d = min(d_left, d_right)
# ストリップ内の点を確認
strip = [p for p in pts if abs(p[0] - mid_x) < d]
strip.sort(key=lambda p: p[1])
for i in range(len(strip)):
j = i + 1
while j < len(strip) and strip[j][1] - strip[i][1] < d:
d = min(d, distance(strip[i], strip[j]))
j += 1
return d
return closest_rec(points)
べき乗の高速計算
def fast_power(base, exp, mod=None):
"""繰り返し二乗法: O(log n)"""
result = 1
base = base % mod if mod else base
while exp > 0:
if exp % 2 == 1:
result = (result * base) % mod if mod else result * base
exp //= 2
base = (base * base) % mod if mod else base * base
return result
# 行列のべき乗（フィボナッチ数列のO(log n)計算）
def matrix_mult(A, B, mod=None):
n = len(A)
C = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
for k in range(n):
C[i][j] += A[i][k] * B[k][j]
if mod:
C[i][j] %= mod
return C
def matrix_power(M, p, mod=None):
n = len(M)
result = [[1 if i == j else 0 for j in range(n)] for i in range(n)]
while p > 0:
if p % 2 == 1:
result = matrix_mult(result, M, mod)
M = matrix_mult(M, M, mod)
p //= 2
return result
def fib_fast(n, mod=10**9+7):
"""O(log n) でフィボナッチ数を求める"""
if n <= 1:
return n
M = [[1, 1], [1, 0]]
result = matrix_power(M, n - 1, mod)
return result[0][0]
7.3 バックトラッキング（Backtracking）
解の候補を段階的に構築し、条件を満たさない場合は直前の選択を取り消して（バックトラック）別の選択を試みる手法。
N-Queens問題
def solve_n_queens(n):
"""N-Queens問題のすべての解を求める"""
solutions = []
def backtrack(row, cols, diag1, diag2, board):
if row == n:
solutions.append([''.join(r) for r in board])
return
for col in range(n):
if col in cols or (row - col) in diag1 or (row + col) in diag2:
continue
board[row][col] = 'Q'
cols.add(col)
diag1.add(row - col)
diag2.add(row + col)
backtrack(row + 1, cols, diag1, diag2, board)
board[row][col] = '.'
cols.remove(col)
diag1.remove(row - col)
diag2.remove(row + col)
board = [['.' for _ in range(n)] for _ in range(n)]
backtrack(0, set(), set(), set(), board)
return solutions
for sol in solve_n_queens(4):
for row in sol:
print(row)
print()
数独ソルバー
def solve_sudoku(board):
"""バックトラッキングによる数独ソルバー"""
def is_valid(board, row, col, num):
for i in range(9):
if board[row][i] == num:
return False
if board[i][col] == num:
return False
box_r, box_c = 3 * (row // 3), 3 * (col // 3)
for i in range(box_r, box_r + 3):
for j in range(box_c, box_c + 3):
if board[i][j] == num:
return False
return True
def solve(board):
for i in range(9):
for j in range(9):
if board[i][j] == 0:
for num in range(1, 10):
if is_valid(board, i, j, num):
board[i][j] = num
if solve(board):
return True
board[i][j] = 0
return False
return True
solve(board)
return board
public class NQueens {
private List<List<String>> solutions = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
char[][] board = new char[n][n];
for (char[] row : board) Arrays.fill(row, '.');
backtrack(0, n, board, new boolean[n],
new boolean[2 * n], new boolean[2 * n]);
return solutions;
}
private void backtrack(int row, int n, char[][] board,
boolean[] cols, boolean[] diag1, boolean[] diag2) {
if (row == n) {
List<String> sol = new ArrayList<>();
for (char[] r : board) sol.add(new String(r));
solutions.add(sol);
return;
}
for (int col = 0; col < n; col++) {
if (cols[col] || diag1[row - col + n] || diag2[row + col])
continue;
board[row][col] = 'Q';
cols[col] = diag1[row - col + n] = diag2[row + col] = true;
backtrack(row + 1, n, board, cols, diag1, diag2);
board[row][col] = '.';
cols[col] = diag1[row - col + n] = diag2[row + col] = false;
}
}
}
7.4 Union-Find（素集合データ構造）
要素のグループ化（Union）と同じグループかの判定（Find）を効率的に行うデータ構造。
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.size = [1] * n
self.count = n # 連結成分の数
def find(self, x):
"""経路圧縮付きFind — 償却O(α(n))"""
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
"""ランクによる統合 — 償却O(α(n))"""
px, py = self.find(x), self.find(y)
if px == py:
return False
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
self.size[px] += self.size[py]
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
self.count -= 1
return True
def connected(self, x, y):
return self.find(x) == self.find(y)
def get_size(self, x):
return self.size[self.find(x)]
# 使用例: 島の数
def num_islands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
uf = UnionFind(rows * cols)
water = 0
for i in range(rows):
for j in range(cols):
if grid[i][j] == '0':
water += 1
continue
for di, dj in [(0, 1), (1, 0)]:
ni, nj = i + di, j + dj
if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1':
uf.union(i * cols + j, ni * cols + nj)
return uf.count - water
class UnionFind {
private parent: number[];
private rank: number[];
count: number;
constructor(n: number) {
this.parent = Array.from({ length: n }, (_, i) => i);
this.rank = new Array(n).fill(0);
this.count = n;
}
find(x: number): number {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]);
}
return this.parent[x];
}
union(x: number, y: number): boolean {
let px = this.find(x), py = this.find(y);
if (px === py) return false;
if (this.rank[px] < this.rank[py]) [px, py] = [py, px];
this.parent[py] = px;
if (this.rank[px] === this.rank[py]) this.rank[px]++;
this.count--;
return true;
}
connected(x: number, y: number): boolean {
return this.find(x) === this.find(y);
}
}
7.5 トポロジカルソート（Topological Sort）
有向非巡回グラフ（DAG）の頂点を、すべての辺が左から右を向くように順序付ける。
from collections import deque
def topological_sort_kahn(graph, V):
"""カーンのアルゴリズム（BFSベース）O(V + E)"""
in_degree = [0] * V
for u in range(V):
for v, _ in graph.neighbors(u):
in_degree[v] += 1
queue = deque([v for v in range(V) if in_degree[v] == 0])
result = []
while queue:
u = queue.popleft()
result.append(u)
for v, _ in graph.neighbors(u):
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)
if len(result) != V:
raise ValueError("グラフに閉路が存在します")
return result
def topological_sort_dfs(graph, V):
"""DFSベースのトポロジカルソート O(V + E)"""
visited = [False] * V
stack = []
def dfs(v):
visited[v] = True
for u, _ in graph.neighbors(v):
if not visited[u]:
dfs(u)
stack.append(v)
for v in range(V):
if not visited[v]:
dfs(v)
return stack[::-1]
public class TopologicalSort {
public static List<Integer> kahnSort(List<List<int[]>> adj, int V) {
int[] inDegree = new int[V];
for (int u = 0; u < V; u++)
for (int[] e : adj.get(u)) inDegree[e[0]]++;
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < V; i++)
if (inDegree[i] == 0) queue.offer(i);
List<Integer> result = new ArrayList<>();
while (!queue.isEmpty()) {
int u = queue.poll();
result.add(u);
for (int[] e : adj.get(u)) {
if (--inDegree[e[0]] == 0) queue.offer(e[0]);
}
}
if (result.size() != V) throw new RuntimeException("Cycle detected");
return result;
}
}
7.6 最大フロー（Maximum Flow）
ソースからシンクへの最大流量を求める問題。Ford-Fulkerson法とEdmonds-Karp法を示す。
from collections import deque
def max_flow_edmonds_karp(capacity, source, sink):
"""
Edmonds-Karp法（BFSベースのFord-Fulkerson法）
O(V * E^2)
"""
V = len(capacity)
flow = [[0] * V for _ in range(V)]
def bfs(source, sink, parent):
visited = {source}
queue = deque([source])
while queue:
u = queue.popleft()
for v in range(V):
if v not in visited and capacity[u][v] - flow[u][v] > 0:
visited.add(v)
parent[v] = u
if v == sink:
return True
queue.append(v)
return False
total_flow = 0
parent = [-1] * V
while bfs(source, sink, parent):
# 増加パスのボトルネックを見つける
path_flow = float('inf')
v = sink
while v != source:
u = parent[v]
path_flow = min(path_flow, capacity[u][v] - flow[u][v])
v = u
# フローを更新
v = sink
while v != source:
u = parent[v]
flow[u][v] += path_flow
flow[v][u] -= path_flow
v = u
total_flow += path_flow
parent = [-1] * V
return total_flow
# 使用例
capacity = [
[0, 16, 13, 0, 0, 0],
[0, 0, 10, 12, 0, 0],
[0, 4, 0, 0, 14, 0],
[0, 0, 9, 0, 0, 20],
[0, 0, 0, 7, 0, 4],
[0, 0, 0, 0, 0, 0]
]
print(f"最大フロー: {max_flow_edmonds_karp(capacity, 0, 5)}") # 23
7.7 文字列アルゴリズム
KMP法（Knuth-Morris-Pratt）
def kmp_search(text, pattern):
"""
KMP法: O(n + m)
"""
def build_failure(pattern):
m = len(pattern)
failure = [0] * m
j = 0
for i in range(1, m):
while j > 0 and pattern[i] != pattern[j]:
j = failure[j - 1]
if pattern[i] == pattern[j]:
j += 1
failure[i] = j
return failure
failure = build_failure(pattern)
n, m = len(text), len(pattern)
j = 0
matches = []
for i in range(n):
while j > 0 and text[i] != pattern[j]:
j = failure[j - 1]
if text[i] == pattern[j]:
j += 1
if j == m:
matches.append(i - m + 1)
j = failure[j - 1]
return matches
print(kmp_search("ababcababcabc", "ababc")) # [0, 5]
Rabin-Karp法
def rabin_karp(text, pattern, base=256, mod=10**9+7):
"""
Rabin-Karp法: O(n + m) 平均, O(nm) 最悪
"""
n, m = len(text), len(pattern)
if m > n:
return []
# パターンのハッシュ
p_hash = 0
t_hash = 0
h = pow(base, m - 1, mod)
for i in range(m):
p_hash = (p_hash * base + ord(pattern[i])) % mod
t_hash = (t_hash * base + ord(text[i])) % mod
matches = []
for i in range(n - m + 1):
if p_hash == t_hash:
if text[i:i+m] == pattern: # 本当に一致するか確認
matches.append(i)
if i < n - m:
t_hash = ((t_hash - ord(text[i]) * h) * base + ord(text[i + m])) % mod
t_hash = (t_hash + mod) % mod
return matches
print(rabin_karp("ababcababcabc", "ababc")) # [0, 5]
public class KMP {
public static List<Integer> search(String text, String pattern) {
int[] failure = buildFailure(pattern);
List<Integer> matches = new ArrayList<>();
int j = 0;
for (int i = 0; i < text.length(); i++) {
while (j > 0 && text.charAt(i) != pattern.charAt(j))
j = failure[j - 1];
if (text.charAt(i) == pattern.charAt(j)) j++;
if (j == pattern.length()) {
matches.add(i - pattern.length() + 1);
j = failure[j - 1];
}
}
return matches;
}
private static int[] buildFailure(String pattern) {
int[] f = new int[pattern.length()];
int j = 0;
for (int i = 1; i < pattern.length(); i++) {
while (j > 0 && pattern.charAt(i) != pattern.charAt(j))
j = f[j - 1];
if (pattern.charAt(i) == pattern.charAt(j)) j++;
f[i] = j;
}
return f;
}
}
7.8 幾何アルゴリズム基礎
凸包（Convex Hull）— Graham Scan法
def convex_hull(points):
"""Graham Scan法: O(n log n)"""
def cross(o, a, b):
return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
points = sorted(set(points))
if len(points) <= 1:
return points
# 下側凸包
lower = []
for p in points:
while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
lower.pop()
lower.append(p)
# 上側凸包
upper = []
for p in reversed(points):
while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
upper.pop()
upper.append(p)
return lower[:-1] + upper[:-1]
points = [(0, 0), (1, 1), (2, 2), (4, 4), (0, 3), (1, 2), (3, 1), (3, 3)]
hull = convex_hull(points)
print(f"凸包の頂点: {hull}")
線分の交差判定
def on_segment(p, q, r):
return (min(p[0], r[0]) <= q[0] <= max(p[0], r[0]) and
min(p[1], r[1]) <= q[1] <= max(p[1], r[1]))
def orientation(p, q, r):
val = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])
if val == 0:
return 0 # 同一直線上
return 1 if val > 0 else 2 # 時計回り / 反時計回り
def segments_intersect(p1, q1, p2, q2):
"""2つの線分が交差するかを判定 O(1)"""
o1 = orientation(p1, q1, p2)
o2 = orientation(p1, q1, q2)
o3 = orientation(p2, q2, p1)
o4 = orientation(p2, q2, q1)
if o1 != o2 and o3 != o4:
return True
if o1 == 0 and on_segment(p1, p2, q1): return True
if o2 == 0 and on_segment(p1, q2, q1): return True
if o3 == 0 and on_segment(p2, p1, q2): return True
if o4 == 0 and on_segment(p2, q1, q2): return True
return False
8. 実践ガイド
8.1 競技プログラミングでの活用
よく出るアルゴリズムと出題頻度
| アルゴリズム | 出題頻度 | 典型的な問題 |
|---|---|---|
| 全探索・BFS/DFS | 非常に高 | 迷路探索、連結成分 |
| 二分探索 | 非常に高 | 答えに対する二分探索 |
| 動的計画法 | 非常に高 | ナップサック、LCS |
| 貪欲法 | 高 | 区間スケジューリング |
| Union-Find | 高 | 連結判定、クラスカル |
| セグメント木/BIT | 中 | 区間クエリ |
| 最短経路 | 中 | ダイクストラ、ワーシャルフロイド |
| 文字列アルゴリズム | 中 | パターンマッチング |
| 最大フロー | 低 | 二部マッチング |
競技プログラミング用テンプレート（Python）
import sys
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from functools import lru_cache
from itertools import permutations, combinations, accumulate
input = sys.stdin.readline
INF = float('inf')
MOD = 10**9 + 7
def solve():
n = int(input())
arr = list(map(int, input().split()))
# ここに解法を書く
solve()
Binary Indexed Tree（BIT / Fenwick Tree）
競技プログラミングで頻出のデータ構造。
class BIT:
"""Binary Indexed Tree (Fenwick Tree)
点更新・区間和クエリ O(log n)
"""
def __init__(self, n):
self.n = n
self.tree = [0] * (n + 1)
def update(self, i, delta):
"""i番目の要素にdeltaを加算 (1-indexed)"""
while i <= self.n:
self.tree[i] += delta
i += i & (-i)
def query(self, i):
"""[1, i] の区間和を求める"""
s = 0
while i > 0:
s += self.tree[i]
i -= i & (-i)
return s
def range_query(self, l, r):
"""[l, r] の区間和を求める"""
return self.query(r) - self.query(l - 1)
# 使用例: 転倒数（inversion count）
def count_inversions(arr):
n = len(arr)
# 座標圧縮
sorted_unique = sorted(set(arr))
rank = {v: i + 1 for i, v in enumerate(sorted_unique)}
bit = BIT(len(sorted_unique))
inversions = 0
for i in range(n - 1, -1, -1):
inversions += bit.query(rank[arr[i]] - 1)
bit.update(rank[arr[i]], 1)
return inversions
print(count_inversions([3, 1, 2, 5, 4])) # 3
public class BIT {
private int[] tree;
private int n;
public BIT(int n) {
this.n = n;
this.tree = new int[n + 1];
}
public void update(int i, int delta) {
for (; i <= n; i += i & (-i))
tree[i] += delta;
}
public int query(int i) {
int sum = 0;
for (; i > 0; i -= i & (-i))
sum += tree[i];
return sum;
}
public int rangeQuery(int l, int r) {
return query(r) - query(l - 1);
}
}
8.2 実務でのデータ構造選択指針
要件に基づくデータ構造の選択
| 要件 | 推奨データ構造 | 理由 |
|---|---|---|
| キーバリューの高速検索 | ハッシュマップ | O(1) 平均 |
| ソート済みデータの管理 | 平衡BST / TreeMap | O(log n) |
| 頻繁な先頭/末尾の操作 | デック / 双方向連結リスト | O(1) |
| 優先度ベースの処理 | ヒープ / 優先度付きキュー | O(log n) |
| 集合の統合・判定 | Union-Find | 償却O(α(n)) |
| 前方一致検索 | トライ木 | O(m) |
| 区間の集約クエリ | セグメント木 / BIT | O(log n) |
| グラフの表現 | 隣接リスト | 疎グラフに効率的 |
| 高速な挿入/削除 | 連結リスト | O(1) |
言語標準ライブラリの対応表
| データ構造 | Python | Java | TypeScript/JS |
|---|---|---|---|
| 動的配列 | list | ArrayList | Array |
| 連結リスト | collections.deque | LinkedList | ― (自作) |
| スタック | list (append/pop) | Deque (ArrayDeque) | Array (push/pop) |
| キュー | collections.deque | Queue (LinkedList) | ― (自作) |
| ハッシュマップ | dict | HashMap | Map |
| ハッシュセット | set | HashSet | Set |
| ソート済みマップ | ― (sortedcontainers) | TreeMap | ― (自作) |
| ソート済みセット | ― (sortedcontainers) | TreeSet | ― (自作) |
| 優先度付きキュー | heapq | PriorityQueue | ― (自作) |
| デック | collections.deque | ArrayDeque | ― (自作) |
Pythonでの効率的なデータ構造の使い方
# dict（ハッシュマップ）の活用
from collections import defaultdict, Counter, OrderedDict
# defaultdict: 存在しないキーにデフォルト値
graph = defaultdict(list)
graph[0].append(1)
graph[0].append(2)
# Counter: 要素の出現回数
counter = Counter("abracadabra")
print(counter.most_common(3)) # [('a', 5), ('b', 2), ('r', 2)]
# heapq: 優先度付きキュー（最小ヒープ）
import heapq
heap = []
heapq.heappush(heap, (3, 'low'))
heapq.heappush(heap, (1, 'high'))
heapq.heappush(heap, (2, 'medium'))
print(heapq.heappop(heap)) # (1, 'high')
# bisect: ソート済みリストへの二分探索挿入
import bisect
sorted_list = [1, 3, 5, 7, 9]
bisect.insort(sorted_list, 4)
print(sorted_list) # [1, 3, 4, 5, 7, 9]
# deque: 両端キュー（BFS等に最適）
from collections import deque
dq = deque([1, 2, 3])
dq.appendleft(0) # O(1)
dq.append(4) # O(1)
dq.popleft() # O(1)
# itertools: 組み合わせ列挙
from itertools import combinations, permutations, product
list(combinations([1, 2, 3], 2)) # [(1,2), (1,3), (2,3)]
list(permutations([1, 2, 3], 2)) # [(1,2), (1,3), (2,1), ...]
8.3 計算量の見積もり方
制約からアルゴリズムを逆算する
一般的なオンラインジャッジの制限時間（1〜2秒）に対し、Pythonでは約 10^7 程度の操作が目安である（C++/Javaは 10^8〜10^9）。
| 入力サイズ N | 許容される計算量 | 適用可能なアルゴリズム例 |
|---|---|---|
| N ≦ 10 | O(N!) | 全順列探索 |
| N ≦ 20 | O(2^N) | ビット全探索 |
| N ≦ 500 | O(N^3) | ワーシャルフロイド |
| N ≦ 5,000 | O(N^2) | 二重ループDP |
| N ≦ 500,000 | O(N log N) | ソート、セグメント木 |
| N ≦ 10,000,000 | O(N) | 線形走査、カウンティング |
| N ≦ 10^18 | O(log N) | 二分探索、行列累乗 |
計算量を改善する一般的なテクニック
# テクニック1: 累積和で区間合計を O(1) に
def prefix_sum_example(arr, queries):
# 前処理 O(n)
prefix = [0] * (len(arr) + 1)
for i in range(len(arr)):
prefix[i + 1] = prefix[i] + arr[i]
# 各クエリ O(1)
results = []
for l, r in queries:
results.append(prefix[r + 1] - prefix[l])
return results
# テクニック2: 座標圧縮
def coordinate_compression(arr):
sorted_unique = sorted(set(arr))
mapping = {v: i for i, v in enumerate(sorted_unique)}
return [mapping[x] for x in arr]
# テクニック3: 二つのポインタ（Two Pointers）
def two_sum_sorted(arr, target):
"""ソート済み配列での2数の和 O(n)"""
left, right = 0, len(arr) - 1
while left < right:
s = arr[left] + arr[right]
if s == target:
return (left, right)
elif s < target:
left += 1
else:
right -= 1
return None
# テクニック4: しゃくとり法（Sliding Window）
def max_sum_subarray(arr, k):
"""サイズkの部分配列の最大合計 O(n)"""
window_sum = sum(arr[:k])
max_sum = window_sum
for i in range(k, len(arr)):
window_sum += arr[i] - arr[i - k]
max_sum = max(max_sum, window_sum)
return max_sum
def longest_substring_no_repeat(s):
"""重複文字なしの最長部分文字列 O(n)"""
char_set = set()
left = 0
max_len = 0
for right in range(len(s)):
while s[right] in char_set:
char_set.remove(s[left])
left += 1
char_set.add(s[right])
max_len = max(max_len, right - left + 1)
return max_len
8.4 面接対策としてのアルゴリズム
頻出トピックと代表問題
| トピック | 代表的な問題 | 難易度 |
|---|---|---|
| 配列/文字列 | Two Sum, 最大部分配列和 | Easy〜Medium |
| 連結リスト | 逆転、環検出、マージ | Easy〜Medium |
| スタック/キュー | 有効な括弧、最小スタック | Easy |
| 二分探索 | 回転配列の探索 | Medium |
| ツリー | LCA、直径、シリアライズ | Medium〜Hard |
| グラフ | 島の数、コースの前提条件 | Medium |
| DP | コイン問題、ロングパス | Medium〜Hard |
| バックトラッキング | N-Queens、組み合わせの和 | Medium |
面接での問題解法ステップ
- 問題の理解: 例を使って条件を確認
- ブルートフォース: まず愚直な解法を考える
- 最適化: より効率的なアルゴリズムへ改善
- 実装: 明確で読みやすいコードを書く
- テスト: エッジケースを含むテストケースで検証
# 面接頻出: 最大部分配列和（Kadane's Algorithm）
def max_subarray_sum(nums):
"""O(n) 時間, O(1) 空間"""
max_sum = current_sum = nums[0]
for num in nums[1:]:
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)
return max_sum
# 面接頻出: 連結リストの環検出（Floyd's Cycle Detection）
def has_cycle(head):
"""O(n) 時間, O(1) 空間"""
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
# 面接頻出: LRU Cache
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key: int) -> int:
if key not in self.cache:
return -1
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key: int, value: int) -> None:
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False)
// LRU Cache in Java
import java.util.LinkedHashMap;
import java.util.Map;
public class LRUCache extends LinkedHashMap<Integer, Integer> {
private final int capacity;
public LRUCache(int capacity) {
super(capacity, 0.75f, true);
this.capacity = capacity;
}
public int get(int key) {
return super.getOrDefault(key, -1);
}
public void put(int key, int value) {
super.put(key, value);
}
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
}
// LRU Cache in TypeScript
class LRUCache {
private capacity: number;
private cache: Map<number, number>;
constructor(capacity: number) {
this.capacity = capacity;
this.cache = new Map();
}
get(key: number): number {
if (!this.cache.has(key)) return -1;
const val = this.cache.get(key)!;
this.cache.delete(key);
this.cache.set(key, val);
return val;
}
put(key: number, value: number): void {
if (this.cache.has(key)) this.cache.delete(key);
this.cache.set(key, value);
if (this.cache.size > this.capacity) {
const firstKey = this.cache.keys().next().value;
this.cache.delete(firstKey);
}
}
}
9. まとめと参考文献
9.1 全体の振り返り
本記事では、アルゴリズムとデータ構造の基礎から応用までを体系的に解説した。
学習ロードマップ
レベル1（初級）
├── 配列、連結リスト、スタック、キュー
├── 線形探索、二分探索
├── バブルソート、挿入ソート
└── Big-O記法の理解
レベル2（中級）
├── ハッシュテーブル、ツリー（BST、AVL）
├── マージソート、クイックソート、ヒープソート
├── BFS、DFS
├── 動的計画法の基本
└── 二分探索の応用
レベル3（上級）
├── セグメント木、BIT、トライ木
├── ダイクストラ、ベルマンフォード
├── Union-Find、トポロジカルソート
├── 高度なDP（ビットDP、桁DP）
└── 文字列アルゴリズム（KMP、Rabin-Karp）
レベル4（発展）
├── 赤黒木、B木
├── 最大フロー、最小カット
├── 幾何アルゴリズム
├── 高速フーリエ変換（FFT）
└── 永続データ構造
データ構造の計算量一覧
| データ構造 | アクセス | 探索 | 挿入 | 削除 | 備考 |
|---|---|---|---|---|---|
| 配列 | O(1) | O(n) | O(n) | O(n) | ランダムアクセス |
| 連結リスト | O(n) | O(n) | O(1) | O(1) | 参照がある場合 |
| スタック | O(n) | O(n) | O(1) | O(1) | LIFO |
| キュー | O(n) | O(n) | O(1) | O(1) | FIFO |
| ハッシュテーブル | N/A | O(1)* | O(1)* | O(1)* | *平均 |
| 二分探索木 | O(log n)* | O(log n)* | O(log n)* | O(log n)* | *平衡時 |
| AVL木 | O(log n) | O(log n) | O(log n) | O(log n) | 常にバランス |
| 赤黒木 | O(log n) | O(log n) | O(log n) | O(log n) | 回転が少ない |
| B木 | O(log n) | O(log n) | O(log n) | O(log n) | ディスク最適 |
| ヒープ | O(1)min/max | O(n) | O(log n) | O(log n) | 最小/最大値 |
| トライ木 | - | O(m) | O(m) | O(m) | 文字列長m |
| セグメント木 | - | O(log n) | O(log n) | - | 区間クエリ |
ソートアルゴリズムの計算量一覧
| アルゴリズム | 最良 | 平均 | 最悪 | 空間 | 安定 |
|---|---|---|---|---|---|
| バブルソート | O(n) | O(n^2) | O(n^2) | O(1) | Yes |
| 選択ソート | O(n^2) | O(n^2) | O(n^2) | O(1) | No |
| 挿入ソート | O(n) | O(n^2) | O(n^2) | O(1) | Yes |
| マージソート | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| クイックソート | O(n log n) | O(n log n) | O(n^2) | O(log n) | No |
| ヒープソート | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| 計数ソート | O(n+k) | O(n+k) | O(n+k) | O(k) | Yes |
| 基数ソート | O(nk) | O(nk) | O(nk) | O(n+k) | Yes |
9.2 参考文献・学習リソース
書籍
- Introduction to Algorithms (CLRS) — Cormen, Leiserson, Rivest, Stein
- アルゴリズムの教科書として世界的に最も有名な一冊
- アルゴリズムイントロダクション — 上記の日本語訳
- プログラミングコンテストチャレンジブック（蟻本） — 秋葉拓哉、岩田陽一、北川宜稔
- 日本の競技プログラマーのバイブル
- Algorithm Design — Kleinberg, Tardos
- アルゴリズム設計のテクニックに焦点
- Competitive Programming 3 — Steven Halim, Felix Halim
- 競技プログラミング向けの実践的な一冊
オンライン学習リソース
| リソース | URL | 特徴 |
|---|---|---|
| LeetCode | leetcode.com | 面接対策問題集 |
| AtCoder | atcoder.jp | 日本の競技プログラミング |
| Codeforces | codeforces.com | 国際的な競技プログラミング |
| Visualgo | visualgo.net | アルゴリズムの可視化 |
| GeeksforGeeks | geeksforgeeks.org | アルゴリズム解説 |
学習のコツ
- 理解してから書く: アルゴリズムの動作を紙上でトレースしてから実装する
- 計算量を常に意識: すべてのアルゴリズムについて時間・空間計算量を把握する
- 手を動かす: 理論だけでなく、実際にコードを書いて動作を確認する
- 問題を解く: LeetCodeやAtCoderで多くの問題を解き、パターンを身につける
- 復習する: 一度解いた問題を時間を空けて再度解く
本記事は、アルゴリズムとデータ構造の主要なトピックを網羅的に解説した。各概念について理論的な説明と実践的なコード例を併せて提示したため、初学者から中上級者まで幅広い読者の学習に役立てていただければ幸いである。