データ構造とアルゴリズム

1. [データ構造] 配列 / 文字列（Array / String）

各言語のライブラリ

静的配列
- C++ ... std::array
- Java ... Array
- Go ... Array
動的配列
- C++ ... std::vector
- Java ... ArrayList
- Go ... Slice
- Python ... list
- Ruby ... Array

データ構造の説明

要素を1列に並べ、各要素に容易にアクセスできるようにしたデータ構造。
静的配列と動的配列の２種類に分けられる。
静的配列（固定長配列 / Static Array / Fixed Length Array）
- 決まった要素数しか格納できない配列。
動的配列（可変長配列 / 配列リスト / Dynamic Array / Variable Length Array / Array List）
- 要素数によって自動的にサイズが拡張される配列。
- メモリが許す限り、要素の末尾追加や途中挿入がいくらでもできる。
得意
- ランダムアクセス（インデックスを指定してのアクセス） O(1)
苦手
- 要素xを要素yの直後に挿入する O(n)
  1. 要素yの検索を線型探索法で行う操作に最悪 O(n)
  2. 要素xを挿入するために要素yより右半分の要素をずらす操作に最悪 O(n)
- 要素xを削除する O(n)
  1. 要素xの検索を線型探索法で行う操作に最悪 O(n)
  2. 要素xを削除し要素xより右半分の要素をずらす操作に最悪 O(n)
Two Pointers
- 通常、配列の先頭の要素から末尾の要素を探索するとき、1つのポインタを用いるが、2つのポインタを同時に用いる方法を Two Pointers と呼ぶ。

時間計算量 O(1) で文字列を反転する関数を Two Pointers で実装する例:

C++での実装

void reverseString(vector<char>& s) {
    int n = s.size();
    int i = 0; // 先頭から探索するポインタ
    int j = n-1; // 末尾から探索するポインタ

    while(i<=j){
        // 左半分の部分文字列の文字と、右半分の部分文字列の文字を同時にスワップする
        char temp = s[i];
        s[i] = s[j];
        s[j] = temp;
        // 先頭から探索するポインタは右へ
        i++;
        // 末尾から探索するポインタは左へ
        j--;
    }
}

https://leetcode.com/problems/reverse-string/description/

操作と計算量

要素の操作	平均時間計算量
インデックスでのアクセス	O(1)
要素の検索	O(n)
要素の挿入	O(n)
要素の末尾への挿入	O(1)
要素の削除	O(n)

2. [データ構造] 連結リスト（Linked List）

各言語のライブラリ

C++ ... std::list
Java ... LinkedList
Go ... list

データ構造の説明

各要素をポインタで1列に繋いだデータ構造。
- 各ノードは次のノードへのポインタを持つ。
- 実用上は配列が用いられることが多いが、連結リストはデータ構造の部品として活用されることが多い。
得意（主に配列が苦手としていた操作）
- 要素 x を要素 y の直後に挿入する O(1)
- 要素 x を削除する O(1)
  ※ 挿入時の要素 y 、または削除時の要素 x を、「探索」する必要がある場合には O(n) となる。
苦手
- ランダムアクセス O(n)
  - 連結リストは、各ノードが全体で何番目かという情報を管理しないため、先頭から順に i 個のノードを辿っていく必要がある。
ノード
- 連結リストを構成する1つ1つの要素。
番兵（ダミーノード / sentinel node / dummy node）
- 挿入・削除操作を簡潔にするため、先頭や最後尾に置かれる データを持たないノード。
- 例えば、新しいノードをリストの先頭に挿入する操作では、番兵の次のノードが、実際のリストの先頭として機能する。
単方向連結リスト（Singly Linked List）
- 各ノードが、次のノードへのポインタ *next のみを持つ。
双方向連結リスト（Doubly Linked List）
- 各ノードが、次のノードへのポインタ *next と前のノードへのポインタ *prev を持つ。
単方向循環連結リスト（Singly Circular Linked List）
- 末尾のノードが、次のノードへのポインタとして（ nil ではなく）先頭のノードのポインタを持つ単方向連結リスト。
双方向循環連結リスト（Doubly Circular Linked List）
- 末尾のノードが、次のノードへのポインタとして（ nil ではなく）先頭のノードのポインタを持ち、
- 先頭のノードが、前のノードへのポインタとして（ nil ではなく）末尾のノードのポインタを持つ双方向連結リスト。

連結リストの挿入:

連結リストの削除:

