Hello Algo「アルゴリズム入門」章まとめ——身近な具体例から理解するデータ構造とアルゴリズムの基本

本章は『Hello Algo』の最初の章であり、アルゴリズムを「手の届かない難しい知識」ではなく、日常の行動の中にすでに存在する思考パターンとして捉え直すための導入です。辞書引き・トランプ整理・お釣り計算という3つの生活事例から二分探索・挿入ソート・貪欲法の本質を掴み、さらに「アルゴリズムとデータ構造の定義」「両者の関係」「エンジニアが基礎を学ぶ意義」を順に整理します。本記事を読み終えると、序章の要点が知識として定着し、後続の各章（探索・ソート・貪欲法など）を学ぶための地図が手に入ります。

この章で押さえるべき3つの「生活の中のアルゴリズム」

本節は、アルゴリズムは至るところにあるで詳述されている内容の要点です。アルゴリズムの多くは複雑な数学を必要とせず、基本的な論理に支えられており、その論理は日常生活のいたるところに現れます。

辞書を引く＝二分探索（二分查找）アルゴリズム

日本語の辞書はピンインのアルファベット順に並んでいます。先頭文字が r の字を探すとき、私たちは次のように辞書を引きます。

1. 辞書をおよそ半分の位置で開き、そのページの先頭文字を確認する（仮に m だったとする）。
2. ピンイン表で r は m より後ろにあるため、辞書の前半を除外し、探索範囲を後半へ絞り込む。
3. 先頭文字が r のページに到達するまで手順 1・2 を繰り返す。

この「半分に割って対象範囲を絞る」操作の繰り返しは、まさに二分探索アルゴリズムそのものです。データ構造の観点では辞書を整列済みの「配列」とみなせ、アルゴリズムの観点ではこの一連の操作を「二分探索」とみなせます。また、二分探索は範囲を半分ずつ捨てる「分割統治（分而治之）」という重要なアルゴリズム思想を体現している点も押さえておきましょう。

二分探索は実装も簡潔です。次のコードは、この章の要点をそのままコード化したもので、二分探索の実装例では両端を含む閉区間 [0, n-1] を使って探索します。

def binary_search(nums: list[int], target: int) -> int:
    """二分查找（双闭区间）"""
    # 初始化双闭区间 [0, n-1] ，即 i, j 分别指向数组首元素、尾元素
    i, j = 0, len(nums) - 1
    # 循环，当搜索区间为空时跳出（当 i > j 时为空）
    while i <= j:
        m = (i + j) // 2  # 计算中点索引 m
        if nums[m] < target:
            i = m + 1  # 此情况说明 target 在区间 [m+1, j] 中
        elif nums[m] > target:
            j = m - 1  # 此情况说明 target 在区间 [i, m-1] 中
        else:
            return m  # 找到目标元素，返回其索引
    return -1  # 未找到目标元素，返回 -1

二分探索は時間計算量が $O(\log n)$ であり、配列がソート済みであることが前提です。なお、同じファイルには探索範囲を「左閉右開」の [0, n) で持つ別実装もあり、区間の持ち方がループ条件（i <= j か i < j）にどう影響するかを比較できます。

トランプを整理する＝挿入ソート（插入排序）アルゴリズム

トランプを手札の小さい順に並べるとき、私たちは無意識のうちに次の手順を踏みます。

1. 手札を「整列済み」と「未整列」の2つの部分に分け、初期状態では左端の1枚を整列済みとみなす。
2. 未整列部分から1枚を取り出し、整列済み部分の中の正しい位置に挿入する。完了すると左端の2枚が整列済みになる。
3. 手順 2 を繰り返し、すべてのカードが整列済みになるまで続ける。

これは本質的に挿入ソートアルゴリズムです。挿入ソートは小規模なデータ集合のソートに適しており、多くのプログラミング言語のソートライブラリ関数の中でも利用されています。実装は挿入ソートのコード例にあり、外側ループで「整列済み区間 [0, i-1]」を育て、内側ループで要素 base を右へずらしながら正しい挿入位置を確定させます。

def insertion_sort(nums: list[int]):
    """插入排序"""
    # 外循环：已排序区间为 [0, i-1]
    for i in range(1, len(nums)):
        base = nums[i]
        j = i - 1
        # 内循环：将 base 插入到已排序区间 [0, i-1] 中的正确位置
        while j >= 0 and nums[j] > base:
            nums[j + 1] = nums[j]  # 将 nums[j] 向右移动一位
            j -= 1
        nums[j + 1] = base  # 将 base 赋值到正确位置

お釣りを計算する＝貪欲法（贪心算法）

スーパーで $69$ 元の商品を買い、$100$ 元を渡した場合、店員は $31$ 元のお釣りを返します。このとき店員は、以下のように「できるだけ額面の大きい貨幣から順に使う」という自然な思考をします。

