スズメの本棚

自分の知識の定着のために本や実装したことをまとめていきます．

トップ > アルゴリズム関係

pythonでマージソートを実装してみた

python アルゴリズム関係 プログラミング

今回はソートアルゴリズムの中でも今まで学んできたものよりも高速なアルゴリズムであるマージソートに関してpythonで実装していきたいと思います．
マージソートは基本的なソートアルゴリズムと比べると少し実装しづらい部分はありますが，全体の流れを掴むことと再帰関数をしっかりと使いこなすことができればそれほど苦戦せずに実装できると思います．

目次

マージソートとは

マージソートは配列全体に対して次の処理を行うようなソートを指します．

  1. 指定されたn個の要素を含む部分配列をそれぞれn/2個の要素を含む2つの部分配列に分割する.

    1.1 部分配列は一つの要素になるまで分割を続ける

  2. 2つの部分配列をそれぞれ順番通りに並ぶようマージ(合併)する

    2.1 部分配列がなくなるまで繰り返す

これらの流れを下図で確認してください.

f:id:tech_shelf:20200603124209p:plain

図で流れを抑えると処理の行い方がより明確に伝わったと思います．
マージソートの土台は配列全体の1/2の大きさの部分配列を作りだすことと部分配列を統合していくことで作ることができます．

また，この分割フェーズに関しては1/2にしていくことを繰り返す，つまり，log2n回の分割を行います．
一方でこの統合フェーズに関してはソート済みの配列を統合していきます．
つまり，必ずどちらかの配列の先頭要素のうち一つが統合後の配列の先頭要素になります．同様に統合後の二番目の配列要素に関してもどちらかの部分配列の要素にあり，この処理を繰り返していくことで統合することができます．よって，各階層でかかる計算量は常にO(n)となります．
これらのことよりマージソートはこれまで書いてきたソートアルゴリズムよりも早いO(nlogn)のアルゴリズムとなります．

マージソートの実装例

マージソートに関しての問題はALDS1_5_B:Merge Sortです．
マージソートの擬似コードなどが載っているので流れを確認したい方は見に行ってみてください.
では，早速実装していきたいと思います．

# mergesort
import random

#統合部
def merge(A, left, mid, right):
    L = A[left:mid]
    R = A[mid:right]
    for i in range(left,right):
        if len(L) == 0:
            A[i] = R.pop(0)
        elif len(R) == 0:
            A[i] = L.pop(0)
        elif L[0] <= R[0]:
            A[i] = L.pop(0)
        else:
            A[i] = R.pop(0)

#分割部
def mergesort(A, left, right):
    if left + 1 < right:
        mid = (left + right)//2
        mergesort(A, left, mid)
        mergesort(A, mid, right)
        merge(A, left, mid, right)
        print(A)
            
    
A = [ i+1 for i in range(10)]
random.shuffle(A)
print(A)
mergesort(A,0,len(A))
print(A)

出力例

[8, 9, 3, 7, 10, 4, 6, 5, 1, 2]
[8, 9, 3, 7, 10, 4, 6, 5, 1, 2]
[8, 9, 3, 7, 10, 4, 6, 5, 1, 2]
[8, 9, 3, 7, 10, 4, 6, 5, 1, 2]
[3, 7, 8, 9, 10, 4, 6, 5, 1, 2]
[3, 7, 8, 9, 10, 4, 6, 5, 1, 2]
[3, 7, 8, 9, 10, 4, 6, 5, 1, 2]
[3, 7, 8, 9, 10, 4, 6, 1, 2, 5]
[3, 7, 8, 9, 10, 1, 2, 4, 5, 6]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

コードの解説

mergesortの関数の部分では部分配列の位置を表すleftとright，また，その中央部分(分割部分)を表すmidをright - leftが2になるまで再帰的に呼び出しています．つまり，leftとrightに含まれる要素がそれぞれ一つになるまで呼び出しを続けています．
その後，再帰関数の呼び出しの逆順に統合部分の関数に値が投げられます．
統合部ではleftの位置にある配列Aの要素群とrightの位置にある配列Aの要素群の値の大小を群の先頭から順に比較しています．
一連の処理を終えると出力例の最終行のようにソートされた値が並ぶと思います．