双方向連結リストの実装:

C++での実装

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// ノードを表す構造体 Node
// 自分自身（ Node 型）へのポインタをメンバに持つ、自己参照構造体
struct Node {
  Node *prev, *next;
  string name; // ノードに付属している値

  // コンストラクタ
  Node(string name_ = "") : prev(NULL), next(NULL), name(name_) {}
};

// 双方向連結リストを表す構造体
struct LinkedList {
  Node *head, *tail; // リストの先頭と末尾へのポインタ

  // コンストラクタ
  LinkedList() {
    head = new Node(); // 先頭のダミーノード（番兵）
    tail = new Node(); // 末尾のダミーノード（番兵）
    head->next = tail;
    tail->prev = head;
  }

  // デストラクタ
  ~LinkedList() {
    Node *cur = head;
    while (cur != NULL) {
      Node *next = cur->next;
      delete cur;
      cur = next;
    }
  }

  // 連結リストを出力する
  void display() {
    Node *cur = head->next; // 先頭から出力していく
    while (cur != tail) {
      cout << cur->name << " -> ";
      cur = cur->next;
    }
    cout << "NIL" << endl;
  }

  // 新しいノードをリストの末尾に挿入
  void insert(Node *node) {
    node->prev = tail->prev; // 新しいノードの前のノードへのポインタを、末尾のダミーノードの前のノードへのポインタに繋ぎかえる
    node->next = tail; // 新しいノードの次のノードへのポインタを、末尾のダミーノードに繋ぎかえる
    tail->prev->next = node; // 末尾のダミーノードの前のノードの次のノードへのポインタを、新しいノードに繋ぎかえる
    tail->prev = node; // 末尾のダミーノードの前のノードへのポインタを、新しいノードに繋ぎかえる
  }

  // ノードをリストから削除
  void delete(Node *node) {
    node->prev->next = node->next; // 削除するノードの前のノードの次のノードへのポインタを、削除するノードの次のノードに繋ぎかえる
    node->next->prev = node->prev; // 削除するノードの次のノードの前のノードへのポインタを、削除するノードの前のノードに繋ぎかえる
    delete node;
  }

  // 特定の名前を持つノードを検索
  Node* find(string name) {
    Node *cur = head->next; // 先頭から検索していく
    while (cur != tail) {
      if (cur->name == name) return cur;
      cur = cur->next;
    }
    return NULL;
  }
};

int main() {
  LinkedList list; // リストの初期化
  vector<string> names = {"yamamoto", "watanabe", "ito", "takahashi", "suzuki", "sato"};

  for (const string &name : names) {
    list.insert(new Node(name));
  }

  cout << "before: ";
  list.display();

  Node *watanabe = list.find("watanabe");
  if (watanabe) list.delete(watanabe);

  cout << "after: ";
  list.printList();

  return 0;
}

出力

before: sato -> suzuki -> takahashi -> ito -> watanabe -> yamamoto ->
after: sato -> suzuki -> takahashi -> ito -> yamamoto ->

操作と計算量

要素の操作	平均時間計算量
インデックスでのアクセス	O(n)
要素の検索	O(n)
要素の挿入	O(1)
要素の末尾への挿入	O(1)
要素の削除	O(1)

3. [アルゴリズム] 線形探索法 / 二分探索法（Linear Search / Binary Search）

探索とは、データの集合の中から与えられたキーの位置や存在の有無を調べる問題。
線形探索法（Linear Search）
- 配列の先頭から各要素を順番に調べる方法。
- 最大探索回数（最大比較回数 / Max Number Of Comparisons） O(n)
- 平均探索回数(平均比較回数 / Average Number Of Comparisons) (n + 1) / 2
- 計算量 O(n)
二分探索法（Binary Search）
- 以下の手順で行われる探索アルゴリズム
  1. 配列全体を探索の範囲とする。
  2. 探索の範囲内の中央の要素を調べる。
  3. 目的のキーと中央の要素のキーが一致すれば探索を終了する。
  4. 目的のキーが中央の要素のキーよりも小さければ前半部分を、大きければ後半部分を探索の範囲として2. へ戻る。
- 計算量 O(log(n))

4. [データ構造] ハッシュテーブル（Hash Table）

各言語のライブラリ

ハッシュセット
- C++ ... std::unordered_set
- Java ... HashSet
- Go ... map[T]bool
- Python ... set
- Ruby ... Set
ハッシュマップ
- C++ ... std::unordered_map
- Java ... HashMap
- Go ... map[T]V
- Python ... dict
- Ruby ... Hash