1. $31$ 元以下で使える貨幣の候補は $1$ 元・$5$ 元・$10$ 元・$20$ 元。
2. 候補の中で最大の $20$ 元を使い、残りは $31 - 20 = 11$ 元。
3. 残りの候補から最大の $10$ 元を使い、残りは $11 - 10 = 1$ 元。
4. 残りから $1$ 元を使い、残りは $1 - 1 = 0$ 元。
5. 結果は $20 + 10 + 1 = 31$ 元でお釣り完了。

各ステップで「その時点で最善と思われる選択＝できるだけ大きい額面の貨幣」を取り続け、最終的に実行可能なお釣りの案を得るこの方法は、データ構造とアルゴリズムの観点では貪欲法と呼ばれます。

貪欲法の実装は零錢兌換（贪心）のコード例にあり、「残額以下で最も大きい硬貨」を繰り返し選ぶ単純なループで表現されています。

def coin_change_greedy(coins: list[int], amt: int) -> int:
    """零钱兑换：贪心"""
    # 假设 coins 列表有序
    i = len(coins) - 1
    count = 0
    # 循环进行贪心选择，直到无剩余金额
    while amt > 0:
        # 找到小于且最接近剩余金额的硬币
        while i > 0 and coins[i] > amt:
            i -= 1
        # 选择 coins[i]
        amt -= coins[i]
        count += 1
    # 若未找到可行方案，则返回 -1
    return count if amt == 0 else -1

注意したいのは、貪欲法は常に大域最適解を保証するわけではないという点です。同ファイルのテストコードでは coins = [1, 20, 50], amt = 60 という反例が示されており、貪欲な選択だと $50 + 1 \times 10$ の 11 枚になる一方、本当の最適解は $20 + 20 + 20$ の 3 枚です。この「常に正しいとは限らない」という性質が、貪欲法の章で詳しく扱うテーマにつながります。

アルゴリズムとデータ構造の定義を正確に押さえる

日常会話で「アルゴリズム」という言葉は数学のイメージを連想させがちですが、本質はもっと平易です。アルゴリズムとは（ja/docs/chapter_introduction/what_is_dsa.md）では、次のように両者を定義しています。

• アルゴリズム（algorithm）：限られた時間内に特定の問題を解決するための一連の命令または操作手順。次の特徴を持ちます。
  • 問題が明確で、入力と出力の定義がはっきりしている。
  • 実行可能であり、有限の手順・時間・メモリ空間で完了できる。
  • 各手順の意味が確定しており、同じ入力と実行条件では常に同じ出力になる（決定的）。
• データ構造（data structure）：データを整理して保存する方式であり、データの内容・データ間の関係・データの操作方法を含む。次の設計目標があります。
  • 使用する空間をできるだけ少なくし、メモリを節約する。
  • データ操作（アクセス・追加・削除・更新など）をできるだけ高速にする。
  • 簡潔なデータ表現と論理情報を提供し、アルゴリズムが効率よく動作できるようにする。

また、データ構造の設計はトレードオフに満ちた過程です。一面を改善しようとすると別の面で妥協が必要になります。たとえば「連結リストは配列に比べてデータの追加・削除が容易だが、データアクセス速度を犠牲にする」「グラフは連結リストより豊富な論理情報を提供するが、より多くのメモリ空間を必要とする」といった関係が典型例です。

データ構造とアルゴリズムの関係——「積み木」の比喩

要点の振り返りでは、両者の関係が次のようにまとめられています。

• データ構造はアルゴリズムの土台であり、アルゴリズムに対して構造化して格納されたデータと、そのデータを操作する方法を提供する。
• アルゴリズムはデータ構造に生命を吹き込む。データ構造はそれ自体ではデータ情報を保存するだけであり、アルゴリズムと組み合わせて初めて特定の問題を解決できる。
• アルゴリズムは通常、異なるデータ構造の上でも実装できるが、実行効率が大きく異なる場合があり、適切なデータ構造の選択が重要になる。

両者の関係は積み木の組み立てにたとえられます。1セットの積み木には多くの部品が含まれるだけでなく、詳細な組み立て説明書も付属しており、その説明書どおりに手順を踏めば精巧な模型を組み立てられます。対応関係を整理すると下表のようになります。

データ構造とアルゴリズム	積み木の対応物
入力データ	まだ組み立てていないブロック
データ構造	ブロックの構成形式（形状・大きさ・接続方法など）
アルゴリズム	ブロックを目標の形に組み上げる一連の操作手順
出力データ	完成したブロック模型

特筆すべき点として、データ構造とアルゴリズムはプログラミング言語から独立しています。だからこそ本書では、Python・Java・C++・C・C#・JavaScript・Go・Swift・Rust・Ruby・Kotlin・TypeScript・Dart など複数言語の実装を提供できています（各言語のコードは codes 配下に章ごとに整理されています）。なお実際の議論では「データ構造とアルゴリズム」を略して単に「アルゴリズム」と呼ぶ慣習があります。たとえば LeetCode のアルゴリズム問題は、実際にはデータ構造とアルゴリズムの両方の知識を同時に問うています。

