はなちるのマイノート

Unityをメインとした技術ブログ。自分らしくまったりやっていきたいと思いますー!

アルゴリズム

アルゴリズムイントロダクション第4章の個人まとめ

はじめに 前回の続きをやっていきたいと思います。 www.hanachiru-blog.com今回のテーマは「分割統治法」になります。 はじめに 分割統治法 置き換え法 1. 推定 2. 数学的帰納法 再帰木法 マスター法 マスター定理 分割統治法 分割統治では以下の3つの段階…

アルゴリズムイントロダクション第3章の個人まとめ

はじめに 前回の続きをやっていきたいと思います。 www.hanachiru-blog.comちなみに内容的には昔書いたこの記事とかなり似ている感じでした。 www.hanachiru-blog.com はじめに 第3章「関数の増加」 Θ記法 O記法 Ω記法 o記法 ω記法 第3章「関数の増加」 Θ記…

アルゴリズムイントロダクション第1~2章の個人まとめ

はじめに 今回はアルゴリズムの名著とも言われている以下の本を読み、そのまとめを備忘録の意味合いも兼ねて書き残しておきたいと思います。 はじめに 第1章「計算におけるアルゴリズムの役割」 第2章「さあ,始めよう」 挿入ソート アルゴリズムの正当性 …

【C#】最小頂点被覆問題の近似アルゴリズムを実装してみる

はじめに 今回は最小頂点被覆問題の近似アルゴリズムを実装してみたいと思います。最小頂点被覆問題の詳細は後述しますが、NP困難の問題と知られていて多項式時間で解くことできないことが証明されています。そういった解くことが難しい問題に関して、以下の…

【Unity】UnityでBag of Wordsベクトルに変換できるライブラリ「UniBagOfWords」を公開してみた(文章の類似度の実装も)

はじめに タイトルの通り,UnityでBag of Wordsベクトルに変換できるライブラリUniBagOfWordsを公開しました。 github.comこれの使い方や応用として文章の類似度の計算をしてみたいと思います。 はじめに できること 導入方法 使い方 応用(文章類似度の計算)…

【C#】グラフの連結成分を調べるアルゴリズムを実装してみる

