午後問題の歩き方 | 地道にアルゴリズム問題に取り組む(1)


2023-03-01 更新

error

この記事は基本情報技術者試験の旧制度( 2022 年以前)の記事です。
この記事の題材となっている「午後問題」は現在の試験制度では出題されません。 ご注意くださいませ。

info

基本情報技術者の午後試験の問 6 は、言わずと知れたアルゴリズム問題です。

令和 2 年度の春期から試験配点が 25 点と、さらに高くなり、この問題で得点を稼げるかどうかが、合格のカギを握っているといえるでしょう。

どのように対策したらよいのでしょうか?

私の講師経験からアドバイスさせていただきます。

info 本記事ではわかりやすいよう、問題に背景色を入れています

アルゴリズム問題の克服に近道なし

多くの受験者が、アルゴリズム問題を「苦手だ」といいます。多くの講師も、「苦手だ」といいます。実は、私も「苦手だ」です。

アルゴリズム問題が「得意だ」という人はいないのだろうか、と思っていたところ、「得意だ」「あんな簡単な問題はない」「 5 分でできる」と豪語する講師が 1 人いました。どうやら秘策があるようです。

 

私が「どうやって問題を解くのか教えてほしい」と頼むと、彼は「お前は、おしゃべりだから教えられない」といいました。

彼は、私が雑誌や Web 記事などに秘策を書くと、それが試験の出題者の目に入り、その秘策が使えなくなってしまうことを心配しているのです。

私が「絶対に誰にも言わないから教えてくれ」と懇願すると、彼は「本当だな」と念を押してから、しぶしぶ教えてくれました。

ここで皆さんに、こっそりお教えしますので、誰にも言わないでください。

 

彼の秘策は、「問題を一切見ずに、選択肢だけを見て正解を選ぶ」というものです。例として、以下をご覧ください。これは、プログラムの穴埋め問題の選択肢です。

ア n  イ n2  ウ n2 + 1  エ n2 - 1

問題を示していませんが、どれが正解だと思いますか。

ただの n より、n の 2 乗の方が立派な感じがします。さらに、n の 2 乗に 1 と足したものと、n の 2 乗から 1 を引いたものが並んでいるのですから、きっとどちらかが正解でしょう。

このように判断してウかエを選ぶというのが、彼の秘策です。

 

私が「選択肢を 1 つに絞れないじゃないか!」というと、彼は「 2 つに絞れれば、正答率が 50% になる。苦手なアルゴリズム問題が 50% できれば十分だろう!」と得意顔で答えました。

私は、彼の秘策を「聞かなければよかった」と後悔しました。こんな方法で試験に合格しても、意味がありません。合格しても、嬉しくないでしょう。

ITエンジニアは、きちんと知識を身に着けて、正々堂々と試験を受けてほしいと思います。アルゴリズム問題の克服に近道なしです。

アルゴリズム問題の克服への地道なステップ(その 1 )

ここからは、私からのアドバイスです。

最終的な目標は、過去問題を練習できるレベルまで知識を身に着けることです。

そこにたどり着くまでに、いくつかのステップがあります。これらのステップをクリアしていない状態で過去問題にチャレンジすると、「わからない」「できない」と悩むことになります。

かなり時間がかかることを覚悟して、地道に取り組んでください。もう一度言いますが、「アルゴリズム問題の克服に近道なし」です。

 

最初のステップとして、試験のシラバスに示されている基本的なアルゴリズムとデータ構造を覚えてください。

アルゴリズム問題 苦手克服への地道なステップ その 1

基本的なアルゴリズムとデータ構造を覚える

覚えるとは、手作業でできるようにすることです。

たとえば、トランプのカードを配列の要素に見立てて、以下に示したソートやサーチのアルゴリズムをやってみるのです。
トランプのカードを並べて、以下に示したデータ構造を作ってみるのです。

午後試験のアルゴリズム問題は、「これらの基本的なアルゴリズムとデータ構造を知っていますよね」という想定で出題されます。したがって、知らなければ、問題を解けません。

    【アルゴリズム】

  • バブルソート(交換法)
  • 選択法
  • 挿入法
  • マージソート
  • クイックソート
  • 線形探索法
  • 二分探索法
  • ハッシュ表探索法
    【データ構造】

  • 配列
  • 構造体の配列
  • 連結リスト
  • 二分探索木
  • ヒープ
  • キュー
  • スタック

label 関連記事

午後問題の歩き方 | 過去問 10 回分から分析した午後問題の出題傾向 ( 2019 春期試験 更新)
アルゴリズム及びデータ構造の出題傾向(午後問 8 )

