【Udemy】アルゴリズム・データ構造入門 ソート #3.2

ron-tech.hatenablog.com
↑の続きで、引き続き各種ソートの紹介を行います。

ソート	Average	Best	Worst	安定	備考
gnome	O(n2)	O(n)	O(n2)	Yes	bubble sortに類似
insertion	O(n2)	O(n)	O(n2)	Yes	整列済のデータ列に適切に新データを挿入していくようにソートを行う
bucket	O(n+k)	O(n+k)	O(n2)	Yes	あらかじめデータがとりうる値すべての容器(バケット)を順番どおりに並べて用意しておき、値を対応する容器に移すことでソートを行う
shell	Depends on gap sequence	O(n log n)	O(n2)	No	insertion sortの改良 リストにおいてあらかじめ離れている要素を交換しておき、最終的に挿入ソートを実行
counting	O(n)	O(n)	O(n)	Yes	数字が入りうる空の配列を予め用意し、要素をカウントする。

• gnomeソート：後ろの要素と比較して入れ替えていくと、入れ替えた時のみ戻って比較を行うことで並び替える。

from typing import List

def gnome_sort(numbers: List[int]) -> List[int]:
    len_numbers = len(numbers)
    index = 0
    while index < len_numbers:
        if index == 0:
            index += 1
        if numbers[index] >= numbers[index-1]:
            index += 1
        else:
            numbers[index], numbers[index-1] = numbers[index-1], numbers[index]
            index -= 1

    return numbers

• insertionソート：隣り合った要素を比べて順番にソートする方法で、整列済みの部分に対して後ろにある要素をどこに入れるのかを探る。

from typing import List

def insertion_sort(numbers: List[int]) -> List[int]:
    len_numbers = len(numbers)
    for i in range(1, len_numbers):
        temp = numbers[i]
        j = i - 1

        while j >= 0 and numbers[j] > temp:
            numbers[j + 1] = numbers[j]
            j -= 1

        numbers[j + 1] = temp

    return numbers

• bucketソート：予めデータがとりうる値すべての容器を順番どおりに並べて用意しておき、値を対応する容器に移す。

from typing import List

def insertion_sort(numbers: List[int]) -> List[int]:
    len_numbers = len(numbers)
    for i in range(1, len_numbers):
        temp = numbers[i]
        j = i - 1

        while j >= 0 and numbers[j] > temp:
            numbers[j + 1] = numbers[j]
            j -= 1

        numbers[j + 1] = temp

    return numbers

def bucket_sort(numbers: List[int]) -> List[int]:
    max_num = max(numbers)
    len_numbers = len(numbers)
    size = max_num // len_numbers

    buckets = [[] for _ in range(size)]
    for num in numbers:
        i = num // size
        if i != size:
            buckets[i].append(num)
        else:
            buckets[size-1].append(num)

    for i in range(size):
        insertion_sort(buckets[i])

    result = []
    for i in range(size):
        result += buckets[i]

    return result

• shellソート：リストにおいてあらかじめ離れている要素を交換しておき、最終的に挿入ソートを実行。

from typing import List

def shell_sort(numbers: List[int]) -> List[int]:
    len_numbers = len(numbers)
    gap = len_numbers // 2
    while gap > 0:
        for i in range(gap, len_numbers):
            temp = numbers[i]
            j = i
            while j >= gap and numbers[j-gap] > temp:
                numbers[j] = numbers[j-gap]
                j -= gap
            numbers[j] = temp
        gap //= 2

    return numbers

• countingソート：数字が入りうる空の配列を予め用意し、要素をカウントする。

from typing import List

def counting_sort(numbers: List[int]) -> List[int]:
    max_num = max(numbers)
    counts = [0] * (max_num + 1)
    result = [0] * len(numbers)

    for num in numbers:
        counts[num] += 1

    for i in range(1, len(counts)):
        counts[i] += counts[i-1]

    i = len(numbers) - 1
    while i >= 0:
        index = numbers[i]
        result[counts[index]-1] = numbers[i]
        counts[index] -= 1
        i -= 1

    return result