再帰関数で作るフラクタル図形 ~コッホ曲線~

python アルゴリズム関係 プログラミング

今回はフラクタル図形の各頂点の座標を求める問題に挑戦していきたいと思います．再帰関数の理解を深めるのにちょうどいい問題でしたのでぜひ挑戦してみてください．

目次

フラクタル図形とは

図形の部分と全体が自己相似（再帰）によってできているものをフラクタルと呼ぶそうです(wiki参照).
シェルピンスキーのギャスケット(初めて名前知りました…)がみなさん見たことあるフラクタル図形の一つだと思います．

f:id:tech_shelf:20200530173537p:plain

フラクタル図形は自然界にもたくさんある形です．こういった幾何学模様は不思議な魅力があって綺麗に見えますよね.

コッホ曲線

コッホ曲線は先ほど説明したフラクタル図形の一つです.
線分を3等分し、分割した2点を頂点とする正三角形の作図するということを無限に繰り返すことによって得られる図形を指しています.
画像参考サイト

f:id:tech_shelf:20200530174335p:plain

正三角形からこのコッホ曲線を描くと雪片のようになることでも有名です.

問題

今回扱う問題はALDS1_5_C: Koch Curveになります．
問題の内容としては入力nを受け,深さnの再帰呼び出しによって作成されるコッホ曲線の頂点の座標を出力するというものです.
作らなければならない動作としては

  • 与えられた線分(p1, p2)を三等分にする
  • 線分を三等分する2点(s, t)を頂点とする正三角形(s, t, u)を作成し，その座標を求める
  • 新しくできた全ての線分[(p1, s),(s, u), (u, t), (t, p2)]に対して上記の処理を再帰的に繰り返す．

コード&解説

n=1の時は直感的にuの座標がわかると思うのですが，nが増えていくに連れてわかりづらくなると思います． (自分はここで詰まりました…)
ここで，点uの座標を求めるのに使うのが回転行列です．

原点中心に θ 回転して点 (x, y) が (x ', y ') に写るとすると、図形的考察または三角関数の加法定理より、x', y ' は以下のように表されることが分かる。
x'= x cosθ - y sinθ
y'= x sinθ + y cosθ
wiki参照

また，図形的考察をしてくれているサイトもあるのでこちらも参考にしてみてください(参考サイト).

では，これらの知識を活用して上記であげた動作をするプログラムを実装していきましょう.

import math



def koch(n, p1, p2):
    if n == 0:
        return
    sx = 2p1[0]/3 + p2[0]/3
    sy = 2p1[1]/3 + p2[1]/3
    tx = p1[0]/3 + 2p2[0]/3
    ty = p1[1]/3 + 2p2[1]/3
    ux = (tx - sx)math.cos(math.radians(60))  - (ty - sy)math.sin(math.radians(60)) + sx
    uy = (tx - sx)math.sin(math.radians(60)) + (ty - sy)math.cos(math.radians(60)) + sy
    koch(n-1, p1, [sx, sy])
    print(sx, sy)
    koch(n-1, [sx, sy], [ux, uy])
    print(ux, uy)
    koch(n-1, [ux, uy], [tx, ty])
    print(tx, ty)
    koch(n-1, [tx, ty], p2)



n = int(input())
#問題文より，端点がp1 = (0,0), p2 =(100,0)と指定されている
p1 = [0, 0]
p2 = [100, 0]
print(p1[0], p1[1])
koch(n, p1, p2)
print(p2[0], p2[1])

上記のコードを実行することでp1から順に繋がった形で線分の座標を出力することができます．
点uの座標を求める方法を考えるのに苦労しましたがコードにすると意外と簡潔になりますね．
再帰関数に関してはこの前 やったばかりなのでお手の物でした！
Pythonを使ってこれらの図形を実際に描くこともできるそうなので今度試してみたいと思います．

組み合わせの列挙で学ぶ再帰関数

python アルゴリズム関係

こんにちは，今回もプログラミングコンテスト攻略のためのアルゴリズムとデータ構造をPythonを用いて実装しながら，解説していきたいと思います．

目次

再帰・分割統治法