データ構造の説明

ハッシュテーブルは、キーと値のペアを格納するデータ構造。
- キーをハッシュ関数 h で変換し、その結果のハッシュ値 h(x) をインデックスとして使用する。 T[h(x)]
ハッシュセット（Hash Set）
- ユニークな要素の集合を管理する（キーの概念はない）。
ハッシュマップ（Hash Map）
- キーと値のペアを格納する。
計算量
- 完全ハッシュ関数（どのキーに対してもハッシュ値が異なるような、理想的なハッシュ関数）であれば、データの「挿入」、「削除」、「検索」の各操作は常に O(1)
- 現実的にはすべてのキーに対してユニークなハッシュ値を保証することは難しい。
ハッシュ衝突
- 異なるキー x , y が、同じハッシュ値を持つこと。
- h(x) = h(y)
ハッシュ衝突の対策
- チェイン法（連鎖法 / Separate Chaining）
  - 各ハッシュ値ごとに連結リストを構築しておき、衝突が発生した場合は、同じハッシュ値のリストの末尾に挿入する。 O(1)
    - 要素を検索するときには、連結リストの各ノードの中身を照合する。
  - 各データに対するハッシュ値は独立かつ一様であるとする（単純一様ハッシュ仮定）と、各操作の平均計算量は O(1 + a) である。
    - ただし、 α = n/m であり、 α を 負荷率(load factor) と呼ぶ。
- オープンアドレス法（開番地法 / Open Addressing）
  - ハッシュ衝突が発生した場合は、線形探索（Linear Probing） or 二次探索（Quadratic Probing） or 二重ハッシュ（Double Hashing） などによって別の空きバケットを探す。

2023年度後期アルゴリズムB 第5回データの探索 - 東京都立大学

ハッシュテーブルのイメージ:

Hash Tables, Hashing and Collision Handling

操作と計算量

要素の操作	平均時間計算量
要素の検索	O(1)
要素の挿入	O(1)
要素の削除	O(1)

最悪のケースは、データの各要素が全て同じ値である場合。
このとき、要素の検索の計算量は O(n) になってしまう。

5. [データ構造] スタック / キュー（Stack / Queue）

データ構造の説明

スタック（Stack）
- データの中で「最後」に入ったものが最初に取り出される、後入れ先出し（LIFO: Last In First Out）のデータ構造
- 一時的にデータを退避したいときに有効なデータ構造。
- C++ の std::stack で使用される。
- 次の操作を行う。
  - push(x) : スタックの一番上にデータを追加する
  - pop() : スタックの一番上からデータを削除する
  - peek() : スタックの一番上のデータを返す
  - isEmpty() : スタックが空かどうかを調べる
  - isFull() : スタックが満杯かどうかを調べる
キュー（待ち行列 / Queue）
- データの中で「最初」に入ったものが最初に取り出される、先入れ先出し（FIFO: First In First Out）のデータ構造
- データを到着順に処理したい時に使用するデータ構造。
- C++ の std::queue で使用される。
- 次の操作を行う。
  - enqueue(x) : キューの末尾にデータを追加する
  - dequeue() : キューの先頭からデータを削除する
  - peek() : キューの先頭のデータを返す
  - isEmpty() : キューが空かどうかを調べる
  - isFull() : キューが満杯かどうかを調べる

6. [アルゴリズム] 再帰 / 分割統治法 / バックトラック法（Recursion / Divide And Conquer / Backtracking）

再帰関数
- 関数の中で自分自身を呼び出す関数のこと。
- 再帰呼び出しを行わずに終了する、 ベースケース となる処理が必要。
- 再帰関数は、呼び出されるたびに引数の値がベースケースに近づいていくように実装する必要がある。

Pythonでの実装

# 整数の n の階乗を計算する関数
def factorial(n):
  if n == 1: # ベースケース
    return 1
  return n * factor(n - 1)

print(factorial(4))
# => 24  # 4 * (3 * (2 * 1))

C++での実装

#include <iostream>
using namespace std;

// 整数の n の階乗を計算する関数
int factorial(int n) {
    if (n == 1) { // ベースケース
        return 1;
    }
    return n * factorial(n - 1);
}

int main() {
    cout << factorial(4) << endl; // => 24  // 4 * (3 * (2 * 1))
    return 0;
}