アルゴリズム問題の克服への地道なステップ(その 2 )

次のステップです。

午後試験のアルゴリズム問題では、プログラムが擬似言語で表記されます。この擬似言語は、基本情報技術者試験独自のものなので、試験問題に仕様書が添付されています。

ただし、ただでさえ時間が足りない午後試験の最中に、この仕様書を見ているようでは、まったく時間が足りなくなってしまいます。

擬似言語の読み方は、事前に確実にマスターしておく必要があります。

アルゴリズム問題 苦手克服への地道なステップ その 2

擬似言語の読み方は、事前に確実にマスターする

以下に擬似言語の仕様書を示します。たかだか 1 ページ半のものなので、当然、この仕様書だけでは不十分です。試験問題のプログラムには、仕様書に示されていない表現が使われる場合もあります

そのときには、問題文に説明があるのですが、「説明しなくてもわかるよね」というノリで使われる表現もあります。

たとえば、「整数型」「論理型」「 break 」「 return 」などです。このような表現は、過去問題を練習して覚えるしかありません。

共通に使用される擬似言語の記述形式

擬似言語を使用した問題では,各問題文中に注記がない限り,次の記述形式が適用されているものとする。

〔宣言,注釈〕

手続,変数などの名前,型などを宣言する。
/* 文 */
文に注釈を記述する。

〔処理〕

・変数 <- 式
変数に式の値を代入する。
・手続(引数, ・・・)
手続を呼び出し,引数を受け渡す。
▲ 条件式
|  処理
▼

単岐選択処理を示す。

条件式が真のときは処理を実行する。

▲ 条件式
|  処理 1
+---
|  処理 2
▼

双岐選択処理を示す。

条件式が真のときは処理 1 を実行し,偽のときは処理 2 を実行する。

■ 条件式
|  処理
■

前判定繰返し処理を示す。

条件式が真の間,処理を繰り返し実行する。

■
|  処理
■ 条件式

後判定繰返し処理を示す。

処理を実行し,条件式が真の間,処理を繰り返し実行する。

■ 変数:初期値, 条件式, 増分
|  処理
■ 条件式

繰返し処理を示す。

開始時点で変数に初期値(式で与えられる) が格納され,条件式が真の間,処理を繰り返す。また,繰り返すごとに,変数に増分(式で与えられる)を加える。

〔演算子と優先順位〕

演算の種類 演算子 優先順位
单項演算  +,-, not 

|
|
|
|
|
|
|
|
|

乗除演算  ×,+,% 
加減演算  +,- 
関係演算  >, <,≧,≦,=,≠ 
論理積  and 
論理和  or 

注記 整数同士の除算では、整数の商を結果として返す。 %  演算子は、剰余算を表す。

〔論理型の定数]

 true, false 

プログラミングに慣れていない人には、擬似言語の仕様書を見ただけでは、意味がわからない部分があると思います。

ポイントとなる部分を説明しましょう。

 

最初の方にある「手続」とは、一般的に「関数」と呼ばれるものです。

プログラミング言語の種類によっては、関数に相当するものをプロシージャ( procedure )と呼ぶ場合があるので、それを直訳して「手続」と呼んでいるのです。

ただし、試験問題では、「関数」や「副プログラム」と呼ぶ場合もあります。

擬似言語は、C 言語によく似ています。

分岐(選択)と繰り返しの表現は、C 言語の構文と対応させて覚えると理解しやすいでしょう。以下に示します。左側が擬似言語で、右側が C 言語です。

【単岐選択処理】


▲ 条件式
|  処理
▼


if 条件式 {
    処理;
}

【双岐選択処理】


▲ 条件式
|  処理 1
+---
|  処理 2
▼


if 条件式 {
    処理 1;
} else {
    処理 2;
}

【前判定繰り返し処理】


■ 条件式
|  処理
■


while (条件式) {
    処理;
}

【後判定繰り返し処理】


■
|  処理
■ 条件式


do {
    処理;
} while (条件式);

【ループカウンタを使った繰り返し処理】


■ 変数:初期値, 条件式, 増分
|  処理
■ 条件式


for ( 変数 = 初期値; 条件式; 増分 ) {
    処理;
}

C 言語では、繰り返しを意味する構文が while(~である限り)であることに注目してください。

試験の問題文では、繰り返しの条件を「~である限り繰り返す」と示す場合と、「~になるまで繰り返す」と示す場合があります。

C 言語は while なので、問題文が「~になるまで繰り返す」であっても、プログラムは「~である限り繰り返す」に置き換えられます。これは、擬似言語でも同じです。

