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

ここから基本情報！配列の形と大きさ

食パンだけでなく、バゲットやクロワッサンの売れた数も曜日ごとに並べたいときは、「何番目の商品の、何曜日か」の2つの番号で箱を決めます。このように、2つ以上の添字で要素を指定する配列を多次元配列といいます。行が商品、列が曜日の表を思い浮かべると、添字が2つの2次元配列になります。

配列の箱の数をいつ決めるかでも、2種類に分かれます。プログラムを動かす前に要素の数を決めておき、実行中には変えられないものが静的配列です。曜日は7つと決まっているので、曜日ごとの売上には静的配列で足ります。一方、通販の注文のように、その日になってみないと数が分からないデータもあります。実行中に要素の数に応じて大きさを広げたり縮めたりできる配列を動的配列といいます。

大きさを実行中に変えるには、そのつどメモリの空いた場所を借りてくる必要があります。プログラムの実行中に、必要な大きさのメモリ領域を確保する関数を領域割付け関数（メモリ割付け関数）と呼ぶことがあります。C言語の malloc がその例で、確保した領域は使い終わったら free で返します。基本情報のシラバスにはこの語は載っておらず、動的配列を支える仕組みとして覚えておけば足ります。

基本情報の範囲ここまで

ここから基本情報！ポインタのつなぎ方

線形リストは、ポインタの持ち方で呼び分けます。各要素が次の要素へのポインタだけを持ち、先頭から後ろへ一方向にしかたどれないものが単方向リストです。10時半の付箋から、1つ前の10時の付箋には戻れません。各要素が次と前の両方へのポインタを持つものが双方向リストで、前後どちらにもたどれます。そのぶん、要素を足すときに書き換えるポインタは増えます。

最後の要素のポインタが先頭の要素を指し、たどっていくと一周して戻ってくるものを環状リストといいます。月曜から日曜まで、日曜の次がまた月曜になるシフト表のような、終わりのない順番を表すのに向いています。

予約を一覧の最後に足すことが多いなら、毎回先頭から最後尾までたどるのは手間です。そこで、先頭を指すポインタとは別に、最後尾の要素を指すポインタを持っておきます。これを末尾ポインタと呼びます。末尾ポインタをたどれば、要素がいくつあっても1回で最後尾に着きます。

基本情報の範囲ここまで

ここから基本情報！略語とスタックの計算

後入れ先出しは、英語の Last In First Out の頭文字をとってLIFOと書きます。先入れ先出しは First In First Out でFIFOです。LIFO がスタック、FIFO がキューと対応させて覚えます。

スタックは、式の計算にも使われます。食パン300円とバゲット200円を2組買ったときの代金は (300 + 200) × 2 です。この式を、演算子を2つの数の後ろに書く形に直すと「300 200 + 2 ×」になります。この書き方を後置記法（逆ポーランド記法）といいます。括弧がなくても、どの順に計算するかが一通りに決まります。

後置記法の式は、左から読みながら、数ならプッシュ、演算子なら2つポップして計算し、結果をプッシュする、という決まりだけで計算できます。

式を読み終えたとき、スタックに残った1000が答えです。

基本情報の範囲ここまで

ここから基本情報！木の各部の呼び名

木構造の1つ1つのデータを節（ノード）と呼びます。いちばん上にあって親を持たない節が根（ルート）で、こむぎ堂のメニューでは「全商品」にあたります。節と節を結ぶ線が枝、子を持たない末端の節が葉です。「食パン」「バゲット」のように、それ以上分けない商品が葉になります。

子どうしの並び順に意味があるかどうかでも区別します。子の並び順が決められている木を順序木といいます。メニューの並びを「よく売れる順」と決めておけば、順序木です。また、1つの節が3つ以上の子を持てる木を多分木と呼びます。「食事パン」「菓子パン」「焼き菓子」の3つを子に持つ「全商品」の節は、多分木の節です。

基本情報の範囲ここまで

ここから基本情報！2分木の形と巡回のしかた

2分木のうち、いちばん下の段を除くすべての段が子で埋まっていて、いちばん下の段も左から順に詰まっているものを完全2分木といいます。隙間がないので、上の段から、同じ段では左から順に1から番号を振ると、配列にそのまま並べられます。番号 k の節の子は 2k と 2k+1 番になります。

2分木のすべての節を1回ずつたどることを巡回（走査）といい、根をいつ処理するかで3通りに分かれます。代金の式 (300 + 200) × 2 を、根が「×」、その左の子が「+」（さらにその左右に300と200）、右の子が「2」という2分木で表して、たどり方を比べます。