分割統治法
- 問題を部分問題に 分割（Divide） し、部分問題を再帰的に解き（Solve）、それらを 統合（Conquer） して、元の問題を解く手法。
- 分割統治法を利用したアルゴリズム
  - マージソート
  - クイックソート

Pythonでの実装

def partMax(T, left, right):
  middle = (left + right) / 2 # Dvide
  if left == right - 1:
    return T[left]

  leftPartMax = partMax(T, left, middle) # Solve（前半の部分問題）
  rightPartMax = partMax(T, middle, right) # Solve（後半の部分問題）

  return max(leftPartMax, rightPartMax) # Conquer

C++での実装

#include <iostream>
#include <vector>
using namespace std;

int partMax(vector<int>& T, int left, int right) {
    if (left == right - 1) {
        return T[left];
    }

    int middle = (left + right) / 2; // Divide
    int leftPartMax = partMax(T, left, middle); // Solve（前半の部分問題）
    int rightPartMax = partMax(T, middle, right); // Solve（後半の部分問題）

    return max(leftPartMax, rightPartMax); // Conquer
}

int main() {
    vector<int> T = {1, 3, 5, 2, 8, 6};
    cout << partMax(T, 0, T.size()) << endl;
    // => 8
    return 0;
}

バックトラッキング（Backtracking）
- 解の候補を構築する際に、部分的に有効でないと判断された候補を捨てて、元の状態に戻り、別の候補を試す探索手法。
- 再帰的な探索を行い、可能性のある解を全て試行することで解を見つける。
- 主に組み合わせ問題やパズル、最適化問題の解決に用いられる。
- バックトラッキングの使用例
  - 数独（Sudoku）
    - 9×9のグリッドを使い、各行、各列、3×3のブロックに1から9までの数字を一度ずつ配置する問題
  - 8クイーン問題（Eight Queens Problem）
    - 8×8のチェスボード上に8つのクイーンを互いに攻撃し合わないように配置する問題

8クイーン問題のPythonでの実装

def is_safe(board, row, col):
    # 同じ列にクイーンがあるか確認
    for i in range(col):
        if board[row][i] == 1:
            return False
    # 左上の対角線にクイーンがあるか確認
    for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False
    # 左下の対角線にクイーンがあるか確認
    for i, j in zip(range(row, len(board), 1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False
    return True

def solve_n_queens(board, col):
    if col >= len(board):
        return True
    for i in range(len(board)):
        if is_safe(board, i, col):
            board[i][col] = 1
            if solve_n_queens(board, col + 1):
                return True
            board[i][col] = 0
    return False

def print_board(board):
    for row in board:
        print(" ".join("Q" if x == 1 else "." for x in row))

n = 8
board = [[0] * n for _ in range(n)]
if solve_n_queens(board, 0):
    print_board(board)
else:
    print("Solution does not exist")

8クイーン問題のC++での実装

#include <iostream>
#include <vector>
using namespace std;

bool is_safe(vector<vector<int>>& board, int row, int col) {
    // 同じ列にクイーンがあるか確認
    for (int i = 0; i < col; i++) {
        if (board[row][i] == 1) {
            return false;
        }
    }
    // 左上の対角線にクイーンがあるか確認
    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 1) {
            return false;
        }
    }
    // 左下の対角線にクイーンがあるか確認
    for (int i = row, j = col; i < board.size() && j >= 0; i++, j--) {
        if (board[i][j] == 1) {
            return false;
        }
    }
    return true;
}

bool solve_n_queens(vector<vector<int>>& board, int col) {
    if (col >= board.size()) {
        return true;
    }
    for (int i = 0; i < board.size(); i++) {
        if (is_safe(board, i, col)) {
            board[i][col] = 1;
            if (solve_n_queens(board, col + 1)) {
                return true;
            }
            board[i][col] = 0;
        }
    }
    return false;
}

void print_board(vector<vector<int>>& board) {
    for (auto& row : board) {
        for (auto& cell : row) {
            cout << (cell == 1 ? "Q" : ".") << " ";
        }
        cout << endl;
    }
}

int main() {
    int n = 8;
    vector<vector<int>> board(n, vector<int>(n, 0));
    if (solve_n_queens(board, 0)) {
        print_board(board);
    } else {
        cout << "Solution does not exist" << endl;
    }
    return 0;
}

出力

Q . . . . . . .
. . . . Q . . .
. . . . . . . Q
. . . . . Q . .
. . Q . . . . .
. . . . . . Q .
. Q . . . . . .
. . . Q . . . .