次回でソート紹介は最後になります。
お疲れ様でした。

【Udemy】アルゴリズム・データ構造入門 ソート #3.1

基礎的な内容ですが、普段何気なくライブラリとして使っている各種ソートについてまとめます。

ソート	Average	Best	Worst	安定	備考
bogo	O((n+1)!)	O(n)	∞	No	ただランダムに入れ替えるだけ
bubble	O(n2)	O(n)	O(n2)	Yes	隣接する要素を並び替える。1週毎に右側から大きい順に並んでいく。
cooktail	O(n2)	O(n)	O(n2)	Yes	bubbleソートを双方向にすることで若干の効率化を図る。
comb	O(n2**g)	O(n log n)	O(n2)	Yes	bubbleでは隣接する要素を比較・交換するが、combソートでは適当な間隔(慣習的に1.3)のデータに対して比較・交換を行う。g=n//1.3
selection	O(n2)	O(n2)	O(n2)	Yes	最大値を探索して配列最後の要素と入れ替える。

• bogoソート：ただランダムに値を入れ替える。

from typing import List

def in_order(numbers: List[int]) -> bool:
    return all(numbers[i] <= numbers[i+1] for i in range(len(numbers)-1))

def bogo_sort(numbers: List[int]) -> List[int]:
    while not in_order(numbers):
        random.shuffle(numbers)
    return numbers

• bubbleソート：隣接する要素を比較して並び替える。1週毎に右側から大きい順に要素がならんでいく。

from typing import List

def bubble_sort(numbers: List[int]) -> List[int]:
    len_numbers = len(numbers)
    for i in range(len_numbers):
        for j in range(len_numbers - 1 - i):
            if numbers[j] > numbers[j + 1]:
                numbers[j], numbers[j + 1] = numbers[j + 1], numbers[j]
    return numbers

• cooktailソート：bubbleソートを双方向にすることで若干の効率化を図る。

from typing import List

def cocktail_sort(numbers:List[int]) -> List[int]:
    len_numbers = len(numbers)
    swapped = True
    start = 0
    end = len_numbers - 1
    while swapped:
        swapped = False

        for i in range(start, end):
            if numbers[i] > numbers[i+1]:
                numbers[i], numbers[i+1] = numbers[i+1], numbers[i]
                swapped = True

        if not swapped: break

        swapped = False
        end = end - 1

        for i in range(end-1, start-1,-1):
            if numbers[i] > numbers[i+1]:
                numbers[i], numbers[i+1] = numbers[i+1], numbers[i]
                swapped = True

        start = start + 1

    return numbers

• combソート：bubbleでは隣接する要素を比較・交換するが、combソートでは適当な間隔(慣習的に1.3)のデータに対して比較・交換を行う。

from typing import List

def comb_sort(numbers: List[int]) -> List[int]:
    len_numbers = len(numbers)
    gap = len_numbers
    swapped = True

    while gap != 1 or swapped:
        gap = int(gap / 1.3)
        if gap < 1:
            gap = 1

        swapped = False

        for i in range(0, len_numbers - gap):
            if numbers[i] > numbers[i + gap]:
                numbers[i], numbers[i + gap] = numbers[i + gap], numbers[i]
                swapped = True
    return numbers

• selectionソート：最大値を探索して配列最後の要素と入れ替える。

from typing import List

def selection_sort(numbers: List[int]) -> List[int]:
    for i in range(len(numbers)):
        min_idx = i
        for j in range(i+1, len(numbers)):
            if numbers[min_idx] > numbers[j]:
                min_idx = j

        numbers[i], numbers[min_idx] = numbers[min_idx], numbers[i]
    return numbers

コードを実装してみると、理解が深まりますね。
お疲れ様でした。

ubuntuでDockerコマンド実行時sudoを省略する

