スズメの本棚

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

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

実装して学ぶ基本データ構造~Stackの応用編~

python アルゴリズム関係

面積計算

これまでの知識を活用した応用問題を解いていきたいと思います．
同じ問題を解きたい方はAOJの問題から解いてみてください
二次元上に対して，"\", "/", ""の三種類の入力が入ってきます．この三種類の入力によってできた図形に対して，雨が降った時に溜まる面積を求めるというのが本問題の目的になります．また，求めた面積の総和に加えて，図形の中にできた水溜りの数とその面積を求める必要があります．
対応する問題はALDS1_3_D: Areas on the Cross-Section Diagram
この問題における入力例で問題の解説をしていきたいと思います．
入力 : \///_/\/\\//\///\_\/\//\
出力 : 35
　　　5 4 2 1 19 9
この入力を図にしたものが下図になります．
f:id:tech_shelf:20200521013414p:plain 今回の解き方としては

  • "\"が来たら
    1. "\"の入力の位置をリストxに追加する.
  • "/" が来たら
    1. リストxから"\"の位置情報を取り出す
    2. "/"の位置と取り出した位置情報の差を計算する．
    3. "\"と"/"の位置の間にすでに面積リストに追加されている要素があればその面積と2の計算結果を足し合わせる．
    4. 確定した計算結果を面積のリストに追加する．

解き方だけではイメージがわからないと思うので，それぞれのタイミングで何をしているかとそのイメージをgifにまとめたので確認してみてください.
f:id:tech_shelf:20200521021857g:plain それでは，実際に実装していきます．

def area_cal(input_fig):
    stack = []
    # area = [[面積計算が始まった位置, 面積],・・・]
    area = []
    total = 0
    for i in range(len(input_fig)):
        fig = input_fig[i]
        if fig == "\\":
            stack.append(i)
        elif fig == "/" and stack:
            j = stack.pop()
            width = i - j
            total += width
            while area and area[-1][0] > j:
                width += area[-1][1]
                area.pop()
            area.append([i,width])
    return area, total
            
input_fig = input()
area, total = area_cal(input_fig)
print(total)
if area:
    print(len(area),*list(zip(*area))[1])
else:
    print(0)

提出してみたい際はこのままの形で提出すれば通ると思います．また，動作を確認したい方はinput()の部分を自分なりの記号列に書き換えて見ると色々試せると思います.
ぜひ解いてみてください.

実装して学ぶ基本データ構造~StackとQueue編~

アルゴリズム関係

StackとQueueに関して

まず，初めに基本的なデータ構造を学ぶとき，スタックやキューが出てくると思います．この二つが持つデータ構造からそれぞれ使いどころが変わってきます．
データの処理の仕方などを考える上で必要になってくると思うので，単にLIFOやFIFOという言葉を学ぶのではなく実践的に学ぶとそれぞれの違いが学べると思います．
以下ではスタックとキューの考え方からそれを用いたプログラミングの問題に取り組んでいます．意味を理解しながら，一緒に実装していきましょう．

Stack

Stackとは

一時的にデータを退避したいときに有効なデータ構造で，データの中で最後に入ったものが最初に取り出される後入れ先出し(LIFO:Last In First Out)の規則に従ってデータを管理する方法です．
基本的にはデータの追加・取り出し・配列が空かどうか・配列が一杯かどうかなどを操作を持っています．

逆ポーランド記法(演習問題)

逆ポーランド記法は，演算子を被演算子の後に記述するプログラムの記法.
例えば，(1+2) * (4+3)という数式があった場合逆ポーランド記法では
12+43+* と記述されます．
これを用いればプログラミングの知識で電卓のようなものを作ることができます．

入力例ではALDS1_3_A：Stackに従い，
"1 2 + 3 4 - *"
を入れたいと思います.
"-3"が出力されれば正解となります．
では，実際に実装していきましょう．

def Stack(order_list):
    cal_list = []
    for content in order_list:
        if content == "+":
            b = cal_list.pop()
            a = cal_list.pop()
            cal_list.append(a+b)
        elif content == "-":
            b = cal_list.pop()
            a = cal_list.pop()
            cal_list.append(a-b)
        elif content == "*":
            b = cal_list.pop()
            a = cal_list.pop()
            cal_list.append(a*b)
        else:
            cal_list.append(int(content))
            
    return cal_list[0]

order = "1 2 + 3 4 - *"
order_list = list(order.split())
ans = Stack(order_list)
print(ans)

実際にAOJの問題を解く場合はorder_list = input().split()として提出してみてください．
また，今回は演算子が"+ - *" の三つでしたが本来は除算も含まれるのでどうすれば機能を追加できるか試してみてください.
本来はエラー処理なども考える必要がありますが，今回は計算ロジックだけ汲み取れればいいと判断し，このようになっています．

Queue