たとえば、問題文に「 A と B が等しくなるまで繰り返す」と示されていても、プログラムでは「 ■ A ≠ B 」つまり「A と B が等しくない限り繰り返す」という条件になります。

 

ループカウンタを使った繰り返し処理は、C 言語では、for という表現になります。ここでも、条件式は、「~である限り繰り返す」です。

 

演算子の中では、% が 剰余算(整数の割り算で余りを求める)を意味していることに注意してください。試験の他の問題では、 Mod という言葉で 剰余算 を表すことが多いのですが、擬似言語では % です。

これは、C 言語でも、% が 剰余算 だからでしょう。

 

演算子の優先順位を丸暗記する必要はありません。優先順位がわかりにくい演算式は、優先する部分をカッコで囲んで示すからです。

ただし、 IT エンジニアの常識として、and の方が or より優先順位が高いことを、覚えておいてください

and を論理積(論理的な掛け算)と呼び、or を論理和(論理的な足し算)と呼ぶので、「論理演算でも掛け算の方が足し算より優先順位が高い」と覚えるとよいでしょう。

 

演算子の「注記」の部分にある「整数同士の除算では、整数の商を結果として返す」とは、「整数同士で割り算をすると、結果の小数点以下が切り捨てられる」という意味です。

アルゴリズム問題の克服への地道なステップ(その 3 )

いよいよ最後のステップです。この後は、ひたすら過去問題を解いてください。

その際に重要なのは、制限時間を設けることです。

令和元年以前のアルゴリズム問題の配点は 20 点 であり、試験時間が 2 時間 30 分( 150 分)なので、令和元年以前の過去問を練習するときは 150 分 ×( 20 点 / 100 点)= 30 分 が制限時間の目安です。

令和 2 年以降は配点が変更され 150 分 × ( 25 点 / 100 点) = 37.5 分 になります

 

ダラダラと時間をかけて解く癖を付けてしまうと、実際の試験のときに時間が足りなくなってしまいます。

たとえ、できないところがあっても、多少あてずっぽうがあっても、初めて見る問題を練習するときは、35 分で解いてください。最初は、0 点かもしれません。それでも、35 分で解いてください。

 

そして、問題を解き終わって、答え合わせをして、間違った部分を検証する作業は、どんなに時間をかけても構いません。自分で「あっそうか!」と気付くまで、しつこく検証してください。

このとき、あまり完璧を求めないでください。

60 % 以上できれば合格なのですから、少しぐらいわからない部分があっても気にしないでください。

出題者だって、満点が続出したら困るので、少しぐらい難しい設問を入れています。それができなくても、気にしないでください。

 

わからないからといって、市販の問題集の解説を見る人もいますが、その際にも注意が必要です。

解説が自分に合ってないと、ますますわからなくなるからです。難しい設問も、スラスラ解説しているので、それがわからない自分に焦ることもあります。

市販の問題集の解説は、あくまでも参考だと割り切ってください。

午後試験のアルゴリズム問題を克服するには、自分流の解法を見出すしかありません。

アルゴリズム問題 苦手克服への地道なステップ その 3

過去問を解いて、自分流の解法を見出す

自分専用に解法ノートを作って、解説者になったつもりで、自分で自分に解説してみるとよいでしょう。

自分流の解法の例は、次回の記事で紹介します。私の解法ですので、あくまでも参考にしてください。

矢沢久雄流 アルゴリズム問題の解き方(2)

私という同じ講師が対策講座を行っても、試験の合格率は、企業によって様々です。

全国平均以下の場合もあれば、全国平均を大きく上回る場合もあります。
 

そんな中、ほぼ 100% の合格率となった企業が 2 社ありました。

別の 1 社は、社長の試みで一度だけ「合格者にボーナス 20 万円」のご褒美を出しました。

そして、もう 1 社は、「本試験の前に 10 回の模擬試験」を行いました。2 社とも、ほぼ 100% の受験者が合格しました。

 

つまり、その気になって、問題の数をこなせば、必ず合格できるということです。アルゴリズム問題も、がんばれば、きっと克服できるはずです。

それでは、またお会いしましょう!

 

info編集部よりお知らせ
アルゴリズム問題のトレースのコツなど紹介する連載が始まりました!

 

label 関連タグ
科目A試験は、
免除できます。
独習ゼミで科目A試験を1年間免除して、科目B試験だけに集中しましょう。
免除試験を受けた 74.9% の方が、
科目A免除資格を得ています。
科目A免除試験 最大 2 回の
受験チャンス !
info_outline
科目A免除試験 最大 2 回の
受験チャンス !
詳しく見てみるplay_circle_filled
label これまでの『午後問題の歩き方』の連載一覧 label 著者