根を先に処理してから左の部分木、右の部分木の順にたどるのが先行順で、「× + 300 200 2」になります。左の部分木、根、右の部分木の順が中間順で、「300 + 200 × 2」と、ふだんの式の並び（括弧は消える）になります。左の部分木、右の部分木、根の順が後行順で、「300 200 + 2 ×」です。後行順で読むと、スタックで計算できる後置記法の式がそのまま得られます。

基本情報の範囲ここまで

ここから基本情報！探しやすい木、偏らない木、大きいものが上の木

データを効率よく探せるように、値の大小などの決まりに従って組み立てた木を、まとめて探索木と呼びます。その代表が2分探索木で、どの節についても、左の部分木には自分より小さい値、右の部分木には自分より大きい値だけが入ります。根を250円にし、左に180円、右に360円、180円の右に200円、360円の左に280円を置いた木なら、280円を探すときは「250より大きいので右」「360より小さいので左」と左右を選び、3回目の比較で280円に着きます。2分探索木を中間順でたどると、値が小さい順に並んで出てきます。

ただし、2分探索木は入れる順番によって形が崩れます。180円、200円、250円、…と安い順に入れると、どの節も右の子しか持たず、1列のリストと同じ形になり、探すたびに端から順にたどることになります。そこで、どの葉までの深さもなるべくそろうように、追加や削除のたびに形を整える木をバランス木（平衡木）と呼びます。

バランス木の一つがAVL木で、どの節でも左右の部分木の高さの差が1以下になるように保たれた2分探索木です。差が2になりそうなときは、節のつなぎ方を組み替えて（回転させて）高さをそろえます。もう一つのB木は、1つの節に複数の値を持たせ、子もたくさん持てるようにした、高さのそろった多分木です。木が低く保たれるので、読み出しの遅い記憶装置から少ない回数で目的の場所に着けます。データベースやファイルシステムの索引に使われています。

探すためではなく、いちばん大きい（または小さい）ものをすぐ取り出すための木もあります。どの節でも、親の値が子の値以上（または以下）になっている木をヒープといいます。親が子以上のヒープなら、最大の値はいつも根にあります。ふつうは完全2分木の形で作り、根を取り出したら、最後尾の節を根に移して、子と比べて入れ替えながら下ろしていき、ヒープの条件を回復させます（ヒープの再構成）。優先度の高い仕事から順にこなすキュー（優先度付きキュー）を作るときに使われます。

基本情報の範囲ここまで

ここから基本情報！流れ図の記号

流れ図の記号は、日本産業規格の JIS X 0121（情報処理用流れ図・プログラム網図・システム資源図記号）で決められています。データの記号のほかに、よく使うものを表にまとめます。

流れは上から下、左から右が基本で、その向きに進むときは線に矢印を付けなくてかまいません。判断の記号からは、「はい」「いいえ」のように条件の結果を書き添えた線を2本以上出します。ループ端は、上の記号（始端）と下の記号（終端）に同じ繰返しの名前を書いて対にし、終わる条件を書き添えて、そのあいだの処理をくり返します。

基本情報の範囲ここまで

ここから基本情報！ほかの整列の手順

挿入ソートは、並べ終えた部分に、残りの要素を1つずつ正しい位置へ差し込んでいく方法です。手に持ったトランプを並べるやり方と同じです。最初の「280」を並べ終えた部分とし、次の150円を280円の前に差し込んで「150, 280」、420円は後ろにそのまま、200円は150円と280円のあいだに差し込みます。元のデータがほぼ並んでいるときは、差し込む手間が少なく速く終わります。

その長所を生かしたのがシェルソートです。まず一定の間隔（たとえば4）だけ離れた要素どうしで挿入ソートを行い、間隔を2、1と狭めながらくり返します。最初の粗い並べ替えで大まかに並ぶので、最後の間隔1の挿入ソートは少ない手間で済みます。

マージソートは、データを半分、また半分と、要素が1つになるまで分け、分けたものを併合しながら大きな列に戻していく方法です。「280, 150」と「420, 200, 360」に分け、さらに分けて1つずつにしてから、「150, 280」「200, 360, 420」と併合し、最後にこの2つを併合して完成させます。

ヒープソートは、データを親が子以上になるヒープの形に組み、根にある最大の値を取り出しては残りをヒープに組み直す、をくり返します。取り出した順に後ろから並べれば、小さい順の列になります。

基本情報の範囲ここまで

ここから基本情報！比べずに場所を計算する探し方