7. [データ構造] 二分木（Binary Tree）

データ構造の説明

木（Tree）
- 節点(節 / 頂点 / ノード / node / vertex) と、それらを結ぶ 辺（枝 / edge） で表される階層構造。
  - 節点は円、辺は線で表される。
根付き木（rooted tree）
- 根を持つ木。
根（root）
- 親（parent）を持たない唯一の節点。
葉（外部節点 / leaf / external node）
- 子（child）を持たない節点。
深さ（depth）
- 根から節点までの経路の長さ。
節点の高さ（height of node）
- 節点から葉までの経路の長さの最大値。
木の高さ（height of tree）
- 根から葉までの経路の長さの最大値。
レベル（level）
- 根をレベル0として、辺を下に進むにつれて1ずつ増える各段階。
兄弟（sibling）
- 同一の親を持つ節点。
二分木（Binary Tree）
- 各節点が2つ以下の子を持つ木。
- 二分木は順序木。
順序木（Ordered Tree）
- 子（兄弟間）に順序性がある木。
  - e.g. 二分木の、ある節点の子が1つの場合、それが左の子なのか右の子なのかを厳密に区別する。

二分木のイメージ:

Pythonで木構造を実装してみた　~二分木と根付き木~ - スズメの本棚

8. [データ構造] 二分ヒープ（Binary Heap）

データ構造の説明

ヒープ（二分ヒープ）は、特定の順序付けに従った完全二分木の一種。
完全二分木（Complete Binary Tree）
- 最下位以外のレベルの節点が完全に埋まっている二分木。
- 節点の数を n としたとき、ヒープの挿入、検索、削除によって、木の高さが常に log2(n) となる。 O(log(n))
最小ヒープ（Min Heap）
- 各節点の値が、その子の値以下である完全二分木。
- 根の値が最小の値になる。
最大ヒープ（Max Heap）
- 各節点の値が、その子の値以上である完全二分木。
- 根の値が最大の値になる。
[アルゴリズム] 優先度付きキュー（Priority Queue）
- 優先度付きキューは、優先度を割り当て、優先度が高い要素からアクセスする抽象データ型。
  - キューはFIFOのデータ構造であったが、それとは異なる。
- 二分ヒープを使用することで、挿入、検索、削除を効率的に行うことができる。 O(log(n))

最大ヒープの例:

二分ヒープ - Wikipedia

優先度付きキューの例:

優先度付きキューとヒープソート：解説と実装(C++) - Nov's Research Note

9. [データ構造] 二分探索木（Binary Search Tree）

データ構造の説明

左の子孫の値 ≦ 節点の値 ≦ 右の子孫の値 という制約を持つ二分木。
- 子孫すべてについて成り立っていなければならないことに注意。
- 各節点は、値に加え、親、左の子、右の子へのポインタを持つ。
平衡（左右の部分木の高さが小さい）状態 では木の高さは log2(n) となる。
- ただし、 偏った二分探索木は、事実上の線形リスト になり、木の高さは n となる。
平衡二分探索木（平衡木 / Balanced Binary Search Tree / Balanced Tree）
- 左右の部分木の高さがほぼ等しい二分探索木。
赤黒木（Red-Black Tree）
- 特定の平衡性を持つ 自己平衡二分探索木（Self-Balanced Binary Search Tree）。
- C++ の std::set や std::map で使用される。
AVL木（AVL Tree / Adelson-Velskii and Landis' Tree）
- 各節点の左右部分木の高さの差が1以下である平衡二分探索木。
B-木（B-Tree）
- 節点が、3つ以上の多くの子を持つことができる平衡木。
- 大量のデータを効率的に管理できるため、データベースやファイルシステムで広く使用されている。
スプレー木（Splay Tree）
- 操作のたびに特定の節点を根まで移動し再アクセスが速くなる平衡二分探索木。
ツリープ（Treap）
- 木（Tree）とヒープ（Heap）の特性を合わせた平衡二分探索木。
- 乱択アルゴリズムを使用する。

二分探索木:

二分探索木 - Rustではじめるデータ構造とアルゴリズム（第2回）

平衡木と非平衡木:

バランスドツリー(平衡木) - ソースコード探検隊

操作と計算量

要素の操作	平均時間計算量	最悪時間計算量
要素の検索	O(n log(n))	O(n)
要素の挿入	O(n log(n))	O(n)
要素の削除	O(n log(n))	O(n)

参考