基本情報技術者試験とは
基本情報技術者試験（きほんじょうほうぎじゅつしゃしけん、Fundamental Information Technology Engineer Examination、略号FE）は、情報処理の促進に関する法律第29条第1項に基づき経済産業大臣が行う国家試験である情報処理技術者試験の一区分。対象者像は「高度 IT 人材となるために必要な基本的知識・技能をもち，実践的な活用能力を身に付けた者」。
情報処理技術者試験制度のスキルレベル2（スキルレベルは1から4が設定されている。）に相当する。2000年度（平成12年度）までの名称が第二種情報処理技術者試験であったことから二種という略称を用いる人もいる。 wiki
大学時代にお世話になった、ジャックダニエル大好きなじいさんに「基本情報はとったほうがええぞ～」といわれたので、アルゴリズムだけでも勉強しようかと。基本情報の勉強している方一緒に頑張りましょう^^
ちなみに、基本情報の試験は午前と午後があって、午後問題は以下の５つからの選択なので、アルゴリズムも下の言語のどれかで勉強すれば一石二鳥な感じですが、「それだとやる気なくなるよぉ」、と私の心がいっているので、使いたい言語使ってアルゴリズム勉強しようと思います。（モチベーション大事）
「 C 言語」「 Java 」「 Python 」「アセンブラ ( CASLⅡ ) 」「表計算」
計算量
アルゴリズムといえば計算量ではないでしょうか。めちゃくちゃ詳しく書かれている記事を見つけました。
上記の表もリンクのQiitaからとってきたものです。一秒間で処理できるforループの回数らしいです。
計算量も意識しながら勉強を進めていきたいですね。
線形探索
計算量 $O(n)$
\begin{align}
target &= 7 \\
list &= [1,9,8,4,5,3,10,7,6,2]
\end{align}
$list$ の中から $target$ がどこにあるのかを探します。線形探索は先頭から愚直に探し当てに行くアルゴリズムです。長さが10なら最悪10回ループを回さないと探索が終わらないので計算量が、__$O(n)$__なんですね。計算量は最悪の場合をとることが多いですけど、クイックソートとかは違ったはずですね。今回は関係ないのでいったん忘れましょう。
function linear_search( target, list )
for n in 1:length(list)
if target == list[n]
return n
end
end
end
二分探索
計算量 $O(\log{2} n)$_
私が二分探索で大事だと考えているポイントは次の3点です。一つ目は前提条件です。二つ目は、実装時に勘違いしそうなポイントです。三つは終了条件です。この3点を理解できるように実装を追うといいと思います。
- 配列は並び替えてある
- 探索範囲を変更するとき使っていた真ん中の値は捨てる
- 終了条件 → 一番大きい値 < 一番小さい値
では実装について簡単にまとめます。
- 昇順 or 降順で配列を並び替える。今回は昇順で並べたとして考える。
- 真ん中の値、一番大きい値、一番小さい値をそれぞれ、$M$ $H$ $L$ と置く。
- 真ん中の値 $M$ と $target$ の値を比較する
- $target$ = $M$ → 探索成功
- $target$ > $M$ → $target$ は配列の後半にある可能性がある。真ん中の値を一つ右にずらして、その位置を新しい $L$ にする。その後2. に戻る
- $target$ < $M$ → $target$ は配列の前半にある可能性がある。真ん中の値を一つ左にずらして、その位置を新しい $H$ にする。その後2. に戻る
- 一番大きい数値 $H$ と一番小さい数字 $L$ が $H \leq L$ になったときに探索失敗
字だけでは難しいと思うので、簡単にですが二分探索の図をつくってみました。今回 $target=8$ とします。わかりやすいようにマスを赤くしておきました。この図と上記の手順を見比べて追ってみてください。
注意ポイントで紹介した、使用した真ん中の値を捨てるということを見てみましょう。2回目のループのとき5は灰色になっていますね。私が初めて二分探索を見たとき、$L$ の位置は5の位置だと勘違いしてました。。。
計算量についても少しだけ考えてみましょう。長さ $N$ の配列を考えます。ループ2回目の時点で配列の長さは $\frac{N}{2}$ になります。ループ3回目では、$\frac{N}{4}$,...。つまり $L$ 回目のループのとき配列の長さは $\frac{N}{2^{L-1}}$ となります。ここで、$L$ 回目に配列の長さが1になるとします。これを用いると
\begin{align}
1 &= \frac{N}{2^{L}} \\
2^{L} &= N \\
\end{align}
両辺に底が2の対数をとると
\begin{align}
L &= \log_{2} N \\
\end{align}
となります。これはループ回数 $L$ がおそよ $\log_{2} n$ に比例することを表しています。
対数なんか知らねぇぜっていう方のために、単純にループの長さと配列の長さをグラフにプロットしてみたものを用意したのでこちらを見てください。
縦軸はループの回数です。縦の目盛りは無視して上からループの回数が2回目, 3回目, ...となっています。
ちなみに $log_{2} N$ のグラフはこんな感じです。
わぁ！そっくりですね！
using Plots
# ループ数をL, 配列の長さをNとします
x( N, L ) = N / 2^(L-1)
N, L = 100, 10:-1:2
# 棒グラフ
bar( x.( N, L ), orientation=:horizontal, label=false )
# 対数のグラフ
plot( x->log(2, x), label="log₂N" )
function binary_tree_search( target, list )
# listを並び替える
X = sort(list)
L, H = 1, length(X)
# 終了条件
while L ≤ H
M = ( L + H ) ÷ 2
if target == X[M]
return M
end
if target < X[M]
H = M - 1
end
if target > X[M]
L = M + 1
end
end
# L ≥ H の場合
println("探索失敗")
end
Juliaの「÷」は商を表します。Pythonでいう「//」です。
続きはこちら
bit全探索【おまけ】
今回の記事はシリーズ化したいなと思っているんですけど、おまけとして下の記事の内容も勉強しようと思います。
計算量 $O(2^{N-1})$ ?
初回はbit全探索という手法を勉強します。適用できる問題としては、各要素について、「裏/表」「On/Off」のように2通りの選び方がある要素が複数あったときの組み合わせを考えるときに役に立ちます。
例えば、３枚のイカサマコインがあるとします。このとき3枚のコインを投げたときの出目の組み合わせは $2^{3}$ です。このとき表の枚数が2枚のときのは何通りあるでしょうか？のような問題です。愚直に書けばfor文使って以下の通りになると思います。
for i in 0:1
for j in 0:1
for k in 0:1
println("$i$j$k")
end
end
end
#=
出力
000
001
010
011
100
101
110
111
=#
あとは1を数えるなどすればいいというわけですね。ですがこれだとコインの枚数が増えると対応できません。
そんな問題を解決するためのbit全探索です。なにはともあれ、リンク先のGIFが本当にわかりやすくてそれを見れば万事解決です。まずはそこのGIFと説明を読みましょう。
私からはリンク先の例題として出されていた問題をJuliaで書いたので、コードの説明をして終わりとしたいと思います。
$N$ 個の硬貨があります。番号 $i$ の硬貨は $A_{i}$ 円です。硬貨の選び方は $2^{N}$ 通りありますが、その中で合計価格が丁度 $X$ 円となる選び方は存在するでしょうか。
制約：$1≤N≤20$,$1≤X$,$Ai≤10^{8}$
function bit_search( target, list )
N = length(list)
for x in 0:2^N - 1
bin = string(x, base=2)
tmp = length(bin) < N ? "0"^(N-length(bin)) * bin : bin
A = parse.( Int, split( tmp, "" ) )
if A'list == target
@show A
end
end
end
まず2進数に直す方法は,string(x, base=2) でできます。引数のbaseでn進数を表せるみたいです。ちなみに引数base はキーワード引数なのでbaseを省略することはできません。
変換した2進数は文字列です。後々のために2進数を数値のベクトルに変換しておきたいです。ベクトルに変換するには、split( 文字列, "" ) で文字列一つ一つを要素とするベクトルを得ることができます。あとは、parseで数値に変換しているだけです。
Juliaを知らない人は、parseの後のドットが気になるかもしれません。これはドット演算子といってJuliaではいろいろなところで登場します。関数の後ろにつけると引数でベクトルを受け取れない関数も、ベクトルを受け取ることができるようになります。そして個々の要素に対して関数を適用した値を返します。
例を挙げたいと思います。$x$ の要素をすべて $int$ にしたいとき、Pythonだとこう書くけどJuliaはこう。
x = [ "1", "2", "3" ]
x_ = [ int(i) for i in x ]
x = [ "1", "2", "3" ]
x_ = parse.( Int, x )
ドットの意味が少しは伝わったでしょうか？
今後勉強に使えそうなページ