本：問題解決のPythonプログラミング

「問題解決のPythonプログラミング ―数学パズルで鍛えるアルゴリズム的思考」を読んだのでまとめてみました！
著者：Srini Devadas
翻訳：黒川 利明
出版社：オライリージャパン
発売日：2018/9/22

まとめ

有名なアルゴリズムの本はC++で書かれているものが多く、pythonで学べる本を探していたところ当書を見つけました。
原書がMITから出されており恐れていましたが、atcoder灰色の僕でも頑張れば読めるレベルでした。
ただ、他のレビューにもある通り読みづらさは少しあります。
(訳がわかりにくい？)

全21章から構成され、それぞれの章で一つの「問題」が設定されています。
「問題」に関しては無機質なものでなく、面白い設定がされています。飽きずに最後まで取り組めます。
流れは最初に思いつきそうなアルゴリズムを示してから綺麗なアルゴリズムを紹介してくれます。
その後に練習問題が3題ほど出題されます。

サンプルコードはMITサイトのCode for Selected Puzzle Solutionsから落としてこれます。(python3対応)
が、残念なことに練習問題の解答がついていませんでした。
わからない問題の答えがないのでかなりストレスになります。

前半は基本的な文法がわかれば比較的容易に解けると思います。
後半は再帰を使わないと解けないので難しく感じました。
ただ、問題の設定が面白いので最後まで読み切れると思います（問題が全部解けるかは別です）。興味がわけばぜひ！

以下当書で学べるアルゴリズムを自分なりにまとめます。

学べたこと

1.二分探索
2.bit全探索
3.再帰
4.マージソート
5.クイックソート
6.深さ優先探索
7.幅優先探索

1-二分探索

ソート済みの配列から任意の要素を探索する一番有名？なアルゴリズム。
単純なループ処理で見つけりとO(N)かかるところをO(logN)で求めることができる！
応用が効くのでアルゴリズム入門にGOOD!

方針

1.配列の中間の要素と調べたい要素の大小を調べる
2-a.調べたい要素の方が大きければ探索範囲を(中間~最後)の範囲に絞る
2-b.調べたい要素の方が小さければ探索範囲を(最初~中間) の範囲に絞る
＞1,2の繰り返し

実装

array = [1,2,3,4,5,6,7,8,9]
target = 9

top = len(array) - 1
bottom = 0

while top >= bottom:
    middle = (top + bottom) // 2
    if array[middle] < target:
        bottom = middle + 1
    elif array[middle] > target:
        top = middle - 1
    elif array[middle] == target:
        print(f'{middle + 1}番目に発見！')
        break
else:
    print('存在しない!')

2-bit全探索

「9章アメリカズ・ゴット・タレント」で出てくる。
名前の通り全探索です。組み合わせの全列挙とかで使える。
計算量が指数的O(2**N)に増えるので N=20~30ぐらいが限界だが、bitの勉強にもなるのでコスパよし！

問題

atcoderからお借りします
https://atcoder.jp/contests/abc045/tasks/arc061_a
こちらを参考にしました
https://qiita.com/hareku/items/3d08511eab56a481c7db

方針

1. 入力された数字(s)とsの間(len(s)-1)と考える
2. sの間をbit探索して1なら'+', 0だと何も入れない。
3. 作った式を都度計算して結果を足していく
4. 上記全パターンを探索する

実装

s = '125'

answer = 0
# bitに変換して探索
for i in range(2 ** (len(s)-1)):
    formula = [''] * len(s)
    for j in range(len(s)):
        if i >> j & 1:
            formula[len(s)-j-2] = '+'
        else:
            formula[len(s)-j-2] = ''

    calc = ''
    for i, j in zip(s, formula):
        calc += i + j
    answer += eval(calc)

print(answer)

3-再帰

関数の中で自分を呼び出す処理をする。
当書の目玉！
後半は再帰を使わないとほとんど解けないが、理解が難しく苦戦したポイント。
単純な再帰だと計算量が多くなりすぎるのでメモ化と併用されることが多い。

問題

フィボナッチ数列を再帰で求める
*フィボナッチ数列:数列のi番目がi-1番目とi-2番目の和になっている数列
0, 1, 1, 2, 3, 5, 8, 13, 21

方針

1. 基底部分を決める。今回は配列の0番目と1番目を基底部にする。
2. i-1とi-2の和をひたすら再帰
3. i番目をメモしておくと効率が良い

実装

idx = 30 #30番目のフィボナッチ数を求める

def recursiveFibonacci(idx, memo = {}):
    if idx <= 0: return 0
    if idx == 1: return 1

    if not idx in memo:
        memo[idx] = recursiveFibonacci(idx-1, memo) + recursiveFibonacci(idx-2, memo)
    return memo[idx]

print(recursiveFibonacci(idx-1))

4-マージソート

「11章 中庭にタイルを敷く」で出てくる。
ソートアルゴリズムのうちの一つ
最小要素まで2分割してソートしたものを結合していく。
一般に計算量O(N*logN)と高速だが、メモリを大量に使うのが欠点

方針

再帰で実装する。
1. 基底部を書く。今回は要素が二つ以下の時に二要素をソートする
2. 配列を二分割する
3. 二分割した配列をソートしながらマージ
4. 2,3を再帰

実装

from random import sample

def mergeLst(left, right):
    merged_lst = []
    l = 0
    r = 0
    while l < len(left) and r < len(right):
        if left[l] <= right[r]:
            merged_lst.append(left[l])
            l += 1
        else:
            merged_lst.append(right[r])
            r += 1
    if l < len(left):
        merged_lst += left[l:]
    elif r < len(right):
        merged_lst += right[r:]

    return merged_lst

