基本情報技術者試験の最大の難関はアルゴリズム問題です。
アルゴリズムの解説や勉強法、コツを検索すると「トレースしましょう」と言われます。
たしかに、問題文の意味を理解し、プログラムの動き通りに考え、丁寧にトレースすれば全問正解も容易でしょう。
しかし、問題文の解釈が難しい！プログラムの動きが分からない！穴埋めが分からない！丁寧にトレースする時間がない！と多くの人がなるはずです。
私もそうでした。解説を読めば何となく分かるけど解き方が分からない！という状態で、どうやって読めば本番で合格できるのだろう..と悩んでいました。
そこで、基本情報技術者試験の一合格者として、実際に解く際に「どこに着目して、どういうメモを取って、どういう風にトレースしているのか」を解説してみようと思いました。
本記事では平成30年春期の過去問を使います。
参考書や各種サイトの丁寧で完璧な解説ではなく、合格者のノートや手元を覗き見る気持ちで読んでください。
導入部分を読む
まずはどんなことをするのか日本語ベースで読んでいきます。
「ヒープの性質」が分からなくても文中で説明されるので焦らなくて大丈夫です。
他の年度でも言えることですが、問題で使うアルゴリズムを知っていれば有利になりますが、知らないからと言って解けない問題ではありません。
例では7つの整数に対しヒープを作成しています。
説明文と図を照らし合わせて「この問題のヒープはどうなっているのか」を確認してください。
プログラム1の説明を読む
早速プログラムの説明を読んでいきましょう。
この時のポイントは「このプログラムは何をしたいんだ？」というゴールを意識して読むことです。
今回のプログラムでは「ヒープの性質」を利用してデータを昇順に並べることがゴールです。
図1の例だと、「5, 10, 15, 20, 30, 45, 60」と並べられればOKです。
プログラム1の説明です。
プログラム1は副プログラムmakeHeapがメインの処理です。名前からしてヒープを作成するのでしょう。
ここでプログラム（ソース）と引数の使用をさらっとチェックすると全体像がつかめて良いです。
ただし闇雲にプログラムから理解しようとするとタイムオーバーになってしまいます。
さらっと「ループや分岐の数」「規模感（何行くらいか）」「穴埋めがあるか」「コメントアウトを読む」程度にとどめておくと良いと思います。
では説明文からmakeHeapに出てくる登場人物（変数とか配列とか）をチェックしていきます。
- Data[] ： 元の（無秩序な並びの）データが入っている配列
- heap[] ： ヒープの性質を満たした配列
どうやらData[]をなんやかんや処理してheap[]を作り出すようです。
(2)①～③は実際の例と照らし合わせて理解しましょう。
図1も確認しつつ、しっかりとheap[]の特徴をつかんでください。
(4)には図2の矢印の関係をつなげる便利関数の存在が記載されています。
このような詳しいプログラムの中身が書かれていない関数に関しては、引数（入力）と戻り値（出力）を把握しておけばOKです。
どれも基準の要素番号を入れると、それに対する子または親の要素番号を返してくれる関数です。
続いて(5)も便利関数ですね。二つの要素番号を渡すので引数の順番には注意が必要かもしれません。
設問1を解く
やることが見えたところで早速プログラムの穴埋めをしていきます。
対象は2か所で、空欄ａは条件分岐の条件式、空欄ｂは値を交換する関数swapの第三引数を答える問題です。
一番外側のループ条件は変数ｉが0～hnum未満、つまり図1・図2の例ではhnum=7なので、0, 1, 2, … , 6と繰り返すループとなります。
2行目でheap[]にdata[]を追加し、3行目で変数ｋに変数ｉの値を格納しています。
変数ｉおよび変数ｋは要素番号を示す変数ですね。
内側のループの条件は変数ｋが0より大きいとき。つまり1回目の変数ｉ=0の時は条件に当てはまらないが、それ以降の外側ループの時は内側ループに入ると解釈できます。
設問を解くときは2回目のループ以降でトレースをした方が良さそうです。
次の空欄ａで条件分岐しています。
空欄ａの条件が正なら変数ｋに格納している数字と、空欄ｂに格納しているデータとを交換するようです。
全体像が見えたところで選択肢を確認しつつ空欄を埋めていきましょう。
空欄ａを解く
選択肢を確認してみます。
選択肢が多くて一瞬嫌になりますが、よく見ると左辺は同じで不等号の向きが2種類、右辺が3種類の様です。
選択肢を日本語で解釈してみます。
- ア：要素番号ｋのデータが、要素番号ｋの左子よりも大きい。
- イ：要素番号ｋのデータが、要素番号ｋの親よりも大きい。
- ウ：要素番号ｋのデータが、要素番号ｋの右子よりも大きい。
- エ：要素番号ｋのデータが、要素番号ｋの左子よりも小さい。
- オ：要素番号ｋのデータが、要素番号ｋの親よりも小さい。
- カ：要素番号ｋのデータが、要素番号ｋの右子よりも小さい。
この中から、並べ替えを行わなくてはならない条件を導ければ空欄ａの問題はクリアです。
ちなみに2回目のループの現状はこんな感じの想定です。（Data[]には適当に数字を入れてます）
今の状態のheap[]だと、そもそも要素番号ｋに対する左右の子は存在しないので比べようがありません。
そしてヒープの性質として親は子以上の数である必要があります。
逆に考えるともし今親が子よりも小さければ入れ替えなければなりません。（メモの状態がまさにこれ！）
よって空欄ａに入るのは選択肢イになります。
空欄ｂを解く
今度もはじめに選択肢を確認します。
ここでは関数swapの引数を選びます。すでに対象の配列がheap[]であること、入れ替え対象の一つが変数ｋであることが分かっています。
関数swapは要素番号を引数に取ると説明文にあるので、この時点でウかエに絞ることができます。
選択肢ウは変数hnumが変化しないため常に固定値となるので入れ替え対象としては不適です。
選択肢エはメモで言うと要素番号0を指すのでOKです。
プログラム2の説明を読む
続いてプログラム2へと読み進めましょう。
設問2のプログラムではヒープの性質を満たしている配列heap[]を使って、今回の大問の目的である昇順の整列を行うもののようです。
ここからはその具体的なやり方が書いてます。
まずはheap[]を「整列対象領域」と「整列済みデータ領域」に区別する必要があるようです。
この区別の境界として変数lastを使うようです。
一番最初、つまり配列heap[]を受け取った直後は変数lastがhnum-1…このようなイメージです。
※整列対象を「」でくくってます。
読み進めていきます。
文章が長いですが、ひとつづつ確認していきましょう。
heap[0]が最大値となっているのはOKですね。heap[0]は根なのでそのはずです。
次にheap[0]とheap[last]（初回はheap[6]ですね）の値を交換します。
最終的に欲しい配列は昇順（大きい数字が最後）なのでこの処理が入るのでしょう。
そしてlastを一つ先頭側へずらす…最大値が最後に入っているのでそこはもう「整列済みデータ領域」ということですね。
このように大きい値を後ろから詰めていく処理という概要が判明しました。
設問2を解く
設問2はプログラムの穴埋めではなく文章の穴埋めです。
先に文章を確認してからプログラムの確認という手順で進みたいと思います。
図2の例を使って解いていくようです。別の例じゃないあたり親切設計です！
早速最初の空欄ｃをサクっと解いちゃいましょう！
空欄ｃを解く
1回目の繰り返し処理ということでトレース量は少なくて済みそうです。
ここでは1回目のheap[0]とheap[last]の値を交換した後のheap[0]に入っているデータを答えます。
1回目なのでheap[last]はheap[6]となり中身は20です。
答えは選択肢エですね。サービス問題なので確実に取りたいです。
空欄ｄを解く
ヒープの性質を満たす配列を作成するプログラムです。
設問１と異なる点はどんどん並び替える対象が減っていく点でしょうか。
上から順番に登場人物と役割を確認していきます。
- hlast ：整列対象領域の最後。last-1。
- n ：要素番号。大きさ比較対象。初期値は0。
- tmp ：要素番号。要素番号ｎの左の子、または右の子の要素番号。
文章を読むと空欄ｄに当てはまるのは変数tmpに入れる要素番号を「左の子にるすか右の子にするか」を決める条件の様です。
選択肢と該当のプログラムを見ていきます。
選択肢は不等号の種類を問うものです。
アプローチとしては空欄前後の日本語と意味が合致する行を探す..が王道です。
5行目を見てください。
変数tmpに要素番号ｎの左の子の要素番号を格納しています。ここが(2)の一文目と同じですね。
6行目の分岐では要素番号ｎの右側の子の要素番号が変数hlast以下なら、つまり「要素番号ｎの右側の子が今回のヒープ整列対象内なら」という条件を示しています。
説明文では「要素番号ｎの子が二つあり」の部分に当たります。
そして7行目。7行目の条件を満たせば、変数tmpに要素番号ｎの右の子の要素番号を格納しなおす処理が走ります。
以上より空欄ｄの答えは「heap[tmp]≦heap[rchild(n)]」に該当するものと分かります。
heap[tmp]には5行目で左の子の要素番号が入っているので、空欄ｄの答えはイの「以上のときには」が入ります。
空欄ｅを解く
もう一度該当の動作説明を載せます。
11行目以降の説明です。
初回の15行目の処理の内容を問う問題で、選択肢はどれも可能性はあるので素直にトレースしていきたいと思います。
11行目までの処理完了時点でそれぞれの変数が指しているのはこの通りになります。
メモとしては最低限「変数ｎが指しているもの」「変数tmpがさしているもの」は記載しておきましょう。
この状態で11行目の条件「heap[tmp]＞heap[n]」、つまり「45＞20」を満たしているので、値を交換します。
11行目の条件を満たすと15行目に進むことができます。
このとき変数tmpの値は更新されていないので、右の子の要素番号である2が空欄ｅに当てはまります。
答えはイです。
おわりに
最後まで読んでくださりありがとうございます。
問題は解けましたか？
今回紹介した解き方がすべてのアルゴリズム問題に適応できるわけではありませんが、一つ一つ読み解いていけば合格へ近づきます。
少しでもアルゴリズム問題に対する苦手意識が減ってくれると嬉しいです。
一合格者の個人的な感想ですが、今期の問題は分かりやすく、アルゴリズム問題で頻出の基本的な処理の理解に活用できる問題だと思います。
勉強し始めの方、この問題の仕組みを理解できれば別の初見の問題の正答率が上がると思います。
勉強中盤の方、この問題を20分で解ければアルゴリズム問題を読むスピードとして申し分ないと思います。
最後に公式の講評を貼っておきます。ご自身の正答率と比較してみてください。
コメント