比べる回数をさらに減らすには、データの置き場所そのものを計算で決めてしまいます。キーの値（商品番号など）を計算式（ハッシュ関数）にかけて格納する位置を求め、探すときも同じ計算をして、その位置を直接調べる方法をハッシュ表探索法といいます。商品番号を10で割った余りを位置にすると決めれば、商品番号 137 のあんバターは7番の箱にあり、1回で見つかります。

ただし、商品番号 247 も余りは7です。違うキーから同じ位置が求まることを衝突（シノニムの発生）といい、空いている別の位置に入れる、同じ位置にリストでつなぐ、などの工夫で対処します。衝突が少なければ、データがいくつあっても平均的にほぼ一定の手間で探せます。

位置を求める計算の方式もいくつかあります。10進数のキーの数字の並びを、別の基数の数（たとえば11進数）とみなして10進数に計算し直し、その結果の一部（下の何桁かなど）を位置として使う方式を基数変換法といいます。数字の並びをかき混ぜて、キーの偏りが位置の偏りにならないようにする工夫です。

基本情報の範囲ここまで

ここから基本情報！自分を呼ぶ手順と、手順の速さの物差し

ある手順が、その途中で自分自身を使うことを再帰といい、関数や手続きが自分自身を呼び出すことを再帰呼出しといいます。再帰で書くときは、「範囲が1つになったら終わり」のような終わりの条件が欠かせません。終わりの条件がないと、呼出しが止まらずにくり返されます。

再帰で書ける代表的なアルゴリズムに、2つの整数の最大公約数を求めるユークリッドの互除法があります。クロワッサン48個とマフィン36個を、どの箱も同じ中身になるように、できるだけ多くの箱に分けたいとします。答えは48と36の最大公約数です。互除法では「大きいほうを小さいほうで割った余り」を使い、48 ÷ 36 の余りは12なので、48と36の最大公約数は36と12の最大公約数に等しくなります。36 ÷ 12 は割り切れる（余り0）ので、答えは12箱です。1箱にクロワッサン4個とマフィン3個が入ります。

問題を同じ種類の小さな部分問題に分け、それぞれを解いてから結果をまとめて元の問題を解く方法を分割統治法といいます。クイックソートとマージソートは、分割統治法の代表です。部分問題は元の問題と同じ形なので、再帰で書くと手順が短くなります。

全部の組み合わせを並べると多すぎるときは、試しながら進み、うまくいかないと分かった時点で1つ前の分かれ道に戻って別の道を試す方法もあります。これをバックトラッキングと呼びます。詰め合わせの箱に、合計がちょうど1,000円になるようにパンを選ぶなら、高いものから入れていき、1,000円を超えた時点で最後の1つを外して次の候補を試します。超えた先の組み合わせは調べずに済みます。

アルゴリズムどうしの速さを比べる物差しにオーダ（O記法）があります。データの数を n としたとき、手間が n に比例するなら O(n)、n の2乗に比例するなら O(n²) と書きます。細かい係数は無視し、n が大きくなったときの増え方だけを見ます。

表の回数は増え方を比べるための目安で、実際に比べる回数そのものではありません。また、クイックソートは、基準の値の選び方が悪く分け方が偏り続けると、O(n²) まで遅くなります。

基本情報の範囲ここまで

ここから基本情報！グラフの表し方とたどり方

こむぎ堂の配達のグラフは、店と公園前が4分、店と駅前が2分、駅前と公園前が1分、公園前と学校が3分、駅前と学校が6分の道でつながっています。どの頂点とどの頂点がつながっているかを、頂点を行と列の両方に並べた表に、つながっていれば1、いなければ0で書き込んだものを隣接行列といいます。1の代わりに重みを書き込むこともあります。

グラフの頂点を残らずたどる方法は、大きく2つあります。1本の道を行き止まりまで深く進み、行き止まったら1つ前の分かれ道に戻って別の道を進むのが深さ優先探索です。戻る先を覚えておくのに、スタックや再帰を使います。出発点から近い頂点を、同じ距離のものから全部調べてから、1つ遠い頂点へ進むのが幅優先探索で、次に調べる頂点をキューにためておきます。木も、輪にならないグラフの一種なので、同じ2つのたどり方が使えます。

配達で知りたいのは、店から学校までいちばん早く着く道です。辺の重みの合計が最小になる道を見つける処理を最短経路探索といいます。代表的な方法がダイクストラ法で、出発点からの距離がまだ確定していない頂点のうち、いま分かっている距離が最も小さいものを1つ確定させ、そこから延びる辺で隣の頂点の距離を更新する、をくり返します。