def mergeSort(lst):
    if len(lst) <= 1: return lst
    if len(lst) == 2:
        if lst[0] >= lst[1]:
            lst = [lst[1], lst[0]]
        return lst

    middle = len(lst) //2
    left = mergeSort(lst[:middle])
    right = mergeSort(lst[middle:])
    return mergeLst(left, right)

# ランダムな配列を作成
lst = sample(range(100), k=15)
print(mergeSort(lst))

5-クイックソート

「13章 整理が苦手な修理屋」で出てくる。
pivotを決めてそれより大きい要素と小さい要素に分けていく。
参考：https://tech-shelf.hatenablog.com/entry/algorithm/quicksort

一般に計算量O(N*logN)と高速。
マージソートと違い、元のリストだけを並び替えていくのでメモリに優しい。
関係ないがpythonの組込sort関数はティムソートと呼ばれるアルゴリズムらしい。

方針

再帰で実装する。
元のリストを並び替えていくことに注意！
1. 基底部を書く。今回は要素数が1の時に再帰処理を終了
2. pivotを決める
3. pivotより大きい要素と小さい要素に分ける処理を作成
4. それぞれの要素に関して再帰

実装

from random import sample

def divided(lst, start, end):
    pivot = lst[end]
    # startを3個目のループで参照したいので最初に-1をする
    start -= 1
    done = False

    while not done:
        while not done:
            start += 1
            if start >= end:
                done = True
                break

            if lst[start] > pivot:
                lst[end] = lst[start]
                break
        while not done:
            end -= 1
            if start >= end:
                done = True
                break

            if lst[end] < pivot:
                lst[start] = lst[end]
                break

    lst[end] = pivot
    return end

def quickSort(lst, start, end):
    if start >= end:
        return lst

    pivot_idx = divided(lst, start, end)
    quickSort(lst, start, pivot_idx - 1)
    quickSort(lst, pivot_idx + 1, end)
    return lst

# ランダムな配列を作成
lst = sample(range(100), 15)
print(quickSort(lst, 0, len(lst)-1))

6-深さ優先探索

「19章 忘れられない週末」で出てくる。
グラフの探索に使うアルゴリズム。
1. ノードがなくなるまで探索
2. 分岐に戻る
1, 2の繰り返し。
実装は再帰で行う他にstackで管理するやり方もある。

問題

グラフが2部グラフかチェックするコードを書く
2部グラフ：グラフを2分割したとき集合の中で頂点が隣接しないグラフ
参考：https://ja.wikipedia.org/wiki/2部グラフ

グラフは無向グラフで辞書型で与えられるとする。
keyにノードの名前。
valueに隣接関係を示す。
{'A': ['B', 'D'],
'B': ['C', 'A'],
'C': ['D', 'B'],
'D': ['A', 'C']}

方針

グラフを色分けした時に2色(red, blue)だけで表現することができるか確かめる
２色で表現できる=>2部グラフ
表現できない=>2部グラフでない

再帰でノードを探索していく

1. 基底部を考える。
   1. 色を塗ってないノードに達した時、色を塗る
   2. 色が既に塗ってあるノードに達した時
      1. 塗る予定の色が同じ色ならスキップ
      2. 塗る予定の色と違う色なら2部グラフでない
2. ルートのノードを決めて探索開始
3. すべての探索が問題なく終わると2部グラフであることがわかる

実装

graph = {'A': ['B', 'D'],
         'B': ['C', 'A'],
         'C': ['D', 'B'],
         'D': ['A', 'C']}

def changeColor(color):
    if color == 'red':
        return 'blue'
    else:
        return 'red'

def dfs(graph, start, color, memo = {}):
    if not start in memo:
        memo[start] = color
        color = changeColor(color)
    else:
        if memo[start] == color:
            color = changeColor(color)
            return True
        else:
            return False

    for node in graph[start]:
        result = dfs(graph, node, color, memo)
        if not result:
            return '二部グラフじゃない！'

    return '二部グラフ！！！'

root = 'A'
color = 'red'
print(dfs(graph, root, color))

7-幅優先探索

「20章 6次の隔たり」で出てくる。
深さ優先探索と似ている。
最短経路を見つける時には幅優先探索を使った方が良い。
1. 一番近いノードをすべて探索する
2. 二番目に近いノードをすべて探索する
...
n. n番目に近いノードをすべて探索する

メモ：再帰で実装するのは難しそう？

問題

グラフのルートから各ノードへアクセスするためのステップ数を求める。

グラフは無向グラフで辞書型で与えられるとする。
keyにノードの名前。
valueに隣接関係を示す。
{'A': ['B', 'D'],
'B': ['C', 'A'],
'C': ['D', 'B'],
'D': ['A', 'C']}

方針

探索したノード、探索するノードをそれぞれvisited, frontearとして管理
1. ルートノードから探索を始める。
1-a. 初めて探索するノードならメモに保存。次に探索するノードに隣接ノードを追加する。
1-b. 探索済ノードなら何もしない
2. frontearが存在しなくなるまで探索する。

実装

graph = {'A': ['B', 'D'],
         'B': ['C', 'A'],
         'C': ['D', 'B'],
         'D': ['A', 'C']}

def bfs(graph, start, memo = {}):
    visited = set()
    frontear = set()
    step = 0

    frontear.add(start)

    while len(frontear) > 0:
        new_frontear = set()
        for node in frontear:
            if not node in visited:
                visited.add(node)
                if step in memo:
                    memo[step] += [node]
                else:
                    memo[step] = [node]
                for child_node in graph[node]:
                    new_frontear.add(child_node)

        frontear = new_frontear
        step += 1
    return memo

root = 'A'
print(bfs(graph, root))

　まとめ2

とりあえずいろいろまとめましたが、効率悪いところが多いかと思います。
今後も勉強を続けて加筆修正していきたい。。。