基本情報技術者試験対策（35）「なぜアルゴリズムとデータ構造を学ぶのか?」

アルゴリズムとデータ構造の基本を知って応用する

アルゴリズム(algorithm) とは、与えられた問題を解くための明確な手順である。データ構造とは、データを効率よく処理するための配置方法のことである。プログラムを作るときには、その設計段階として、アルゴリズムとデータ構造を明確にしなければならない。

アルゴリズムとデータ構造は、 自分で考えるものである。 ただし、 そのためには、すでに知られている基本的なアルゴリズムとデータ構造を、十分に理解しておく必要がある。 基本がわかっていれば、 そのアイデアを様々な場面で応用できるからである。

基本的なアルゴリズムとデータ構造には、「バブルソート」や「二分探索木」のような名前が付けられている。 基本情報技術者試験の科目Aには、 基本的なアルゴリズムとデータ構造の名前と内容を知っているかどうかを問う問題が出題される。

試験のシラバスに示されている主なアルゴリズムとデータ構造

さらに、科目Bには、擬似言語で表記されたプログラムが出題される。
このプログラムを読み取るには、 科目Aのテーマになっている基本的なアルゴリズムとデータ構造で得た知識を、問題の内容に当てはめて応用する能力が要求される。

アルゴリズムを考えるコツ

基本的なアルゴリズムとデータ構造を説明する前に、 アルゴリズムを考えるコツを紹介しておこう。 例えば、コンピュータとは直接関係ないが、「3リットルのバケツを1つと、5リットルのバケツを1つ使って、 ぴったり4リットルの水を用意しなさい」 という問題を解くアルゴリズムを考えてみよう。 水道の蛇口から、 好きなだけ水を汲めるとする。 汲んだ水を捨てることもできる。

この問題を解くには、水を汲んだり、移したり、捨てたりといった、いくつかの処理をコツコツと進めていかなければならない。
そのためには、処理の区切りを見出せなければならない。 ここでは、 「汲む」 「移す」 「捨てる」が、処理の区切りになる。
処理を進めることで、 データの値（ここでは、バケツに入っている水の量）が変化していく。 問題を解くには、それぞれの処理におけるデータの値の変化を追いかけることも必要になる。 データの値の変化を追いかけることをトレース (trace = 追跡) と呼ぶ。

「処理の区切りを見出す」、「処理をコツコツと進める」、「データの値の変化をトレースする」。 これらが、 アルゴリズムを考えるコツである。この問題を解くアルゴリズムの例と、バケツに入っている水の量をトレースした結果を下図に示す。 アルゴリズムが苦手な人は、このトレースを、 何度も紙の上に書いて練習しよう。 そうすれば、アルゴリズムを考えるコツがつかめる。

ぴったり4リットルの水を用意するアルゴリズムの例

変数と代入

バケツで水を汲むアルゴリズムでは、水がデータに相当し、バケツがデータの入れ物に相当すると考えよう。 コンピュータのアルゴリズムでは、数値がデータであり、 データの入れ物を変数で表す。 数学の変数は、何らかの数値という意味だが、 アルゴリズムの変数は、データの入れ物に名前を付けたものである。 これを変数名と呼ぶ。

変数名は1文字でも、Sum や Aveのような複数文字でも構わない。 複数文字の変数名にする場合は、 変数の役割を表す英語にするのが一般的である。例えば、合計値(sum) を格納する変数ならSumという名前にして、平均値(average)を格納する変数ならAveという名前にする。

変数を図に示すときには、 四角い箱で表すのが一般的である。 変数に値を入れることを代入と呼び、 矢印で示すのが一般的である。 上図は、 変数 Sumへの456というデータの代入と、 変数 Sum に456というデータが格納されている様子を表したものである。 格納されたデータは、その値を箱の中に書く。

データ構造の基本となる配列

例えば、100個のデータを処理するには、 その入れ物として100個の変数が必要である。
この場合には、100個の変数それぞれに異なる名前を付けるのは面倒なので、全体に1つの名前を付け、個々の変数を番号で区別する。 この表現を配列 (array) と呼び、 個々の変数を要素と呼び、 要素の番号を要素番号や添字 ( index )と呼ぶ。

下図は、要素数5個の配列を表したものである。 配列は、すき間なく箱を並べた絵で表す。 この配列全体の名前は、Aであり、 個々の要素は、 A[0]～A[4]という名前である。 配列名 [要素番号]という名前にするのである。配列の左端が先頭で、 右端が末尾である。 ここでは、先頭を0番にしているので、末尾が4番になる。

アルゴリズムの問題では、配列の先頭を0番にする場合と、1番にする場合があるので注意しよう。 要素数が5個の場合、 先頭が0番ならA[0] ～ A[4] になり、 先頭が1番ならA[1] ～ A[5] になる。 どちらであるかは、問題文に示されているので、必ず確認しよう。

配列は、様々なデータ構造の基本になる。 なぜなら、コンピュータのメモリ内で物理的にデータを格納する形式は、配列と同じになっている(連続した記憶領域に並べて格納する) からである。 配列の使い方を工夫することで、リストや二分探索木などのデータ構造が実現される。

配列を使ったアルゴリズムでは、 配列の要素を先頭から末尾まで1つずつ順番に取り出して、処理をコツコツ進める。 配列の処理は、繰り返しの表現を使うことで、 効率的に記述できる。 下図は、A[0]～A[4]の値を順番に表示するフローチャートである。 変数 iを要素番号として 「A[i]の値を表示する」という処理を繰り返していることに注目しよう。 変数iの値を0から4まで1ずつ増やしながら繰り返しを行うことで、 A [0] ~A[4] の値を順番に表示することができる。

ソートとサーチ

科目Aによく出題される基本的なアルゴリズムは、ソート (sort=整列) とサーチ (search=探索) である。 ソートとサーチは、 どちらも配列を対象としたアルゴリズムである。

ソートとは、配列の要素の順序を揃えることである。 小さい順に揃えることを昇順と呼ぶ。 配列の先頭から末尾に向かって、 データの値が昇っていく（だんだん大きくなる)からである。逆に、大きい順に揃えることを降順と呼ぶ。配列の先頭から末尾に向かって、データの値が降りていく(だんだん小さくなる)からである（下図）。

サーチとは、配列の中から、 目的のデータを見つけることである。一般的にデータが見つかった場合は、見つかった位置 (配列の要素番号) をサーチの結果とする。 見つからない場合は、配列の要素としてあり得ない番号をサーチの結果とする。例えば、 配列の先頭の要素を0番としている場合は、ー1番を見つからない結果とする(下図)。

（参考）情報処理教科書 出るとこだけ！基本情報技術者［科目A］［科目B］2025年