はなちるのマイノート

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

アルゴリズム

【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…

【C#】順列全探索を実装してみる

はじめに 今回は順列全探索を実装してみる記事になります! はじめに 順列全探索とは コード 使い方 順列全探索とは 順列全探索とは通りの順列を生成して探索をすることです。例えば{1, 2, 3}の順列の組み合わせは以下の通りです。 1 2 3 1 3 2 2 1 3 2 3 1 …

【C#】FizzBuzz問題のイカした解答を考えてみる

はじめに 今回はFizzBuzz問題についての記事になります!そもそもFizzBuzz問題とはどんなものか一応説明しておくと、こんな感じ。 プレイヤーは円状に座る。最初のプレイヤーは「1」と数字を発言する。次のプレイヤーは直前のプレイヤーの次の数字を発言して…

【C#】約数を列挙するプログラムを実装してみる

はじめに 今回は約数を列挙するプログラムを実装してみる記事になります!一応約数とはなにかというとこんな感じ。 数 a ≠ 0 が N の約数であるとは、「ある整数 b をとると N = ab が成立することである」であるが、条件「a ≠ 0」を外すこともある。 約数 -…

【C#】ダイクストラ法を実装してみる

はじめに 今回はダイクストラ法を実装してみようという記事になります!ダイクストラ法を用いることで迷路の最短距離を求めたりすることができます。カーナビの経路探索や鉄道の経路案内なんかにも使われている例があるそうです。では早速みていきましょう。…

【C#】累積和を実装してみる

はじめに 今回は累積和を実装してみようという記事になります!そもそも累積和をどこに使う必要があるのかというとこんな時です。 適切な前処理をしておくことで、配列上の区間の総和を求めるクエリを爆速で処理できるようになる手法 累積和を何も考えずに書…

【C#】優先度付きキュー(優先度付き待ち行列,priority queue)を実装してみる

はじめに 今回は優先度付きキューを実装してみようとという記事になります!優先度付きキューを用いることで迷路での最短距離を求めるダイクストラ法などを実装することができます。他の言語だと実装されているものもあるらしいのですが、C#にはないみたいな…

【C#】bit全探索を行う

はじめに 今回はbit全探索を実装していこうと思います。bit全探索とはN 個のものから、選ぶ・選ばない(true,false)を全列挙して調べ上げる手法のことです。例えば3個の番号がついたボールがあり、選んだときは1(true),選ばなかったときを0(false)とすると…

【C#】回分かどうか調べる

はじめに 今回は回分かどうか調べてみようという記事になります!回分というのは「しんぶんし」のように上から読んでも下から読んでも同じになる文句のことですね。これを実装してみましょう。 はじめに やり方 さいごに やり方 public static bool IsPalind…

【C#】二分探索(バイナリサーチ)をする

はじめに 今回は二分探索をしてみようという記事になります! はじめに 二分探索とは コード さいごに 二分探索とは 二分探索(バイナリサーチ)とはソート済みの配列に対する探索アルゴリズムの一つです。 ソート済みのリストや配列に入ったデータ(同一の値…

【C#】素数判定のプログラムを書いてみる

はじめに 今回は素数判定のプログラムを書いてみようという記事になります!素数とは一とその数自身との外には約数がない1より大きい正の整数のことです。例えば7は素数ですが、8は素数ではありません。では早速みていきましょう。 はじめに 素数判定 改良し…

【C#】順列・組み合わせの数を求める

はじめに 今回は順列・組み合わせの数を求めてみようという記事になります。ただ列挙するのではなく数を求めることに注意してください。では早速みていきましょう。 はじめに 順列 組み合わせ さいごに 順列 順列とは「異なるn個の中から k 個を順番をつけ…

【C#】クイックソートを実装してみる

はじめに 今回はクイックソートについて取り上げていきたいと思います。クイックソートは最悪計算時間は𝑂(𝑛2)ですが、平均計算時間が𝑂(𝑛log𝑛)である比較的高速なソートです。実際の処理の流れをWikipediaから引っ張ってきました。 適当な数(ピボット)を選…

【C#】最大公約数・最小公倍数を求める

はじめに 今回は二つの整数の最大公約数を求めるプログラムについてやっていきたいと思います。最大公約数とは共通の約数のうち最大のもののことを指します。例えば12と18の最大公約数は6となります。早速やっていきましょう。 はじめに 求め方 プログラム …