ubuntuでdockerを使う場合、デフォルトでは頭にsudoをつける必要があります。
地味に面倒なので、sudoを省略する方法を忘れないように残しておきます。

やること

gpasswdを用いてdocker groupにログインしているユーザーを追加

$ sudo gpasswd -a <user> docker   

たったこれだけです、簡単ですね。 ubuntuにはユーザグループという概念があり、そのグループに入っているユーザに指定した権限を付与することができます。
今回はログインユーザーをdockerグループに追加してあげれば良いです。

変更を反映するには再起動が必要なので、注意です。

$ sudo reboot

以上です。お疲れ様でした。

【AtCoder】ABC200 感想戦

2021/5/12に開催されたABC200を振り返ります。
結果はA~Cの3完でした。D問題もう少しで解けそうでしたがあと1歩及ばずでした。
順位：2320位、パフォーマンス：1042、レート：635 → 686(茶)

• A問題：A - Century
  西暦から世紀を求める問題でした。
  100の倍数の西暦の場合に惑わされなければ非常に簡単でした。

n = int(input())
print((n-1)//100 + 1)

• B問題：B - 200th ABC-200
  整数Nに対して
  • Nが200の倍数であればNを200で割る。
  • そうでなければ、NをNの後ろに文字列として200を付け加えた整数に置き換える。

という処理をK回繰り返した後の数字を出力する問題でした。
Kの上限が20と小さいので普通にループを回せば良いです。
文字列として200を後ろに加える処理はNを1000倍して200を足せば良いです。(文字列に変換して足しても良い)

n, k = map(int,input().split())
for i in range(k):
    if n % 200 == 0:
        n //= 200
    else:
        n = n*1000 + 200
print(n)

• C問題：C - Ringo's Favorite Numbers 2
  N個の正整数からなる数列Aにおいて、以下の条件を全て満たす整数の組(i, j)の個数を求める。
  • 1 <= i < j <= N
  • Ai - Ajは200の倍数

引き算した結果が200の倍数になるということは、配列Aの全要素のmod 200を予め算出しておき、同じ数の選び方を考えれば良いです。
pythonの場合、collectionライブラリのCounterを使うとどの要素が何個あるか辞書型で簡単に求められます。
その後n個から2つを選ぶ組み合わせ(nC2)はn*(n-1)//2で求められるので、答えに加算していけば良いです。

from collections import Counter
n = int(input())
a = list(map(int, input().split()))

a = [itm % 200 for itm in a]
cnt = Counter(a)

ans = 0
for val in cnt.values():
    ans += val * (val-1) // 2

print(ans)

• D問題：D - Happy Birthday! 2
  問題省略します。
  解けませんでしたが、以下のように考えました。
  • C問題と同様配列Aの全要素のmod 200を求め、後は要素の組み合わせで同じ値を作れるかを検証すれば良い。
  • 2⁷ < 200 < 2⁸より、n>=8の場合は絶対にYesになる。
  • 1<N<200よりbit全探索をするとTLEになる。

TLE対応で行き詰まりました。
結論、2⁸>200のため、鳩の巣原理より配列Aの最初の8要素でbit全探索をすれば良いらしいです。
これは初見では厳しかったです。鳩の巣原理勉強しないとですね。

• まとめ
  A~Cまではすらすらと解けましたが、Dで大ブレーキでした。
  レートは結構上がったので、この調子で緑を目指して頑張ります。

【Udemy】アルゴリズム・データ構造入門 #2

前回の記事ron-tech.hatenablog.com

の続きでSec2. アルゴリズムと計算量を受講しました。

Sec2. アルゴリズムと計算量

• アルゴリズム・・・問題を解決するための手順や計算方法。
  Googleの検索や、Teslaの自動運転など、高速な計算が求められる場合に最も早く解くためのアルゴリズムを実装できることが求められる。
  GAFAを筆頭とした企業の面接ではかならずアルゴリズム面接が行われる。

• データ構造とは・・・データの集まりをコンピュータの中で効果的に扱うため、一定の形式に系統立てて格納するときの形式。

• Big O Nation (Big O 記法)

引用： Understanding Big-O Notation With JavaScript | by Bonvic bundi | Better Programming

データが増えれていくにつれて、どれだけ計算に時間がかかるかを表す。

• 安定ソート・・・ソート判定において同一であると判断された入力データの順序がソート後も変わらない。

次回は各種ソートについて学んでいきます。
では！

【Udemy】アルゴリズム・データ構造入門 #1

前回の記事ron-tech.hatenablog.comでAtCoderの環境構築を行いました。

実践あるのみですが、理論的な勉強も並行して進めていきたいと思います。
まずはUdemyにて公開されている。現役シリコンバレーエンジニアが教えるアルゴリズム・データ構造・コーディングテスト入門

www.udemy.com

を受講しようと思います。 備忘録も兼ねて、セクション毎に簡単にまとめたいと思います。 では！

【AtCoder】VScodeで環境構築 in Mac

概要

プログラミングの練習でAtCoderを始めました。
デバッグは公式で提供されているコードテストを使用していましたが、テストケースのコピペなどだんだん煩わしくなってきたので、VScodeで環境構築しました。

動作環境

• macOS Big Sur 11.1
• VScode 1.52.1
• python 3.8.2

使用するツール

• online-judge-tools (ojt)
  テストケースの判定を自動化するツール
  コンテストサイトからサンプルケースをスクレイピングし、自動テストしてくれる。

• atcoder cli (acc)
  コンテストサイトからテストケースのダウンロード、やコード提出も行える。

インストール

pip install online-judge-tools
npm install -g atcoder-cli

もう少し詳しく知りたい方はatcoder-cliの開発者様のブログを参考にしてください。

使ってみる

1. ログイン

oj login -u ユーザー名 -p パスワード "https://atcoder.jp/"

以下のコマンドでチェックできる。

oj login --check "https://atcoder.jp/"

[*] You have already signed in.と出力されればOK。

2. コンテストディレクトリ作成

• コンテストIDを取得 (画像はabc188)

  

  コンテストID

• ディレクトリ作成

acc new コンテストID (abc188)

上記コマンドを叩き、usernameとpasswordを入力すると、どの問題を解くか聞かれるので希望の問題を選択する。

問題選択

選択した問題のサンプルケースがダウンロードされる。

ディレクトリ構成

3.問題を解く

問題のディレクトリ直下にコードファイルを作成して、コードを書く。ファイルの置き場所、言語等は各自ご自由に。
※ pythonで書く場合、最初に実行環境を指定する必要があるらしいです。以下サンプル

#!/usr/bin/env python3
~~

• デバッグ コード書けたらテストケースでデバッグします。

oj t -c "python3 a.py" -d tests 

上記a.py、testsはそれぞれコードファイルとテストケースのディレクトリへのパスを指定する。

デバッグ結果

それぞれのテストケースについての計算時間、結果が表示される。

4.提出

acc submit a.py

現在のディレクトリからどのコンテストのどの問題を説いているか識別してくれるので、単にファイルを指定してあげればOKです。
※a.pyの指定の際にdir/a.pyのようなパスを指定すると、何故かエラーになりました。提出するファイルと同じ階層で実行するのがよさそうです。
提出すると、自動でブラウザが立ち上がり通常通り結果が表示されます。
いや〜便利ですね☆

5.その他

• 問題の追加

acc add

問題を選択する画面が出てくるので、次に解く問題を選ぶ。
1問ずつ問題を選択するのが面倒な方は

acc config default-task-choice all

を実行することで、デフォルトでコンテストの全問題の環境をまとめて作るようにすることができます。

まとめ

VScodeでAtCoderの環境構築をしました。
自分で書いたコードの管理もしやすいので、おすすめです。
もうすでに達成感がありますが、これからちゃんと勉強していきたいと思います。
では！