アルゴリズムとフローチャート
データ構造とは、プログラムの中でデータをどう入れておくかという型のことで、配列やリスト、スタック、キュー、木構造などがあります。アルゴリズムとは、問題を解決するための手順を明確に定めたものです。
アルゴリズムとデータ構造の基本的な考え方を理解し、フローチャートの記号の意味を読み取れるようになります。また、代表的な整列(ソート)や探索(サーチ)のアルゴリズムの考え方を説明できるようになります。
データ構造とフローチャートは、単元27の擬似言語問題を読み解くための土台になります。スタックとキューのような似た構造の区別や、判断記号の読み方を正確に押さえておくと、この先の学習がぐっと楽になります。
データ構造の基礎
アルゴリズムとは、ある問題を解決するための手順を、誰が実行しても同じ結果が得られるように明確に定めたもののことです。料理のレシピが「材料をこの順番で、この分量だけ使えば、決まった料理ができあがる」手順を示すのと同じように、アルゴリズムはコンピュータに「この順番でこの処理を行えば、目的の結果が得られる」手順を示します。そのアルゴリズムを実際にコンピュータで動かすには、扱うデータをどう入れておくかという設計も欠かせません。仕事でたくさんのデータを扱うときは、データをどう入れておくかという「入れ物」の設計が大切になります。この入れ物の形のことをデータ構造と呼びます。
一つの値を入れておく箱を変数、同じ種類の値を順番に並べて入れておく棚を配列と呼びます。氏名や住所など、種類の異なるデータを一件分にまとめたものをレコード、レコードをたくさん集めたものをファイルと呼びます。
配列に似た構造にリストがあります。配列はデータを連続した順番で並べるのに対し、リストは一つ一つのデータが次のデータの場所を指し示す形でつながっており、途中への挿入や削除がしやすいという特徴があります。
よく出題されるのがスタックとキューです。スタックは、最後に入れたデータを最初に取り出す構造で、積み重ねたお皿を上から取っていくイメージです。この性質をLIFO(Last In First Out、後入れ先出し)と呼びます。ブラウザの「戻る」ボタンが、直前に見たページから順にさかのぼる動きは、この仕組みに近い例です。キューは反対に、最初に入れたデータを最初に取り出す構造で、窓口に並ぶ行列のイメージです。この性質をFIFO(First In First Out、先入れ先出し)と呼びます。プリンタの印刷待ちが依頼した順番どおりに出力されるのは、この仕組みに近い例です。両者の違いは、データを取り出すときにどちら側の端から取るかという一点にあります。
もう一つよく出てくるのが木構造です。木構造は、データを親子関係でつないで階層状に表す構造で、会社の組織図やパソコンのフォルダ構成をイメージするとわかりやすいです。木構造のうち、一つの要素(ノード)が持てる子の数が最大2つまでのものを、特に2分木と呼びます。
どのデータ構造を選ぶかによって、データの追加や取り出しのしやすさが変わってきます。試験では名前と特徴(取り出す順番、階層の有無)を結びつけて覚えておけば十分対応できます。
フローチャートの基本記号
フローチャート(流れ図)は、アルゴリズムの手順を図記号と矢印で視覚的に表現したものです。記号の形にはそれぞれ意味が決まっており、この意味を正確に覚えておくことがフローチャートを読み解く第一歩になります。日本語で「今日の仕事の進め方」を書いた業務フローと基本的な考え方は同じで、対象がコンピュータの処理になったものだとイメージするとつかみやすくなります。
角が丸い長方形(または楕円)は端子記号と呼ばれ、処理の「開始」と「終了」を表します。フローチャートは必ずこの記号から始まり、この記号で終わります。長方形は処理記号で、計算や代入などの具体的な処理内容を表します。「変数xに1を代入する」といった処理はこの記号の中に書かれます。
ひし形は判断記号で、条件によって処理の流れが枝分かれすることを表します。「xは10より大きいか」といった条件を判断記号の中に書き、条件が成り立つ場合(YES)と成り立たない場合(NO)とで、矢印が2方向に分かれます。この判断記号がフローチャートの中で最も試験に頻出する記号です。矢印が必ず2方向に分かれる点を忘れると、片方の結果しか読み取れず、正解を選び間違える原因になります。
このほか、平行四辺形は入出力記号で、データの入力や出力(画面への表示など)を表します。矢印は処理の流れる方向を示し、上から下、あるいは左から右に処理が進んでいくのが基本です。
これらの記号を組み合わせることで、「順次(上から順番に実行する)」「選択(条件によって処理を分岐する)」「繰り返し(条件を満たす間、同じ処理を繰り返す)」という3つの基本的な処理の構造をすべて表現できます。この3つの構造は構造化プログラミングの基本要素でもあり、単元27の擬似言語の理解にも直接つながります。試験問題を解くときは、まず端子記号で開始と終了の位置を確認し、次に判断記号がどこにあるかを探すと、全体の流れをつかみやすくなります。
整列(ソート)と探索(サーチ)の考え方
アルゴリズムの中でも、特によく出題されるのが整列(ソート)と探索(サーチ)です。
整列とは、複数のデータをある基準(数の大小や五十音順など)に従って並べ替える処理です。代表的な整列アルゴリズムにバブルソート、選択ソート、クイックソートがあります。バブルソートは、隣り合う2つのデータを比較し、順序が逆であれば入れ替える、という操作をデータの列全体に繰り返し行うことで、少しずつ正しい順序に並べ替えていく方法です。データが1回の走査で少しずつ「浮き上がる」ように移動していく様子が、泡(バブル)が水面に上がる様子に似ていることから、この名前がついています。選択ソートは、未整列の部分から最小(または最大)のデータを毎回選び出し、先頭から順に確定させていく方法です。クイックソートは、基準となる値を決めて、それより小さいグループと大きいグループに分ける操作を繰り返すことで、データが多いときでも比較的高速に並べ替えられる方法です。
探索とは、複数のデータの中から目的のデータを見つけ出す処理です。代表的な探索アルゴリズムに線形探索と二分探索があります。線形探索は、先頭から順番に一つずつデータを確認していく方法で、データが整列されていなくても使える一方、データの数が多いと時間がかかります。
二分探索は、あらかじめ整列されたデータに対して使う方法で、探索範囲の真ん中の値と目的の値を比較し、目的の値がそれより大きいか小さいかによって、探索する範囲を半分ずつに絞り込んでいきます。例えば1から100までの整列された数字から「73」を探す場合、まず中央の50と比較し、73は50より大きいので後半(51〜100)に絞り込みます。この後半の中央である75と比較し、73は75より小さいので51〜74に絞り込む、というように範囲を半分ずつ狭めていきます。この方法は、データが整列されているという条件付きですが、線形探索よりもはるかに少ない比較回数で目的のデータにたどり着けるのが特徴です。
整列と探索は組み合わせて使われることも多く、あらかじめデータを整列しておいてから二分探索で検索する、という流れは実務でもよく見られます。試験ではアルゴリズムの名前を暗記するだけでなく、フローチャートの形で示された処理を1行ずつ追って、どのアルゴリズムに当たるかを判断させる問題が多く出ます。
この単元の確認問題
答えを見る前に、まず自分の言葉で答えてみてください。言葉にできないところが、そのまま本試験で止まるところです。
Q. 最後に入れたデータを最初に取り出すデータ構造を何と呼びますか。
A. スタックです。この性質をLIFO(後入れ先出し)と呼びます。
積み重ねたお皿のように、後から入れたものほど先に取り出される構造だからです。最初に入れたものを最初に取り出すキュー(FIFO)と対比して覚えるとよいでしょう。
Q. フローチャートで、条件によって処理の流れが枝分かれすることを表す記号は何ですか。
A. ひし形(判断記号)です。
条件が成り立つか成り立たないかによって、矢印がYESとNOの2方向に分かれることを表す記号だからです。
Q. あらかじめ整列されたデータに対して、探索範囲を半分ずつに絞り込みながら目的のデータを探すアルゴリズムを何と呼びますか。
A. 二分探索です。
中央の値と目的の値を比較し、大小関係によって探索範囲を半分ずつ絞り込んでいく方法だからです。データが整列されていることが前提となります。
アルゴリズムとフローチャートは、読んで分かることと、本番で点になることが別です。点にするための材料はこちらにまとめてあります。
- この単元の問題 23問（どこをどう間違えたかまで解説）
- この単元のひっかけ（本試験がどう引っかけてくるか）
- この単元をそのままITパスポート専用AIチューターに質問できます
- 間違えた問題だけを自動で拾い直す復習リスト
「第7章 基礎理論とアルゴリズム」の他の単元
この単元を、手を動かして確かめる
ITパスポートAIチューターでは、いま読んだ単元の四択問題をその場で解いて、 どこで間違えたかまで解説付きで確かめられます。 わからないところはITパスポート専用のAIチューターに訊けます。
この単元をアプリで開く 登録は無料。メールアドレスだけで始められます。