擬似言語で押さえるアルゴリズム一覧｜科目Bで出る型を整理して解説

科目Bのアルゴリズムって、結局どこまで覚えればいいんだろう。

範囲が見えないまま勉強を続けて、不安になっていませんか？

参考書を開くと、探索や整列といった名前が次々に出てきます。全部を完璧にしないといけない気がして、手が止まってしまう人は多いはずです。

先に結論をお伝えします。科目Bで出るアルゴリズムは無限にあるわけではなく、いくつかの型に整理できます。

私はエンジニアとして10年以上、Webシステムの開発や運用に携わってきました。日々のコードレビューでも、他人が書いた処理を読むときは同じことをしています。

まず型を見抜き、それから細部を追う。この順番を守るだけで、読む速さはずいぶん変わるものです。

この記事では、科目Bに出るアルゴリズムを一覧に整理し、どの順番で潰していけばよいかまでを見ていきます。

科目Bのアルゴリズムは、4つの型に分けられる¶

はじめに全体像を持っておきましょう。地図がないまま歩くから、範囲が無限に感じられるのです。

出題されるアルゴリズムは、やっていることの性質で分けると4つに収まります。集計、探索、整列、そしてデータ構造の操作です。

どの型も、配列や変数を使って値を出し入れするという点では同じです。違うのは、何のために出し入れしているかという目的のほうになります。

この4つを知っているだけで、参考書の目次の見え方が変わります。ばらばらに並んだ項目が、同じ仲間ごとにまとまって見えてくるからです。

言葉だけでは掴みにくいので、一覧にまとめました。次の表が、この記事全体の地図になります。

上から下へ行くほど、読むのに必要な体力が上がっていきます。逆に言えば、上の型を飛ばして下から始めると苦しくなるということです。

科目Bという科目そのものの位置づけを先に確かめたい場合は、親記事にまとめてあります。

【関連記事】基本情報技術者試験の科目Bとは？擬似言語・アルゴリズム対策を初心者向けに解説

型が分かると、初見の問題でも当たりが付く¶

本番で出るコードは、参考書に載っていたものとは違う顔をしています。それでも解ける人がいるのは、型を知っているからです。

たとえば配列を一周して変数を1つ更新しているなら、それは集計の型です。中身が合計でも最大値でも、読み方の骨格は変わりません。

私が現場で知らないコードを渡されたときも、最初にやるのはこの当たり付けです。何をしようとしている処理かが分かれば、細部の意味は後から埋まります。

覚えるのではなく、動きを再現できるようにする¶

アルゴリズムの学習でよくある失敗は、名前と説明を暗記して終わることです。二分探索は真ん中と比べる、と言えても、コードを追えないなら点にはなりません。

必要なのは、紙の上で値の動きを再現できることです。この差が本番の得点をはっきり分けます。

集計の型：すべての土台になる¶

まずは一番やさしい集計から見ていきましょう。ここが読めないと、他の型はどれも読めません。

集計は、配列を先頭から末尾まで一周し、その間に変数を育てていく処理です。合計を足していくのも、最大値を更新していくのも同じ形になります。

実際の形を見てもらったほうが早いと思います。次は配列の中から最大値を探すコードです。

○整数型: saidai(整数型の配列: data)
  整数型: max ← data[1]
  整数型: i
  for (i を 2 から data の要素数 まで 1 ずつ増やす)
    if (data[i] > max)
      max ← data[i]
    endif
  endfor
  return max

注目してほしいのは、最初の1行です。maxに先頭の値を入れてから、2番目以降と比べています。

ここを0で初期化すると、値がすべて負の数だったときに答えが狂います。実務でも、初期値の置き方が原因の不具合はよく見かけるものです。

合計や件数の数え方をもう少し丁寧に確かめたい人には、専用の記事があります。

【関連記事】擬似言語で合計・最大値・件数を求める方法｜基本情報 科目Bの頻出パターンをやさしく解説

探索の型：見つからなかったときが問われる¶

集計が読めるようになったら、次は探索です。ここからは条件の組み立てが少し複雑になります。

探索は、配列の中から目的の値がどこにあるかを調べる処理です。前から順に見ていく線形探索と、並んでいることを利用して半分ずつ絞る二分探索が代表になります。

出題で狙われるのは、見つかった場合ではありません。見つからなかったときに何を返すか、という部分です。

線形探索の形も見ておきましょう。集計とよく似ていますが、途中で処理を抜ける点が違います。

○整数型: tansaku(整数型の配列: data, 整数型: target)
  整数型: i
  for (i を 1 から data の要素数 まで 1 ずつ増やす)
    if (data[i] = target)
      return i
    endif
  endfor
  return -1

最後の行に置かれた-1が、見つからなかったという合図です。ここを0にするか-1にするかは問題ごとに違うので、必ず本文で確かめてください。

配列の1番目から始まるのか0番目から始まるのかも、設問によって変わります。この前提を読み飛ばすと、答えが1つずれてしまいます。

二分探索では、探す範囲を表す2つの変数がすれ違った時点で終了になります。この終了条件を読み違えると、選択肢を絞りきれません。

線形探索と二分探索の違いは、こちらの記事で図と一緒に整理しています。

