「アルゴリズム」
恐らく基本情報技術者試験を受験しようと思っている殆どの人に、苦手意識がある分野ではないでしょうか？
プログラムを理解したいけど、プログラムをどのように読んだら良いのか分からない
問題が難しすぎる・・・
などなど。
アルゴリズムの勉強をしている人は、大抵こんな悩みを持っているでしょう。
そこで今回は、基本情報技術者試験の鬼門とも言える、アルゴリズムを解くためのコツ、そして頭に入れておきたいポイントについて解説します。
目次
今回は内容がかなり長くなったため、ページを分割させていただきました。
そのため今回の記事では、アルゴリズムで出題される問題の種類やアプローチの方法。
次回の記事では、問題を解くために心がけたいコツやポイントといった内容に重点を置いています。
それではアルゴリズムという強敵を打ち破るため、まずは問題の種類や問題の解き方について解説していきます。
アルゴリズムって本当に難しいよな。それこそ人によっては、アルゴリズムで勉強をやめてしまうぐらいだからな
確かにアルゴリズムで絶望を感じるという人は多いと思う。けどだからと言って、アルゴリズムを捨てるような勉強はしない方が良いね。
アルゴリズム以外で点数を勘定すると痛い目を見るからな
・問題の種類は大きく分けて３つ
アルゴリズムの問題は大きく分けて３つ。
- プログラムの穴埋め
（難易度 低～中） - 途中経過と実行結果を問う問題
（難易度 中～高） - その他の問題
（難易度 低～高）
に分けられます。
問題の出題率
平成２１春期～平成３０秋期
全１２７問
- プログラムの穴埋め
４６問（３６．２％） - プログラムの処理における途中経過と実行結果内容に関する問題
４２問（３３．０％）
実に７割近くの問題が、途中経過と実行結果の内容、プログラムの穴埋めになるため、必ず頭医に入れておいてください。
では問題の種類における特徴や内容の解説をしていきます。
・プログラムの穴埋め問題
プログラムの穴埋めに関しては、以下のような形で問題が出題されます。
ちなみに当てはめる内容についてですが、
- 処理
- 条件式
といった内容が用意されています。
また複数の処理や条件式を丸ごと当てはめるといった選択肢も出題されるため注意しておきましょう。
ちなみに「プログラムの穴埋め」という問題は、アルゴリズムで出題される問題の中では、簡単な部類に入ります。
ただし次の見出しでも書いてある通り、重要度が高い問題でもあるため、手を抜いて勉強しないように注意してください。
※プログラムの穴埋めは間違えてはいけない
「プログラムの穴埋め」における注意点として、
「プログラムの穴埋め」は、できる限り間違えてはいけないという点を頭に入れておいてください。
何故「プログラムの穴埋め」を間違えてはいけないか？
受験生自ら穴埋めをしたプログラムをそのまま流用して次の問題に進むからです。
つまりプログラムの穴埋め問題を間違えていると、
間接的に他の問題を間違える可能性が高くなります。
だからこそ「プログラムの穴埋め」を答える際には、他の問題や解答に繋がると思って、慎重に答えるようにしましょう。
・途中経過と実行結果を問う問題
「途中経過と実行結果を問う問題」において、問題となる箇所は以下の通りです。
- 変数の内容
- 配列の内容
- 実行結果によるデータや値
箇条書きにした要素だけを見ると単純そうですが、実のところ「途中経過と実行結果を問う問題」というのは、アルゴリズムの中でもそこそこ難しい問題に分類できます。
難しい理由としては、データや処理を正しく追う必要があるため、
カンや予測で答えにくく、解答するまで時間が掛かるというポイントがあるためです。
またデータを正しく追うためには、
- プログラムを読んだ回数
- 変数や配列の要素や内容を書き出し慣れておく
といった勉強が重要となります。
またデータを正しく追うという勉強は、短期間で身につくものではないため、じっくりと腰を据えて勉強を進めましょう。
途中経過と実行結果を問う問題の出題例
- 平成３０年秋期
- 平成２９年秋期
- 平成２９年春期
・その他の問題
アルゴリズムで出題される問題の中には、以下のような問題も出題されます。
- 特定の処理が何回実行されたか？
- プログラム自体は何回実行されるか？
- プログラムの処理量は？
- メモリの使用量は？
- プログラムにおいてエラーが起こる原因は？
上記の中で特に注意したいのは、
「プログラムにおける特定の処理が何回実行されたか？」
「プログラムは何回実行されるか？」といった問題。
理由としては、ズバリ出題率が高いといった特徴があるからです。
実行回数を問うような問題を答えられるようにするためには、以下の内容が重要です。
- データの流れを細かくメモしていく
- 配列の内容（要素番号）を書き出す
- ループの回数別にデータの内容と流れを書き出す
また「その他の問題」は、基本的にどの問題もプログラムを読み切ったという前提で出題されるような問題が多いため、全体的に難易度が高いのも注意するべきポイントと言えるでしょう。
その他の問題の出題例
- 平成２７秋期
設問２（特定の処理の実行回数） - 平成２４秋期
「d」 （メモリの使用量） - 平成２１春期
「e」「f」（エラーが起こる原因）
基本的にアルゴリズムの問題は、以下のような形で問題が進んでいくよ
- 「プログラムの穴埋め」
- 「途中経過と実行結果を問う問題」or「その他の問題」
問題の難易度は、後に出題される問題の方が難しくできている
だからこそ「プログラムの穴埋め」は、できる限り間違えないように気をつけたいね
・問題へのアプローチについて
では問題の種類をおさらいしたところで、問題に答える際の解答方法や問題へのアプローチについて解説します。
基本情報技術者試験のアルゴリズムの問題を解く方法は、以下の４つがメインになります。
- データを当てはめて処理を追う
- プログラムの内容を元にデータを予測する
- 有り得ない解答を削る
- 当てはめるデータを変えてみる
具体的に解答方法を確実性や解答に掛かる時間で分けてみると、
- データを当てはめて処理を追う
確実性 高
解答に掛かる時間 多
- プログラムの内容を元にデータを予測する
確実性 中
解答に掛かる時間 中
- 有り得ない解答を削る
確実性 低
解答に掛かる時間 短
- 当てはめるデータを変えてみる
確実性 中
解答に掛かる時間 短
※どうしても解けない問題に使うと、光明が見えてくる可能性アリ
といった具合です。
では１つ１つ解答方法を解説していきます。
・データを当てはめて処理を追う
アルゴリズムの問題を解く上で、
一番確実で正答率が高くなる方法は「データを当てはめて処理を追う」という方法です。
単純ですが実際にパソコン上でプログラムを動かしているのと同様の結果が得られるため、問題から逆算をするような他の方法より確実性が高い方法となっています。
ただし「データを当てはめて処理を追う」という方法は、
問題を解くまでに時間が掛かってしまう解答方法です。
ちなみに「データを当てはめて処理を追う」という方法を利用する際には、
プログラムに当てはめるデータや変数を逐一紙に書き出すというポイントを忘れないようにしてください。
頭の中でデータを当てはめて処理を追うという方法をしてしまうと、アルゴリズムに余程慣れていない限り、確実性が落ちるため注意が必要です。
初めの内から複雑な値を用意すると、思考がまとまりにくく、プログラムを読んで問題に答えるという本質を忘れやすくなるため気をつけてください。
・プログラムの内容を元にデータを予測する
「プログラムの内容を元にデータを予測する」という方法は、
- データが当てはめられないから（面倒だから）プログラムだけを読む
- 時間が無いからプログラムだけを読む
といった状況の時に、やってしまいがちな方法です。
またデータの流れと内容を確認しないまま解答が進むため、自分の知識外の処理が出てくると混乱する方法となっています。
ただデータを当てはめてみる方法と比較すると、プログラムを読む部分は限定されて、データを追う必要もないため時間は掛かりません。
そのため確実性を高めるために、次の見出しで解説している「有り得ない解答を削る」という方法と組みわせると良いでしょう。
・有り得ない解答を削る
「有り得ない解答を削る」という方法は、
問題の解き方がまるで分らない時に有効な方法と言えます。
また選択肢を削る意味合いもあるため、
このくらいの値になるだろうけど、計算式がうまく立てられないな
といった状況の時に、答えを推測するのに使えるでしょう。
他にも問題への解答時間を減らすという意味合いでも、重要度が高い解答方法だと言えます。
ただし「有り得ない解答を削る」という方法は、
あくまでも他の解答方法の補助として使うべき方法であり、答えが分からない時の最終手段として活用した方が良いでしょう。
できる限り自力で解いて、悩みに悩み抜いてから使う方法だと覚えておいてください。
・当てはめるデータを変えてみる
プログラムの処理が、どれだけ考えても分からない・・・
そんな時は視点を変えて、当てはめるデータを変更してみるという方法を試してみてください。
というのも試験で出題される問題の中にはごく少数ですが、エラーデータを想定して作られているプログラムもあります。
そのため単純に正常終了するデータを当てはめているだけだと、正しい解答に辿り着けないパターンも稀にあるため注意しましょう。
ちなみに「当てはめるデータを変えてみる」という方法の
優先順位はかなり低めです。
何故ならばエラーデータを想定した問題は、出題率が低いから。
また下手に「当てはめるデータを変えてみる」という解き方を使うと、時間を浪費する可能性もあるため最終手段として覚えておいてください。
アルゴリズムの問題を解く際には、できる限り「データを当てはめて処理を追う」
という方法を使うようにしよう。
データをキッチリ当てはめて処理を追わないと、実力が付かないのがアルゴリズムの特徴だと言えるからね
地道な努力が物を言う、小手先の技術は通用しにくい。だからこそアルゴリズムは難しいのかも知れないな
まとめ
今回は、アルゴリズムにおける問題の種類と問題へのアプローチについて解説しました。
問題の種類は大きく分けて３つ
- プログラムの穴埋め
（難易度 低～中）
※プログラムの穴埋めは、他の問題への影響を考えて慎重に答える - 途中経過と実行結果を問う問題
（難易度 中～高） - その他の問題
（難易度 低～高）
問題へのアプローチの種類
- データを流してみる
- プログラムの内容を元にデータを予測する
- 有り得ない解答を削る
- 当てはめるデータを変えてみる
それでは次にアルゴリズムの問題を効率よく解くためのコツ、正確に解くためのポイントをチェックしていきましょう。
コメント