店から学校へは、駅前と公園前を通る6分の道が最短です。駅前から学校へ直接行く道（合わせて8分）は、近道に見えて遅いことが分かります。

ダイクストラ法は、辺の重みに負の値がないことを前提にしています。重みに負の値を含むグラフでも最短経路を求められるのがベルマンフォード法で、すべての辺について距離の更新をくり返します。ダイクストラ法より手間はかかりますが、回るたびに合計が小さくなり続ける輪（負の閉路）があることも見つけられます。

基本情報の範囲ここまで

ここから基本情報！文字列を探す、縮める、記録を集計する

ある文字列（パターン）が、別の文字列の中のどこに現れるかを探す処理を文字列照合といいます。いちばん素直な方法は、「あんバターパン」の先頭に「バター」を重ねて1文字ずつ比べ、合わなければ1文字右にずらしてまた比べる、をくり返すやり方です。「あんバ」は合わず、「んバタ」も合わず、3文字目から重ねたとき「バター」が一致します。合わなかったときに、どれだけ大きくずらしてよいかを工夫して、比べる回数を減らす方法もあります。

文字列を短い符号に置き換えて、データを小さくする方法もあります。よく出る文字には短い符号を、まれな文字には長い符号を割り当てる方式がハフマン方式（ハフマン符号化）です。4種類の文字A・B・C・Dの出る割合が、50%・25%・12.5%・12.5% だとします。どれにも2ビットずつ割り当てると、1文字あたり2ビットです。Aに「0」、Bに「10」、Cに「110」、Dに「111」を割り当てると、1文字あたりの平均は 0.5×1 + 0.25×2 + 0.125×3 + 0.125×3 = 1.75ビットに減ります。どの符号も、ほかの符号の頭の部分になっていないので、つなげて送っても区切りを間違えません。

ファイルの処理では、まず記録を日付や商品番号の順に整列し、必要なら複数のファイルを1つに併合してから、集計に進むのが基本の流れです。キーになる項目の順に並んだ記録を先頭から読み、キーの値が変わったところで小計を出すなどの処理をする方式をコントロールブレーク処理といいます。日付順に並んだ売上の記録を読みながら金額を足していき、日付が10月1日から10月2日に変わった時点で「10月1日の合計」を書き出し、合計を0に戻して次の日を足し始めます。

出した数字を、人が読める形に整える処理を編集処理といいます。「52300」を「52,300円」とする、日付を「10月1日（水）」の形にそろえる、見出しや罫線を付けて帳票の形にする、などがその例です。

基本情報の範囲ここまで

ここから基本情報！文を読み取る段階

文の意味を読み取る処理は、いくつかの段階に分けられます。最初の段階が、文を意味を持つ最小の単位（形態素）に区切り、それぞれの品詞を決める形態素解析です。日本語は単語のあいだに空白がないので、この段階が特に要ります。「店長が焼いたパンを買った」なら「店長／が／焼い／た／パン／を／買っ／た」と区切り、「店長」は名詞、「が」は助詞、と決めていきます。

次に、文法の決まりに従って、語どうしがどう組み合わさって文を作っているかという構造を調べるのが構文解析です。日本語では特に、どの語がどの語を修飾・補足しているかという関係を調べる係り受け解析がよく使われます。「店長が焼いたパン」では、「店長が」は「焼いた」に係り、「焼いた」は「パン」に係ります。

構造が分かったら、その文が何を表しているかを調べるのが意味解析です。たとえば「パンを買った」の「パン」が食べ物を指すことや、買ったのが誰かを決めます。さらに、1つの文だけでは決まらない意味を、前後の文の流れから決めるのが文脈解析です。「クロワッサンを買った。それが少し固かった」の「それ」がクロワッサンを指すと決めるのは、文脈解析の仕事です。

文を細かく解析するのとは別に、文字や単語を、連続するn個ずつのまとまりに区切って扱う方法もあります。これをn-gramといいます。「こむぎ堂」を2文字ずつ区切ると「こむ」「むぎ」「ぎ堂」になります。単語に区切らなくても使えるので、検索の索引作りなどに使われます。

2つの文章がどれくらい似ているかを数値で表したものが文章間類似度です。たとえば、それぞれの文章に出てくる単語やn-gramを数え、共通する部分が多いほど大きな値になるように計算します。「クロワッサンが少し固かった」と「クロワッサンが固くてもおいしい」は、「クロワッサン」「固い」を共有するので、「配達が早かった」より似ていると判断されます。

基本情報の範囲ここまで