問題を解く時に，部分的に問題を解く関数を用意することで与えられた元の問題を解いていくテクニックの一つが分割統治法です．
再帰関数とは，関数の中で自分自身をさらに呼び出すような関数のことを言います．

全探索の問題

今回は全探索の問題を再帰を使って解いていきたいと思います．実際により効率的に解こうと思えば，他の方法もありますが，再帰に慣れるため計算時間のかかる方法で解いています．
問題文は以下の通りです．
長さnの数列Aと整数mに対して，配列Aの要素の中のいくつかの要素を足し合わせてmが作る事ができるかどうかを判定するプログラムを作成してください．Aの各要素は一度だけ使う事ができます．

入力：一行目にn,二行目にAを表すn個の整数,
　　　三行目にq，四行目にq個の整数m_iが与えられます.
出力：整数mを作る事ができれば"yes",できなければ”no”
制約：n ≦ 20
　　　q ≦ 200
　　　1 ≦ Aの要素 ≦ 2000
　　　1 ≦ 整数m ≦ 2000

対応する問題はALDS1_5_A:Exhaustive Searchです．

組み合わせ列挙の関数

今回は全探索で判定を行うようなプログラムを作成していきたいと考えているので，その要素を使うか使わないかを示した全組み合わせが必要になります．
まずが，要素の組み合わせを列挙するような関数をまず作ってみたいと思います．

#n=5の時の組み合わせ
def comb(n):
    A = [0]*n
    select(0,A)
        
def select(i, A):
    if i == n:
        print(A)
        return
    select(i+1, A)
    A[i] = 1 #A[i]を選択
    select(i+1, A)
    A[i] =0  #A[i]を選択しない
n = 5
comb(n)

これで組み合わせの列挙はできるようになりました．
また，要素の組み合わせをpythonで作る場合より効率的な方法がいくつかあるので別記事で紹介しています．

tech-shelf.hatenablog.com

全探索を解くためのプログラム

次にこの組み合わせの中で整数mを作ることができるかどうかチェックするプログラムを作成します．
これは先ほどのプログラムのA[i]を選択するかしないかの部分を書き換えていくことで作成することができます．

n = 5
A = [1,5,7,10,21]
q = 4
m = [2,4,17,8]
def solve(i,m):
    if m == 0:
        return 1
    if i >= n:
        return 0
    rec =  solve(i+1,m) or solve(i+1, m - A[i])
    return rec
for i in m:
    if solve(0,i):
        print("yes")
    else:
        print("no")

このプログラムを一般化することでこの問題は解くことができます．

問題の解答

では，問題に答えられるように形を整えていきます．

n = int(input())
A = list(map(int,input().split()))
q = int(input())
m = list(map(int,input().split()))
sumA = sum(A)
def solve(i,m):
    if m == 0:
        return 1
    if i >= n:
        return 0
    rec =  solve(i+1,m) or solve(i+1, m - A[i])
    return rec
for i in m:
    if i >= sumA:
        print("no")
    else:
        if solve(0,i):
            print("yes")
        else:
            print("no")

※Pythonで問題を解く場合，整数mが配列Aの総和より大きい場合再帰関数に飛ばさないという分岐を作成する必要があります．

このアルゴリズムは選択するかしないかというのを各配列の要素に聞くような再帰関数を用いています．そのため，計算量はO（2n）となっており，nが小さい場合にしか活用することができません．
今後さらに章を進めていく中でもっと効率的なアルゴリズムがでてくるので，まずは全列挙が簡単に作れるようにマスターしましょう．
　　　　　　　　

実装して学ぶ基本探索アルゴリズム ~二分探索の応用~

python アルゴリズム関係

解答部分だけに興味がある方は二分探索による実装からみてください

目次

基本探索アルゴリズムの応用問題

今回扱うのはALDS1_4_D:Allocationです．
最大積載量が決まっているトラックに対して荷物をどう割り当てるかというのがこの問題の趣旨になります．
詳しく問題文を読み解いていきます．.
重さがそれぞれw_i(i = 0, 1,…, n-1)のn個の荷物をk台のトラックに積みます．トラックには荷物はいくらでも載せられますが，最大積載量Pを超えられません．この時の最大積載量Pの最小値を求めるという問題になります．
制約は

  • 1 ≦ n ≦ 100000
  • 1 ≦ k ≦ 100000
  • 1 ≦ w ≦ 10000

