はじめに
アルゴリズムを学ぶのに有名な本として, 「問題解決力を鍛える！アルゴリズムとデータ構造」 が挙げられます.
こちらの内容紹介では, 次のことが書かれています.
競技プログラミング経験が豊富な著者が、「アルゴリズムを自分の道具としたい」という読者に向けて執筆。入門書を標榜しながら、AtCoderの例題、C++のコードが充実。入門書であり実践書でもある、生涯役立つテキストを目指した。
本書はアルゴリズム入門者向けとして書かれていますが, ソースコードは基本的にC++によって記述されています.
そこで, 本記事では, アルゴリズム入門者である筆者がこの本をPythonで記述しながら学んでいこうというものです.
そのため, 基本的にPython中心となります. 問題文や解説は本書を参考にして, Pythonで記述する場合の補足として本記事を閲覧いただければと思います.
全探索
以下では, 全探索の章のコードを記述していきます.
code3.1 線形探索法
入力
5 7
4 3 12 7 11
出力
Yes
ソースコード
# 実行部分
if __name__ == '__main__':
# 入力
N, v = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
# 線形探索
exist = False # 初期値はFalseに設定
for i in range(N):
if (a[i] == v):
exist = True # 見つかったらフラグを立てる
# 出力
if exist: print('Yes')
else: print('No')
code3.2 特定の要素の存在する「添字」も取得する
入力
5 7
4 3 12 7 11
code3.1と同様です.
出力
3
ソースコード
# 実行部分
if __name__ == '__main__':
# 入力
N, v = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
# 線形探索
fount_id = -1 # 初期値は -1 などありえない値に
for i in range(N):
if (a[i] == v):
found_id = i # 見つかったら添字を記録
break # ループを抜ける
# 出力 (-1 のときは見つからなかったことを表す)
print(found_id)
code3.3 最小値を求める
入力
5
4 3 12 7 11
code3.1と似ていますが, 1行目の v (ここでは 7)がなくなり N (ここでは 5)だけとなっています.
出力
3
ソースコード
# 実行部分
if __name__ == '__main__':
INF = 20000000 # 十分大きな値に
# 入力
N = int(input())
a = list(map(int, input().split(' ')))
# 線形探索
min_value = INF
for i in range(N):
if (a[i] < min_value):
min_value = a[i]
# 出力
print(min_value)
code3.4 ペア和の最小値を求める（K以上の範囲）
入力
3 10
8 5 4
4 1 9
出力
12
ソースコード
# 実行部分
if __name__ == '__main__':
INF = 20000000 # 十分大きな値に
# 入力
N, K = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
b = list(map(int, input().split(' ')))
# 線形探索
min_value = INF
for i in range(N):
for j in range(N):
# 和が K 未満の場合は捨てる
if (a[i] + b[j] < K):
continue
# 最小値を更新
if (a[i] + b[j] < min_value):
min_value = a[i] + b[j]
# 出力
print(min_value)
code3.5 整数 bit の表す部分集合に i 番目の要素が含まれるかどうかを判定する
code3.5 は code3.6 の内容の一部であるため, 説明は割愛します.
code3.6 部分和問題に対するビットを用いる全探索解法
入力
5 10
1 2 4 5 11
出力
Yes
ソースコード
# 実行部分
if __name__ == '__main__':
# 入力
N, W = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
# bit は 2^N 通りの部分集合全体を動きます
exist = False
for bit in range(1 << N):
int_sum = 0 # 部分集合に含まれる要素の和
for i in range(N):
# i 番目の要素 a[i] が部分集合に含まれているかどうか
if (bit & (1 << i)):
int_sum += a[i]
# sum が W に一致するかどうか
if (int_sum == W): exist = True
# 出力
if exist: print('Yes')
else: print('No')
本書では, 部分集合に含まれる要素の和としてint sum = 0;と置いていますが, Pythonでは予約語にsumが含まれるため, 上記のコードではint_sum = 0と置いています.
1 << N は 1のNビット左シフト を表します. ビット演算に関する演算子（JavaDrive）によると, 以下の通りらしいです.
左シフトは左辺の値を右辺の値だけ左へシフトします。
x << n(中略)
左シフトを 1 ビット行うと値は 2 倍になり、 2 ビット行うと 4 倍となります。
これより, 1 << N は $2^N$ を表していると分かります.
以上が終わった後は
ここで, AtCoderで解くべき全探索の問題が収録されています.
全て解きましょう.