Recursion
選択ソート 配列から最小・最大値を探し，先頭要素と交換することを繰り返すことで整列を行う方法。 未整列部分の値を全て確認するので、等差数列的に計算数が加算され、時間計算量は0(n2)必要になる。 def selection_sort(arr): # 結果を出力するリスト res…
動的計画法 解決するべき問題を簡単に解決できる細かい問題に分割し、その細かい問題の解答を利用して大きな問題を解くこと。 動的計画法に向いている問題 再帰的な問題は向いている。 また最適部分構造(親問題が最適化を問うており、その子問題も同様に最適…
エラトステネスの篩 素数を見つけるためのアルゴリズム。 素数の倍数を除外していき、全ての数値を走査して最後まで除外されなかった数値群が素数となる。 ja.wikipedia.org 実装 # n以内の素数をリストで返す def sieve_of_eratosthenes(n): n += 1 if n ==…
現在Recursionに取り組んでいる。 そこで学んだことをメモする。 リスト（List） 生成 直接要素を指定 リスト内包表記 文字列をリストに変換 任意の値を任意個数要素にもつリストを生成 操作 読み取り 特定インデックスの値 for文を使用して繰り返し処理 後…
現在Recursionに取り組んでいる。 そこで学んだことをメモする。 インスタンスを生成すると、その実態はヒープ領域に格納される。 以下のようにインスタンスが格納されているヒープ領域のアドレスを取得できる。 class Person: def __init__(self, name): se…
現在Recursionに取り組んでいる。 そこで学んだことをメモする。 メモ化再帰 再帰処理において、同じ引数の計算を何度も行う場合がある。 そこで計算結果をメモとしてキャッシュして効率化をはかること。 例えば以下が計算結果をキャッシュする前。 （例とし…
現在Recursionに取り組んでいる。 そこで学んだことをメモする。 グローバル変数は、プログラムの実行中常にメモリを占有する グローバル変数は、グローバルスコープに紐づけられる グローバルスコープはプログラムのどこからでもアクセスできるスコープ ど…
現在Recursionに取り組んでいる。 そこで学んだことをメモする。 スコープ データや関数の影響範囲のこと。 ローカルスコープとグローバルスコープがあり、 ローカルスコープは特定のクラスや関数内の、制限された領域のこと。 ローカルスコープ内で定義され…
現在Recursionに取り組んでいる。 そこで学んだことをメモする。 再帰処理 再帰処理とは、とある処理の中で、自分自身を呼び出す処理のこと。 詳しくは以下の記事で紹介した。 note-tmk.hatenablog.com 最大公約数 複数の数値が存在するとき、各数値の約数の…
現在Recursionに取り組んでいる。 そこで学んだことをメモする。 ハノイの塔 3本の棒と複数の円盤を用いたシンプルなパズル。 円盤を目的の棒に、なるべく少ない移動回数で移動させるというもの。 円盤は全てサイズが異なり、サイズの小さい円盤は大きい円盤…
現在Recursionに取り組んでいる。 そこで学んだことをメモする。 フィボナッチ数列 次の漸化式で表現される数列をフィボナッチ数列と呼ぶ。 計算量はO(2n)である。 F0 = 0 F1 = 1 Fn = Fn-1 + Fn-2 (n ≥ 2) ja.wikipedia.org フィボナッチ数列は自然界でも観…
現在Recursionに取り組んでいる。 そこで学んだことをメモする。 テキストデータの圧縮 Recursionの練習問題で、以下のような問題が出た。 # 文字列を以下のように圧縮する関数を書け "aaabbbbccd" → "a3b4c2d" この関数は再起処理を用いるとシンプルに実装…
現在Recursionに取り組んでいる。 そこで学んだことをメモする。 再帰処理 再帰処理とは、とある処理の中で、自分自身を呼び出す処理のこと。 例えば以下のような処理。 def sum(n): if n == 0: return 0 return sum(n-1) + n これを実行すると以下のように…