となっています．

線形探索による実装

まず，問題を解く時に考えられるのが線形探索の考え方を使い，最大積載量Pを0から増やしていき，その時に荷物を積み切ることができるかどうか調べていくということが考えられます．
では，線形探索を用いて実装していきます．

#Pの時に必要なトラックの数を求める関数
def unit_check(n, k, w_list, P):
    i = 0
    for j in range(k):
        weight = 0
        while weight + w_list[i] <= P:
            weight += w_list[i]
            i += 1
            if i == n:
                return 1
    return 0

n, k = map(int,input().split())
w_list = [0] * n
for i in range(n):
    w_list[i] = int(input())

P = max(w_list) - 1
flag = 0
while flag == 0:
    P += 1
    flag = unit_check(n,k,w_list,P)
print(P)

このコードの提出結果は次のようになります． f:id:tech_shelf:20200525164354p:plain

二分探索による実装

前述のコードの結果を見ると問題自体は解けているようですが，計算時間が間に合わないことがわかります．
ここで注目して欲しいところが，Pの値を一つずつ増やしているという部分です．
基本的には P で積載できなければ P+1 でも積載できない可能性が高いので，Pの値を大きく動かしながら探索した方が検討をつけやすいことがわかると思います．
そこで，これまでに学んだ二分探索を使ってPの値を作成する部分を調整してみましょう．
では，早速実装していきます．

#Pの時に必要なトラックの数を求める関数
def unit_check(n, k, w_list, P):
    i = 0
    for j in range(k):
        weight = 0
        while weight + w_list[i] <= P:
            weight += w_list[i]
            i += 1
            if i == n:
                return 1
    return 0

n, k = map(int,input().split())
w_list = [0] * n
for i in range(n):
    w_list[i] = int(input())

left = 0
#荷物の最大数x荷物の最大の重さ
right = 100000*10000
while left+1 < right:
    mid = (left+ right)//2
    check = unit_check(n, k, w_list, mid)
    if check == 1:
        right = mid
    else:
        left = mid
print(right)

このコードでの提出結果 f:id:tech_shelf:20200525164346p:plain

コード解説

まず，rightの初期値ですが，荷物の最大数x荷物の最大の重さとすることで k=1 の時でもトラックに全ての荷物を積むことができるので，このような値を取っています．
"while left + 1< right" の部分に関しては今回はleftとrightが共存するということがなく,"while left < right"とするとループを抜けられなくなってしまうのでこのようになっています．
最後にrightを出力しているのはunit_checkで"1"が帰ってきている中で最小のものが答えなのでwhileを抜けた時のrightが答えになっています．

コードの中身に関してこうした方がいいやここがわからないなどあればコメントよろしくお願いします！

実装して学ぶ基本探索アルゴリズム ~線形探索と二分探索~

python アルゴリズム関係

目次

探索とは

データ集合の中から目的の要素を探し出す処理のことです．
競技プログラミングでは与えられた配列に対して処理を行うことが多いので，覚えておくべきものの一つになります．
その中でも基本となるアルゴリズムは線形探索，二分探索，ハッシュ法になります．
では，早速それぞれのアルゴリズムの説明と実装に移っていきます．

配列の先頭から各要素が目的の値と等しいかどうかを順番に調べます．等しいものを見つけた時点でその位置情報を返し，探索を終了する単純なものになります．
もし末尾まで調べて目的の要素がなければ特別な値(競プロなどでは"-1"など指定されています．)を返します．
アルゴリズム効率の悪さはありますが，データの並び方に関係なく，利用することができます.
競プロでは計算量を考慮しなければいけませんが，まずはこれでいけるかどうか考えてみるといいかもしれませんね．
対応する問題はALDS1_4_A:Linear Searchです．
問題の意図としてはn個の整数を含むリストxとq個の重なりのない整数を含むリストyを比較し，リストyの要素がリストxに何個含まれているかを答える問題になっています．
では，早速実装していきましょう．
今回は素直な実装とpythonの特徴を生かした実装の二つを用意してみました．

素直な実装