Q&A：業務で「アルゴリズムを使ったことがない」という疑問に答える

本章のまとめに収録されている Q&A は、実務エンジニアにとって最も身近な疑問です。

Q：プログラマーとして日常業務でアルゴリズムを使って問題を解決したことがありません。よく使うアルゴリズムはプログラミング言語にすべてカプセル化されており、そのまま使えばよいのです。これは、仕事上の問題がまだアルゴリズムを必要とする段階に達していないことを意味するのでしょうか？

この問いに対し、本書は「具体的な仕事のスキル＝武術の『型（招式）』、基礎科目＝『内功』」という比喩で答えます。アルゴリズム（およびその他の基礎科目）を学ぶ意義は、仕事でそれをゼロから実装することではなく、学んだ知識に基づいて問題解決の際に専門的な反応や判断ができるようになり、仕事全体の品質を高めることにあります。

具体例として、どのプログラミング言語にも組み込みのソート関数があります。

• データ構造とアルゴリズムを学んでいなければ、与えられたデータをすべて組み込みソート関数に任せてしまうかもしれません。実行は問題なく、性能も悪くなく、一見すると特に問題はありません。
• しかしアルゴリズムを学んでいれば、組み込みソート関数の時間計算量が $O(n \log n)$ であることを知っています。さらに、与えられたデータが固定桁数の整数（例えば学籍番号）であれば、より効率の高い**基数ソート（基数排序）**を使い、時間計算量を $O(nk)$（$k$ は桁数）へ下げられます。データ量が非常に大きい場合、節約できた実行時間は大きな価値（コスト削減・体験向上など）を生みます。

基数ソートは「桁ごとに下位から順に安定ソートを繰り返す」アルゴリズムで、基数ソートのコード例では、最大値 m から桁数を判定し、exp = 1, 10, 100, … と変化させながら各桁に対して一度ずつ計数ソート（counting sort）を適用しています。

def radix_sort(nums: list[int]):
    """基数排序"""
    # 获取数组的最大元素，用于判断最大位数
    m = max(nums)
    # 按照从低位到高位的顺序遍历
    exp = 1
    while exp <= m:
        # 对数组元素的第 k 位执行计数排序
        # k = 1 -> exp = 1
        # k = 2 -> exp = 10
        # 即 exp = 10^(k-1)
        counting_sort_digit(nums, exp)
        exp *= 10

ここで digit() 関数は (num // exp) % 10 で対象桁の数字を取り出し、桁数の $k$ 回のパスそれぞれが $O(n)$ で済むため、全体で $O(nk)$ になります。組み込みソートの $O(n \log n)$ と比べると、桁数 $k$ が小さい整数データでは基数ソートが有利になるケースがある、というのが要点です。

まとめの最後は、工学分野の現実を鋭く指摘しています。

工学分野では、大量の問題で最適解に到達することは難しく、少なくない問題は「だいたい」解決されているにすぎません。問題の難しさは、一方では問題そのものの性質に依存し、他方ではそれを観測する人の知識の蓄積にも依存します。知識が充実し、経験が豊富であるほど問題分析はより深くなり、問題はより洗練された形で解決できるようになります。

先ほどの貪欲法の反例（最適解を得られない硬貨の組み合わせ）も、この「問題はそもそも難しい」「知識と経験が解の質を左右する」という視点と響き合います。基礎を学ぶことは、単発の知識を暗記することではなく、問題を観測する「解像度」を上げることなのです。

要点の振り返りと、次の学び方

本章の要点は、次の一文に凝縮されます。

アルゴリズムは日常生活の至る所にあり、決して手の届かない難解な知識ではありません。実際、私たちは気づかないうちに多くのアルゴリズムを身につけ、生活のさまざまな問題を解決しています。

• 辞書引きは二分探索、トランプ整理は挿入ソート、お釣り計算は貪欲法——それぞれの生活スキルが、探索・ソート・貪欲法というアルゴリズムの具体例である。
• アルゴリズムは「限られた時間内に特定の問題を解決する一連の命令または操作手順」、データ構造は「コンピュータ内でデータを組織し保存する方法」である。
• データ構造はアルゴリズムの土台であり、アルゴリズムはデータ構造に生命を吹き込む。両者は積み木（データ）・構成形式（データ構造）・組み立て手順（アルゴリズム）という比喩で対応づけられる。
• 実務で基礎を学ぶ意義は「ゼロからの実装」ではなく、「知識に基づく専門的な判断」にある。

本文で紹介したコードはすべて、リポジトリの codes/python 以下に章別・テーマ別のファイルとして保存されており、冒頭の Driver Code 付きでそのまま実行して動作を確認できます。たとえば日本語版のコード一式は ja/codes に、本文書の元になった導入章は アルゴリズム入門（ja/docs/chapter_introduction/index.md） を起点に読むことができます。次のステップとしては、計算の複雑さの章へ進み、本書の各アルゴリズムを評価する共通の物差し（時間・空間計算量）を身につけることをおすすめします。