Queueとは

待ち行列とも呼ばれ，データを到着した順に処理していくときに使うデータ構造で，データの中で最初に入ったものが最初に取り出される，先入れ先出し（FIFO: First In First Out）の規則に従ってデータを管理します．
イメージとしてはレジ待ちの行列のような感じですかね．
基本的な操作はスタックと同様です．

ラウンドロビンスケジューリング(演習問題)

ラウンドロビンスケジューリングとは，プロセスの管理方法の一つで，順番にプロセッサ(計算するところ)を割り当てる方式のことです．
一定時間プロセッサで処理を行なった後，まだプロセスが完了していなければキューの後ろにプロセスを回し，プロセッサは次のプロセスの処理を行うというのを繰り返していきます．

対応する問題はALDS1_3_B: Queueで入力例・出力例は次のようになります．

入力例 　 出力例 　
5 100
p1 150 p2 180
p2 80 p5 400
p3 200 p1 450
p4 350 p3 550
p5 20 p4 800 
def round_robin(queue_list, t):
    elapsed_time = 0
    while len(queue_list) > 0:
        p, c = queue_list.pop(0)
        if c-t > 0:
            elapsed_time += t
            queue_list.append([p, c-t])
        else:
            elapsed_time += c
            print("{} {}".format(p,elapsed_time))

N, cpu_time = map(int,input().split())
queue_list = []
for i in range(N):
    process,cost = input().split()
    queue_list.append([process, int(cost)])

round_robin(queue_list, cpu_time)

pythonの場合リストの大きさはあらかじめ決めることもできますが，決めずに作ることができるので，C言語などと比べて直感的にわかりやすい形になっているかと思います．
また，競技プログラミングに合わせた形で入力を受け取っているので初めての人は見慣れないとは思います．どういった処理を行なっているのかはround_robinの部分に全て書いてあるので追ってみてください．

シェルソートの実装

アルゴリズム関係

シェルソート

シェルソートは，挿入ソートの特徴を生かし，さらに高速化したアルゴリズムになります．
基本的な動作は挿入ソートと同じで二つの数字の大小を比較をしていき，最終的にソートが完成されているというものです．
挿入ソートでは隣り合った要素の大小の比較でしたが，シェルソートでは無駄な比較をなるべく減らすために一定の間隔g毎の数字の大小の比較をしていきます.
ある間隔gが終わったらそれよりも小さな間隔でさらにソートしていき，最終的に間隔1の比較，つまり，挿入ソートを行うことで全体が完全にソートされることになります.
この間隔gの選び方は諸説あるらしいのですが，gn+1= 3gn+1に従って選ぶとある程度高速になるそうです．
つまり，今回は20個の配列で試しているのでg = {1,4,13}のように選ぶといいようですね.
本プログラムではgapという配列を利用して間隔を指定しているので，そこの部分を自分なりにアレンジしてみて試してみてください.

def make_gap(num_list):
    gap_num = 1
    gap = [1]
    while gap_num < len(num_list):
        gap_num = gap[-1]*3 + 1
        gap.append(gap_num)
    gap.pop()
    return gap

def n_gapsort(num_list, gap):
    sort_list = list(num_list)
    for i in range(gap,len(num_list)):
        target = sort_list[i]
        j = i - gap
        while j >= 0 and sort_list[j] > target:
            sort_list[j+gap], sort_list[j] = sort_list[j], target
            j -= gap
    return sorted_list

def shellsort(num_list):
    sort_list = list(num_list)
    gap = make_gap(num_list)
    for i in gap:
        sort_list = n_gapsort(sort_list,i)
    return sort_list

num_list = list(range(1,20))
shuffle(num_list)
sorted_list =  shellsort(num_list)
print(num_list)
print(sorted_list)

実際のソート部分はn_gapsortで行なっています．
また，このn_gapsortは挿入ソートのプログラムを少しいじるだけで作ることができるので力試しに挑戦してみてください！

基本ソートアルゴリズム3つの実装

アルゴリズム関係

挿入ソート

トランプを並び替える時などに左から小さい順に並び替えたりする場合によく使われている方法に似ています．
一枚のカードを取り出し，それをすでにソート済みのカードの適切な位置に挿入するというのが挿入ソートの基本的な考え方です．
基本的な動作としては

  • 先頭のものをソート済みとする
  • 残っている未ソート部分がなくなるまで以下を繰り返す
    1. 未ソート部分の先頭の要素xを一つ取り出す
    2. ソート済み部分の後ろの要素とxの値の大小を比較し，xより要素が大きければリストの順番を入れ替える
    3. 適切な位置に要素xを入れる

このソートアルゴリズムの計算量は最悪の場合O(n2)となります．
また，入力データがソートした時と真逆の状態の時に計算量は最大となり，その並び順が計算量に大きく響きます．
実装に関しては次のようになります．