はじめに 今回はグラフの連結成分を調べるアルゴリズムを実装してみようと思います。そもそもグラフの連結成分とは「任意の2点間に道があるグラフのうち、極大な連結部分グラフ」のことをいいます。以下の画像のようなグラフだと{0, 1},{2, 3, 4},{5, 6, 7…

【C#】トポロジカルソートを実装してみる

はじめに 今回はトポロジカルソートを実装していきたいと思います。ja.wikipedia.orgトポロジカルソートとは有向非巡回グラフ(DAG)においてどのノードもその出力辺の先のノードより前にくるように並べるアルゴリズムのことです。 トポロジカルソート アルゴ…

【C#】配列から2つの要素を選び、指定した和になる組み合わせを列挙する

はじめに 今回扱ってみる問題はこんな感じ。 n個の配列Aと整数kが入力として与えられたとき,Aの2つの要素の和がkとなる組み合わせを列挙せよ 例. 入力:A = {1, 6, 4, 5, 3},k = 7 出力:(6, 1), (3, 4) 解き方 まずは2重ループを使った全探索の方法が思い…

【C#】2分探索木を実装してみる

はじめに 今回は2分探索木を実装してみようと思います。ja.wikipedia.org早速みていきましょう。 二分探索木 二分探索木は「左の子孫の値 ≤ 親の値 ≤ 右の子孫の値」という制約を持つ二分木のことを指します。 今回は以下の4つを実装します。 挿入 削除 要素…

【C#】選択ソートを実装してみる

はじめに 今回は選択ソートを実装していきたいと思います。 ja.wikipedia.orgこのアルゴリズムは実装は簡単だけど性能がいいといったソートアルゴリズムで、バブルソートと似た系統のものです。早速みていきましょう。 はじめに 選択ソート 実装 テスト 考察…

【C#】マージソートを実装してみる

はじめに 今回はマージソートを実装してみようという記事になります! ja.wikipedia.org前置きはなしに本題をみていきたいと思います。 はじめに マージソート 実装 使い方 考察 マージソート 英語ですが、この動画がすごく分かりやすく説明されていたのでオ…

【C#】シェルソートを実装してみる

はじめに 少し前に挿入ソートを実装してみました。 https://www.hanachiru-blog.com/entry/2020/07/30/180000www.hanachiru-blog.comこの挿入ソートをより高速化するために生まれたのが今回紹介するシェルソートになります。 ja.wikipedia.org早速みていきま…

【C#】ヒープソートを実装してみる

はじめに 今回はヒープソートを実装してみようという記事になります!ヒープソートというのは名前の通りヒープというデータ構造を用いたソートアルゴリズムであり,安定して高速に処理ができる(安定ソートという意味ではない)優秀なソートだと知られています…

【C#】基数ソートを実装してみる

はじめに 前回はバケットソートを紹介しましたが、今回はその改良版とも言われる基数ソートについて実装していきたいと思います。 ja.wikipedia.orgバケットソートではバケットの数が膨大になってしまうのはNGという制約がありました。計算量と引き換えにそ…

【C#】バケットソートを実装してみる

はじめに 前回は挿入ソートを紹介しましたが、今回はバケットソートを実装していきたいと思います。バケットソートはソートアルゴリズムでよくある要素を交換する手法を取らない面白いアルゴリズムです。 ja.wikipedia.orgまた以下の制約を満たさなければ動…

【C#】挿入ソートを実装してみる

はじめに 今回は挿入ソートを実装してみようという記事になります!挿入ソートはソートのアルゴリズムの一種で、性能はあまり良くないですが実装が簡単なアルゴリズムだと知られています。 ja.wikipedia.orgバブルソートと似た系統だと表現した方が分かりや…

【C#】Boyer-Moore法(BM法)を使って文字列の照合を行う

はじめに 今回はBoyer-Moore法(BM法)を自前で実装してみようという記事になります。BM法とは文字列検索アルゴリズムの一つで,他の文字列検索アルゴリズムと比べて優秀な部類と言われるアルゴリズムです。(最悪計算量は)C#をそれなりに触ったことのあるかた…

【C#】部分和問題(subset-sum problem)を解いてみる

はじめに 今回は部分和問題(subset-sum problem)を解いてみたいと思います。最初にネタバレをしてしまいますが、具体的にはbit全探索を用いた方法と動的計画法を用いた2種類を紹介していきます。アルゴリズムの教科書なんかでもよく出てくる問題なので、マス…

【Unity】xorを使った暗号化の基礎からPlayerPrefsの暗号化クラス作成まで

はじめに 今回はxor(排他的論理和)についてみていきます。xorを使った暗号化はかなり簡単な分類の暗号化アルゴリズムとして知られているので、すぐに習得できると思います。またその応用としてUnityのデータのセーブ・ロードのために用いられるPlayerPrefsを…

【C#】セグメント木を実装してみる

はじめに 今回はセグメント木を実装してみようという記事になります!セグメント木は主に区間上の値の更新と任意の区間内の最小値などの取得を高速化できます。構造としては完全二分木を用いていて、初期化に,更新・取得は共にで動作します。 en.wikipedia.…

【C#】ナップザック問題を解いてみる

はじめに 今回はナップザック問題を解いてみようという記事になります。 ja.wikipedia.orgナップザック問題は動的計画法の典型例なので、アルゴリズムの勉強にも良い問題だと思います。早速みていきましょう。 はじめに ナップザック問題とは 問題 方針 実装…

【C#】木の直径を求める

はじめに 今回は木の直径を求めてみようという記事になります!あまり用いる機会はないと思いますが、簡単な頭の体操のように捉えてくれれば嬉しいです。早速みていきましょう。 はじめに 木の直径とは? 実装方針 コード さいごに 木の直径とは? 木の直径…

【C#】幅優先探索(BFS)を実装してみる

はじめに 前回深さ優先探索の実装をしてみました。 www.hanachiru-blog.comこの深さ優先探索と兄弟のようなアルゴリズムである幅優先探索を実装していきたいと思います。 はじめに 実装方針 コード 使い方 さいごに 実装方針 実は深さ優先探索ではスタックを…

【C#】深さ優先探索(DFS)を実装してみる

はじめに 今回は深さ優先探索を実装してみようという記事になります!深さ優先探索とはこちら。 木やグラフを探索するためのアルゴリズムである。アルゴリズムは根から(グラフの場合はどのノードを根にするか決定する)始まり、バックトラックするまで可能な…

【C#】最大容量付きのLinkedListを実装してみる

はじめに 今回は最大容量付きのLinkedListを実装してみる記事になります!まずLinkedListとはListとは違いインデックスによる要素の指定はできませんが、挿入と削除の操作を高速(計算量)で行うことができるコレクションです。イメージとしてはキューに近い?…

【C#】最大容量付きのキューを実装してみる

はじめに 今回は最大容量付きのキューを実装してみようという記事になります!C#には標準でキューが扱え、初期容量を設定するコンストラクターも存在します。 docs.microsoft.comところが最初に設定した容量を超えると自動で容量を増やしてくれるという親切…

【Unity】Unityでもゼロから機械学習を作る【ロジスティック回帰モデル(2値分類)】

はじめに 今回はUnityでロジスティック回帰を使った2値分類を実装してみたいと思います。前回や前々回で実装したものは出力値が数値でしたが、今回は分類(離散値)をします。 【Unity】Unityでもゼロから機械学習を作る【単回帰モデル】 - はなちるのマイノー…

0,1,2,…,Nの中からk個選び足し合わせてできる整数は何通りか

はじめに 最近AtCorderなるものを始めてみたのですが、そこで出題されていた以下の箇所がよく分かりませんでした。 D - Sum of Large Numbers 0,1,2,…,Nの中からk個選び足し合わせてできる整数は何通りか ずっとコンビネーションnCrをうまく使えば解けると思…

【C#】Union-FInd木を実装してみる

はじめに 今回はUnion-FInd木を実装してみようという記事になります!これが使える場面は以下のようなとき。 データの集合を素集合(互いに素である集合)に分割してデータを保持したいとき 例えばきのこの山とたけのこの里の2つの派閥があり、きのこの山とた…

【C#】動的計画法(DP)を実装してみる

はじめに 今回は動的計画法(DP)を実装してみようという記事になります!動的計画法とはなんだ一体というと、こんな感じ。 対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ。 動的計画法 - Wikip…