はなちるのマイノート

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

アルゴリズム

【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#】選択ソートを実装してみる

はじめに 今回は選択ソートを実装していきたいと思います。 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…

【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)とすると…