アルゴリズム＆データ構造 完全攻略：計算量分析からAI/MLアルゴリズムまで

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

T(n) = aT(n/b) + f(n)

# 赤黒木の回転 - 左回転(Left Rotation)の概念
#
#     x                y
#    / \    →         / \
#   a   y            x   c
#      / \          / \
#     b   c        a   b
#
def left_rotate(tree, x):
    y = x.right          # yはxの右の子
    x.right = y.left     # yの左部分木をxの右へ
    if y.left != tree.NIL:
        y.left.parent = x
    y.parent = x.parent  # xの親をyの親に
    if x.parent == tree.NIL:
        tree.root = y
    elif x == x.parent.left:
        x.parent.left = y
    else:
        x.parent.right = y
    y.left = x           # xをyの左の子に
    x.parent = y

import heapq

# Dijkstra法のための最小ヒープ活用
def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    # (距離, ノード) 形式でヒープに格納
    heap = [(0, start)]
    visited = set()

    while heap:
        dist, node = heapq.heappop(heap)
        if node in visited:
            continue
        visited.add(node)

        for neighbor, weight in graph[node]:
            new_dist = dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heapq.heappush(heap, (new_dist, neighbor))

    return distances

# 使用例
graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('C', 2), ('D', 5)],
    'C': [('D', 1)],
    'D': []
}
print(dijkstra(graph, 'A'))
# {'A': 0, 'B': 1, 'C': 3, 'D': 4}

def floyd_warshall(n, edges):
    INF = float('inf')
    # dist[i][j] = iからjへの最短距離
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w

    for k in range(n):          # 経由ノード
        for i in range(n):      # 出発ノード
            for j in range(n):  # 到着ノード
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

from collections import deque

def topological_sort(n, edges):
    indegree = [0] * n
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1

    queue = deque([i for i in range(n) if indegree[i] == 0])
    result = []
    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    return result if len(result) == n else []  # 閉路あり → 空リスト

def lcs(s1, s2):
    m, n = len(s1), len(s2)
    # dp[i][j] = s1[:i] と s2[:j] の LCS の長さ
    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])

    # 2Dテーブルの可視化 (s1="ABCD", s2="ACBD"):
    #     ""  A  C  B  D
    #  ""  0  0  0  0  0
    #  A   0  1  1  1  1
    #  B   0  1  1  2  2
    #  C   0  1  2  2  2
    #  D   0  1  2  2  3  <- LCS の長さ = 3 ("ABD" または "ACD")
    return dp[m][n]

def knapsack(weights, values, capacity):
    n = len(weights)
    # dp[i][w] = i番目のアイテムまで考慮し、容量wのときの最大価値
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            # アイテム i を含まない場合
            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]

class SegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        self.build(arr, 0, 0, self.n - 1)

    def build(self, arr, node, start, end):
        if start == end:
            self.tree[node] = arr[start]
        else:
            mid = (start + end) // 2
            self.build(arr, 2*node+1, start, mid)
            self.build(arr, 2*node+2, mid+1, end)
            self.tree[node] = self.tree[2*node+1] + self.tree[2*node+2]

    def query(self, node, start, end, l, r):
        if r < start or end < l:
            return 0  # 範囲外
        if l <= start and end <= r:
            return self.tree[node]  # 完全包含
        mid = (start + end) // 2
        left = self.query(2*node+1, start, mid, l, r)
        right = self.query(2*node+2, mid+1, end, l, r)
        return left + right

    def update(self, node, start, end, idx, val):
        if start == end:
            self.tree[node] = val
        else:
            mid = (start + end) // 2
            if idx <= mid:
                self.update(2*node+1, start, mid, idx, val)
            else:
                self.update(2*node+2, mid+1, end, idx, val)
            self.tree[node] = self.tree[2*node+1] + self.tree[2*node+2]

class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def update(self, i, delta):
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)  # 最下位ビットを加算

    def query(self, i):
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & (-i)  # 最下位ビットを除去
        return total

    def range_query(self, l, r):
        return self.query(r) - self.query(l - 1)

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        # 経路圧縮（Path Compression）
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False  # すでに同じ集合
        # ランクによる合併（Union by Rank）
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        return True
# 経路圧縮 + ランク → 事実上 O(α(n)) ≈ O(1)（逆アッカーマン関数）

def kmp_search(text, pattern):
    def build_lps(pattern):
        lps = [0] * len(pattern)
        length, i = 0, 1
        while i < len(pattern):
            if pattern[i] == pattern[length]:
                length += 1
                lps[i] = length
                i += 1
            elif length:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
        return lps

    lps = build_lps(pattern)
    i = j = 0
    results = []
    while i < len(text):
        if text[i] == pattern[j]:
            i += 1; j += 1
        if j == len(pattern):
            results.append(i - j)
            j = lps[j - 1]
        elif i < len(text) and text[i] != pattern[j]:
            j = lps[j - 1] if j else (i := i + 1) and 0
    return results

class KDNode:
    def __init__(self, point, left=None, right=None):
        self.point = point
        self.left = left
        self.right = right

def build_kd_tree(points, depth=0):
    if not points:
        return None
    k = len(points[0])
    axis = depth % k
    sorted_points = sorted(points, key=lambda p: p[axis])
    mid = len(sorted_points) // 2
    return KDNode(
        point=sorted_points[mid],
        left=build_kd_tree(sorted_points[:mid], depth + 1),
        right=build_kd_tree(sorted_points[mid+1:], depth + 1)
    )

def nearest_neighbor(root, query, depth=0, best=None):
    if root is None:
        return best
    k = len(query)
    axis = depth % k

    dist = sum((q - p) ** 2 for q, p in zip(query, root.point)) ** 0.5
    if best is None or dist < best[0]:
        best = (dist, root.point)

    # クエリポイントと分割超平面を比較
    diff = query[axis] - root.point[axis]
    close, away = (root.left, root.right) if diff <= 0 else (root.right, root.left)

    best = nearest_neighbor(close, query, depth + 1, best)
    # 反対側のサブツリーも探索が必要か確認
    if abs(diff) < best[0]:
        best = nearest_neighbor(away, query, depth + 1, best)
    return best

ビーム幅 k=2、各トークンで上位2つを保持：
ステップ1: [A(0.6), B(0.4)]
ステップ2: [AA(0.36), AB(0.24), BA(0.28), BB(0.16)] -> 上位2: [AA, BA]
ステップ3: [AAX, AAY, BAX, BAY] -> 上位2を保持...

f(n) = g(n) + h(n)
g(n) = スタートから現在のノードまでの実際のコスト
h(n) = 現在のノードからゴールまでの推定コスト（許容ヒューリスティック）

# ソート済み配列で合計が target になる2つの数を見つける
def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        current = arr[left] + arr[right]
        if current == target:
            return (left, right)
        elif current < target:
            left += 1
        else:
            right -= 1
    return None
# 時間 O(n)、空間 O(1)

# 長さkの部分配列の最大和
def max_subarray_sum(arr, k):
    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
# 時間 O(n)、空間 O(1)

# N-Queens問題
def solve_n_queens(n):
    results = []
    board = [-1] * n

    def is_valid(row, col):
        for r in range(row):
            if board[r] == col:
                return False
            if abs(board[r] - col) == abs(r - row):
                return False
        return True

    def backtrack(row):
        if row == n:
            results.append(board[:])
            return
        for col in range(n):
            if is_valid(row, col):
                board[row] = col
                backtrack(row + 1)
                board[row] = -1  # バックトラック

    backtrack(0)
    return results