N = int(input())
num_list = list(map(int, input().split()))
q = int(input())
search_num = list(map(int,input().split()))
ans = 0
for i in search_num:
    if i in num_list:
        ans += 1
print(ans)

最初の4行は入力を受け取っているだけなのであまり気にしないでください．if文でnum_listの中にsearch_num[i]が含まれているか確認しています．この時，n回の比較をしているので，オーダーはO(qN)となります．

pythonの特徴(set)を生かした実装

N = int(input())
num_list = list(map(int, input().split()))
q = int(input())
search_num = list(map(int,input().split()))
ans = 0
for i in set(num_list):
    if i in search_num:
        ans +=1
print(ans)

少し計算量の話を追加で書きます.
pythonの特徴を生かした実装で使ったsetは集合を表していてリストの中身の重なりのある整数を重なりのない状態にしています．また，setのオーダーはO(1)です(参考)．扱った問題ではn個のリストの中に同じ整数が含まれていることがあったので，多少計算時間が短くなると思います．
今回の問題ではNが大きくなれば計算量はもちろん増えますが，qにも依存しているので条件次第では計算時間が大きく変わるので問題文などをよく読んで解きましょう.
実際Atcoderのような競技プログラミングではPythonでO(n2)になると厳しいケースなどもあるので選ぶ探索アルゴリズムが重要になってきます．

二分探索ではデータの大小関係を利用しています．そのため，配列が整列されて管理されている場合，効率的に探索することができるアルゴリズムです．
基本的な動作は

  • 配列全体を探索の範囲にする
  • 探索が終了するまで以下の処理を繰り返す．
    1. 探索の範囲内の中央の要素を調べる
    2. 目的の値と中央の要素が一致した場合探索を終了する．
    3. 目的の値が中央の要素よりも小さければ二分したうちの前半部分を，
      大きければ二分したうちの後半部分を探索範囲として1.に戻る．

各計算ステップが終わるごとに調べる範囲が半分になっていくので，高速に探索を行うことができます．
対応する問題はALDS1_4_B:Binary Searchになります．
問題の意図は先ほどと変わらないのですが，注目して欲しいのが制約部分です．

  • 整数のリストSは昇順に並んでいる．
  • n ≤ 100,000 , q ≤ 50,000

つまり，入力はソートされた整数で与えられることと先ほどの線形探索だとO（qn）だったので 5.0 x 109 となり計算量が先ほどの問題の1000 倍かかるようになっているということに注目して欲しいです．こういった場合に二分探索は威力を発揮します．
では早速実装して行ってみましょう．

def binary_search(num_list, key):
    left = 0
    right = len(num_list)
    while right > left:
        mid = (left + right)//2
        if num_list[mid] == key:
            return 1
        #前半部分に答えがある
        if num_list[mid] > key:
            right = mid
        #後半部分に答えがある
        elif num_list[mid] < key:
            left = mid + 1            
    return 0
            
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))
ans = 0
for i in T:
    ans += binary_search(S, i)
print(ans)

今回解いた問題は同じなので，線形探索のコードと二分探索のコードどちらとも提出してみました．
結果は次のようになります．

線形探索の結果

f:id:tech_shelf:20200524191150p:plain

二分探索の結果

f:id:tech_shelf:20200524190731p:plain

後半のテストケースになるにつれて(計算量が多くなるにつれて)計算速度に違いが大きく表れていることがわかると思います．
二分探索はその名の通り計算する範囲を半分にしていくので必要となる計算量はO(logn)となります．
今回の問題では n ≦ 100,000 までの範囲だったので二分探索自体は16回程度の探索回数で答えにたどり着きます．
二分探索を扱った問題は競技プログラミングでよく出てくるのでこれを機に一緒に覚えましょう!

ハッシュ法

ハッシュ関数と呼ばれる関数値によって，要素の格納場所を決定する方法です．データ構造の一種でハッシュテーブルと呼ばれる表を用いる探索アルゴリズムです．
要素の値を引数として関数を呼び出すだけでその位置を特定することができるので，データの特性によっては高速に探索することができます．
pythonの場合全く同じではないですが辞書型がこれに当たると思います．
該当する問題はあるのですが，pythonで解くと簡単に済んでしまうので今回は省略させていただきます.