プログラム設計(アルゴリズム、データ構造、プログラミング技法)
この章で覚えておきたいこと
- 線形探索は 整列不要、二分探索は 整列済みが前提 です。
- 選択ソートは 最小値や最大値を探して所定位置へ置く、バブルソートは 隣同士を比較して交換する 方法です。
- キューは FIFO、スタックは LIFO です。
- ハッシュ法は高速探索に向きますが、衝突処理が必要 です。
- AND、OR、NOT は、日本語条件を論理式へ直してから考えます。
- 正規表現は 文字列パターン処理 であり、順位付けや集計そのものには使いません。
- Python の辞書は キー:値 の組で、入れ子では外側のキーから順にたどります。
基本知識
探索アルゴリズム
線形探索は、先頭から順に目的の値かどうかを調べる方法です。単純ですが、整列していないデータにも使えます。
二分探索は、整列済みのデータで中央と比較し、探索範囲を半分ずつ狭める方法です。速いことだけを覚えるのではなく、整列済みでなければ使えない ことを確実に押さえます。
ハッシュ法は、キーから格納位置を求めるため高速探索に向きます。ただし、異なるキーが同じ位置になる 衝突 が起こり得るため、その処理方法を持つ必要があります。
整列アルゴリズム
選択ソートは、未整列部分から最小値または最大値を見つけ、先頭や末尾の所定位置へ移します。文章題で「最も小さい値を見つけて先頭と交換する」とあれば選択ソートを疑います。
バブルソートは、隣り合うデータを比較し、順序が逆なら交換する処理を繰り返します。1回の走査で最大値または最小値が端へ押し出されるのが特徴です。
平均や合計を求めるだけなら、通常は整列は不要です。処理速度の問題では、不要なソートや重複走査を減らす発想が問われます。
データ構造
キューは先に入れたものを先に取り出す FIFO の構造で、待ち行列や印刷ジョブに向きます。スタックは後に入れたものを先に取り出す LIFO の構造で、関数呼出しや戻る操作のイメージです。
配列は同種データを順に持つ基本構造です。表形式データでも、1件分をレコードとして持てば一次元配列で扱えます。表だから必ず二次元配列 とは限りません。
Python の辞書は、キーと値の組でデータを持つ連想配列です。2022年度第2問では、入れ子になった辞書の参照順序がそのまま問われました。存在しないキーを参照する記述は誤りになりやすいです。
条件式と流れ図
条件式では、AND は条件を狭め、OR は条件を広げます。日本語の「かつ」「加えて」は AND、「または」は OR と置き換えます。
IF 文や判定表の問題では、すべての組合せを漫然と追うより、結果が変わる境界ケースを先に見つけると整理しやすいです。2023年度や過去問の論理式問題でも、条件の入れ子と括弧の解釈が得点差になっています。
流れ図や擬似コードは、頭の中だけで追わず、変数表を作って1行ずつ更新します。
| 手順 | 確認すること | ひっかけ | |---|---|---| | 1 | 初期値を表に書く | 初期値を処理後の値で上書きして始めない | | 2 | 判定条件を評価する | 未満 と 以下、> と >= を取り違えない | | 3 | 条件が真のときの処理だけ実行する | 分岐しなかった側の代入を勝手に行わない | | 4 | カウンタや添字を更新する | 更新前の値で出力するのか、更新後の値で出力するのかを分ける | | 5 | 終了条件を再判定する | 最後の1回を数え忘れる、または1回多く数える |
特にループ回数は、1からnまで なのか、0からn-1まで なのかで変わります。配列の添字やカウンタが出たら、「判定、処理、更新」の順序を問題文の矢印どおりに追うことが重要です。
計算量と処理速度
診断士試験では厳密な計算量の証明までは求められませんが、件数が増えると操作回数がどう増えるかの感覚は必要です。
線形探索は件数に比例して調べる回数が増えやすく、二分探索は整列済みなら探索範囲を半分ずつ減らせます。同じデータを何度も読み直す処理や、不要な整列を加える処理は遅くなりやすいと理解しておきます。
正規表現と言語の基礎
正規表現は、文字列の検索、抽出、置換、入力検証に使う道具です。2023年度第1回第2問では、文字列処理に使える場面と、売上ランキングのような数値集計には向かない場面の見極めが問われました。
Python はデータ分析や機械学習でもよく使われる汎用言語で、インデントでブロックを表します。SQL はデータベース操作の問い合わせ言語であり、Python と同じ分類ではありません。言語問題は、用途と特徴の対応 を問う形で出やすいです。
この章のまとめ
- 探索は 整列の要否、整列は 手順の動詞、データ構造は 取り出し順序 で見分けます。
- 二分探索、選択ソート、バブルソート、ハッシュ法は、それぞれ典型的な説明文を覚えておくと強いです。
- キューとスタック、配列と辞書、正規表現と集計処理のように、役割の違うものを同じ言葉で混同しないことが重要です。
- 条件式では、日本語を論理式に翻訳してから考えると、入れ子や括弧の問題で崩れにくくなります。
- Python や正規表現の出題は増えているため、最新トピックでも 用途の切り分け を重視します。
一次試験過去問での出方
2021年第6問では Python の特徴、2022年第2問では辞書型、2023年度第1回第2問では正規表現の用途が問われました。過去には 2014年第5問で選択ソート、バブルソート、二分探索、ハッシュ法、2013年第5問でキューとスタック、2015年第5問で IF 文の条件判定も出ています。近年の言語問題が増えても、土台は 探索、整列、データ構造、条件式 のままです。