def insertsort(num_list):
    sort_list = list(num_list)
    for i in range(len(num_list)):
        target = sort_list[i]
        j = i -1
        while j >= 0 and sort_list[j] > target:
            sort_list[j+1], sort_list[j] = sort_list[j], target
            j -=1
    return sort_list

num_list = list(range(1,20))
shuffle(num_list)
sorted_list =  insertsort(num_list)
print(num_list)
print(sorted_list)

途中の状態を確認したい場合はwhile文の後にsort_listをprintしてみてください．

バブルソート

バブルソートも挿入ソートと同様にソートしていく過程で未ソート部分とソート済み部分に分けられます．
基本的な動作としては

  • 順番が逆担っている隣接容姿がなくなるまで次の処理を繰り返す
    1. 配列の末尾から隣接する要素を順番に比べていき，正しい大小関係ならば逆に交換する．
      (ループを抜けると未ソート部分の中で一番小さな要素がソート済みに変わっていくイメージ)

バブルソートも挿入ソート同様オーダーはO(n2)となります．
実装に関しては次のようになります．

def bubblesort(num_list):
    i = 0
    sort_list = list(num_list)
    for i in range(len(num_list)-1):
        for j in range(len(num_list)-1, i, -1):
            if sort_list[j] < sort_list[j-1]:
                sort_list[j], sort_list[j-1] = sort_list[j-1], sort_list[j]            
    return sort_list

num_list = list(range(1,20))
shuffle(num_list)
sorted_list =  bubblesort(num_list)
print(num_list)
print(sorted_list)

選択ソート

選択ソートにおいても既出のソートアルゴリズム同様ソートしていく過程で未ソート部分とソート済み部分に分けられます．
動作はプログラムとして直感的に理解しやすい形になっていて，未ソート部分の中から一番小さな要素を見つけ出し未ソート部分の先頭の要素と入れ替えていくということを繰り返すことになります．
基本的な動作としては

  • 次の処理をN-1回繰り返す
    1. 未ソート部分から最小の要素xの位置を見つけ出す
    2. 未ソート部分の先頭の要素の位置と最小の要素xの位置を入れ替える
    3. 新しいxの要素の位置をソート済みとする

これまでのソートアルゴリズムと異なり，選択ソートは離れた要素同士の位置を入れ替えていくことを行うため，ソート後の結果が不安定になることがあります.
ソートが不安定な状態とは今回考えているのは一次元の配列なので問題はありませんが，テストの結果のように多次元の配列を考えた時に理想とするソート結果と実際のソート結果で差異が生まれてしまうことを言います．
ちなみに，選択ソートのオーダーに関してもO(n2)となります．
実装に関しては次のようになります．

def selectionsort(num_list):
    sort_list = list(num_list)
    for i in range(len(num_list)):
        minposi = i
        for j in range(i,len(num_list)):
            if sort_list[minposi] > sort_list[j]:
                minposi = j
        sort_list[i], sort_list[minposi] = sort_list[minposi], sort_list[i]
    return sort_list
                  
num_list = list(range(1,20))
shuffle(num_list)
sorted_list =  selectionsort(num_list)
print(num_list)
print(sorted_list)

これらのアルゴリズムは動きが直感的にわかりやすく，実装もしやすいと思いますので，自分の得意な言語で実装してみてください！

計算量の考え方

アルゴリズム関係
計算量の評価方法に関して

競技プログラミングなどに参加する上で，後々問題になってくるのが計算量に関する考え方です．
計算量には

  • 時間計算量
  • 領域計算量

のふたつがあります．
実際にシステムにアルゴリズムを適用させる際にはこの二つの制約を守ったり，出来るだけ計算量を小さくする必要があります．

O表記に関して

アルゴリズムの計算量を評価するもののひとつがO表記です．
例えば，プログラム上でforループが一つあればn回ループを処理することになるのでO(n)となります．
ここでO(n)とO(n2)を比較してみましょう.
nが最大100までの場合
O(n)のプログラムは最大で100回ループを処理する
一方で，
O(n2)のプログラムは最大で10000回ループを処理する
この二つを比較では計算量は100倍に増えています．
つまり，nの数に比例して計算量は多くなり，発散してしまいます．
また，オーダーの中身の値，つまり，ループの回数にも大きく依存して計算量は増えていきます.

計算量の比較

nの値に応じてそれぞれのオーダーがどのように変わるか表にまとめたので参考までに覚えておくと役にたつと思います．
f:id:tech_shelf:20200510175035p:plain 表からわかるようにオーダーが大きければnの値が小さかったとしても計算量はとても大きくなってしまいます．
実際に，競技プログラミングに参加する際には時間制約が2秒というように指定されていたりします.
なるべくオーダーは小さくなるようにアルゴリズムを構築しましょう！