【関連記事】擬似言語の線形探索と二分探索をやさしく解説｜基本情報 科目Bのアルゴリズム対策

速さの違いは、ループの形に表れる¶

探索の話には、必ず計算量という言葉が付いてきます。難しく聞こえますが、見るところは決まっています。

配列を一周するだけならデータの数に比例し、半分ずつ絞るなら比例よりずっと緩やかになる。この差がそのまま速さの差です。

ループがどう書かれているかを見れば、おおよその見当は付きます。計算量の考え方は別記事で詳しく扱いました。

【関連記事】擬似言語で学ぶ計算量（オーダー）の考え方｜基本情報 科目Bのアルゴリズム対策

整列の型：途中経過を答えさせる問題が多い¶

探索の次は整列です。ここは手を動かした量がそのまま差になる領域だと感じています。

整列は、値を小さい順や大きい順に並べ替える処理です。隣どうしを比べて交換していく方法や、最小値を選んで前に持ってくる方法などがあります。

設問でよく問われるのは、何回目の繰返しが終わった時点で配列がどうなっているか、という形です。最後の答えだけでは足りず、途中の状態を追う必要があります。

手順そのものを暗記しようとすると、かえって苦しくなります。交換法と選択法の名前が入れ替わっても、コードが読めれば答えは出せるからです。

だからこそ、整列はトレース表を書く練習に向いています。並べ替えの記事では、代表的な手順を一つずつ追いました。

【関連記事】擬似言語のソートアルゴリズム入門｜基本情報 科目Bで出る並べ替えをやさしく解説

データ構造の型：出し入れの規則を先に押さえる¶

最後はデータ構造です。ここは前提の知識がないと、コードだけ見ても意味が取れません。

スタックは後に入れたものから先に出て、キューは先に入れたものから先に出ます。この規則を知らないままコードを読むと、単なる配列操作にしか見えないでしょう。

連結リストや木も同じです。値そのものより、次の要素を指す情報をどうたどるかが中心になります。

この型では、図を描くかどうかで正答率が大きく変わります。頭の中だけで追おうとすると、要素のつながりを一つ取り違えた時点で崩れてしまうからです。

実務で扱うデータも、たどる順番を間違えると別のものを取り出してしまいます。私は今でも、複雑なつながりを追うときは紙に矢印を描いています。

型ごとに、押さえるべき点を並べておきます。次の表を見ながら、自分がどこまで理解できているかを確かめてみてください。

スタックとキューは、擬似言語の中でも登場頻度が高い部類です。仕組みの違いはこちらで解説しています。

【関連記事】擬似言語のスタックとキューをやさしく解説｜基本情報 科目Bのデータ構造入門

木の問題は苦手意識を持たれやすいのですが、たどる順番さえ決まれば作業は単純です。

【関連記事】擬似言語の二分木をやさしく解説｜基本情報 科目Bのデータ構造対策

どの順番で潰していくか¶

一覧を眺めると、量に圧倒されるかもしれません。ただ、全部を同時に始める必要はありません。

順番には理由があります。前の型で使った読み方が、次の型の土台になるからです。

学習の順番を段階に分けておきました。上から順に進めれば、無理なく積み上がります。

1段目に時間をかけるのが結局は近道です。ここが曖昧なまま整列に進むと、どの変数を追えばよいか分からなくなります。

1つの型につき3問ずつでよい¶

何問やれば足りるのかと聞かれることがあります。数を決めておくと進みやすいので、目安をお伝えします。

同じ型の問題を3問続けて解くと、共通する骨格が見えてきます。1問目は手探りでも、3問目には読む順番が身についているはずです。

大切なのは、間隔を空けずに続けることです。1週間空けてから次の1問に進むと、また手探りからやり直しになります。

各段階で共通して必要になるのが、トレース表を書く力です。書き方そのものに不安があるなら、先にこちらを読んでおくとよいでしょう。

【関連記事】擬似言語のトレース表の書き方｜基本情報 科目Bで変数の動きを追うコツ

動かしながら確かめると、定着が速い¶

一覧を頭に入れても、実際にコードが動く様子を見ないと感覚はつかめません。紙のトレースは大切ですが、答え合わせの相手がいるとさらに安心できます。

Giji Academy では、擬似言語のコードを画面上で動かしながら学べます。値がどう変わるかを目で追えるので、自分のトレースが合っていたかをその場で確認できます。

集計の型から順に試してみてください。学習を始める場所はこちらから選べます。

まとめ¶

ここまでの要点を振り返っておきましょう。

科目Bのアルゴリズムは、集計、探索、整列、データ構造の4つの型に整理できます。範囲は無限ではなく、地図を持てば見通しが立ちます。

読むときは、まず型を見抜いてから細部に入るのが順番です。配列を一周して変数を1つ育てているなら集計、というように当たりを付けていきます。

学習は集計から始めて、探索、整列、データ構造へと進めてください。前の型の読み方が、そのまま次の型の土台になります。

覚える対象は名前ではなく、値の動かし方です。名前を忘れても、コードが追えるなら点は取れます。

一覧をそばに置いておけば、初見の問題でも今どの型を読んでいるかが分かるはずです。まずは最大値を探すコードを、トレース表で最後まで追ってみませんか。

そこまでできた時点で、地図の1つ目にはもう色が塗られています。