C#
はじめに 今回はトポロジカルソートを実装していきたいと思います。ja.wikipedia.orgトポロジカルソートとは有向非巡回グラフ(DAG)においてどのノードもその出力辺の先のノードより前にくるように並べるアルゴリズムのことです。 トポロジカルソート アルゴ…
はじめに 今回扱ってみる問題はこんな感じ。 n個の配列Aと整数kが入力として与えられたとき，Aの2つの要素の和がkとなる組み合わせを列挙せよ 例. 入力：A = {1, 6, 4, 5, 3}，k = 7 出力：(6, 1), (3, 4) 解き方 まずは2重ループを使った全探索の方法が思い…
はじめに 今回は選択ソートを実装していきたいと思います。 ja.wikipedia.orgこのアルゴリズムは実装は簡単だけど性能がいいといったソートアルゴリズムで、バブルソートと似た系統のものです。早速みていきましょう。 はじめに 選択ソート 実装 テスト 考察…
はじめに 今回はマージソートを実装してみようという記事になります！ ja.wikipedia.org前置きはなしに本題をみていきたいと思います。 はじめに マージソート 実装 使い方 考察 マージソート 英語ですが、この動画がすごく分かりやすく説明されていたのでオ…
はじめに 少し前に挿入ソートを実装してみました。 https://www.hanachiru-blog.com/entry/2020/07/30/180000www.hanachiru-blog.comこの挿入ソートをより高速化するために生まれたのが今回紹介するシェルソートになります。 ja.wikipedia.org早速みていきま…
はじめに 今回はヒープソートを実装してみようという記事になります！ヒープソートというのは名前の通りヒープというデータ構造を用いたソートアルゴリズムであり，安定して高速に処理ができる(安定ソートという意味ではない)優秀なソートだと知られています…
はじめに 前回はバケットソートを紹介しましたが、今回はその改良版とも言われる基数ソートについて実装していきたいと思います。 ja.wikipedia.orgバケットソートではバケットの数が膨大になってしまうのはNGという制約がありました。計算量と引き換えにそ…
はじめに 前回は挿入ソートを紹介しましたが、今回はバケットソートを実装していきたいと思います。バケットソートはソートアルゴリズムでよくある要素を交換する手法を取らない面白いアルゴリズムです。 ja.wikipedia.orgまた以下の制約を満たさなければ動…
はじめに 今回は挿入ソートを実装してみようという記事になります！挿入ソートはソートのアルゴリズムの一種で、性能はあまり良くないですが実装が簡単なアルゴリズムだと知られています。 ja.wikipedia.orgバブルソートと似た系統だと表現した方が分かりや…
はじめに 今回はBoyer-Moore法(BM法)を自前で実装してみようという記事になります。BM法とは文字列検索アルゴリズムの一つで，他の文字列検索アルゴリズムと比べて優秀な部類と言われるアルゴリズムです。(最悪計算量は)C#をそれなりに触ったことのあるかた…
はじめに 今回は部分和問題(subset-sum problem)を解いてみたいと思います。最初にネタバレをしてしまいますが、具体的にはbit全探索を用いた方法と動的計画法を用いた2種類を紹介していきます。アルゴリズムの教科書なんかでもよく出てくる問題なので、マス…
はじめに 今回はxor(排他的論理和)についてみていきます。xorを使った暗号化はかなり簡単な分類の暗号化アルゴリズムとして知られているので、すぐに習得できると思います。またその応用としてUnityのデータのセーブ・ロードのために用いられるPlayerPrefsを…
はじめに 今回はセグメント木を実装してみようという記事になります！セグメント木は主に区間上の値の更新と任意の区間内の最小値などの取得を高速化できます。構造としては完全二分木を用いていて、初期化に，更新・取得は共にで動作します。 en.wikipedia.…
はじめに 今回はイミュータブル(Immutable)クラスについて書いていきたいと思います。ネットサーフィンをしていたところ以下の記事を見つけました。 www.c-sharpcorner.com正直私自身理解が曖昧だったのですが、これを機に少し勉強してみたいと思いました。…
はじめに 今回はスレッドセーフなシングルトンを実装してみる記事になります。Unityなんかでは頻繁に使われているシングルトンパターンですが、マルチスレッドで処理をする場合には落とし穴があったりします。どういった落とし穴があるのかということから、…
はじめに もしUnityを扱ったことのある方は以下のようなコードをみたことはないでしょうか。 #if UNITY_EDITOR Debug.Log("Unity Editor"); #endif #if ~ #endifの中にあるDebug.LogはUnityのエディタのときのみコンパイル，実行されます。これらは別にUnity…
はじめに 今回はナップザック問題を解いてみようという記事になります。 ja.wikipedia.orgナップザック問題は動的計画法の典型例なので、アルゴリズムの勉強にも良い問題だと思います。早速みていきましょう。 はじめに ナップザック問題とは 問題 方針 実装…
はじめに 以前までVisual Studioでコードを実行すると外部のターミナルが立ち上がっていたのですが、アップデートでVisual Studio内部で動作するようになっていました。最初は喜ばしいことかなとも思ったのですが、以下の点が気に入らなかったので元に戻そう…
はじめに 非同期処理やマルチスレッド処理をするときにTaskを使ったりすると思います。ただUnityは基本全てメインスレッドで動くので、誤ってメインスレッドを止めてしまった場合他の処理が止まってしまう危険もあります。←正しくTaskを使えた場合 メインス…
はじめに C#のプログラミングを初めて3年ぐらい経ちますが、いまだに上手に例外処理を使えていない有様だったのでこれを機にまとめてみようと思いました。基本的な文法からExceptionの自作派生クラスを作るまでを一通りやっていきます。 はじめに 基本文法 …
はじめに 今回は木の直径を求めてみようという記事になります！あまり用いる機会はないと思いますが、簡単な頭の体操のように捉えてくれれば嬉しいです。早速みていきましょう。 はじめに 木の直径とは？ 実装方針 コード さいごに 木の直径とは？ 木の直径…
はじめに 前回深さ優先探索の実装をしてみました。 www.hanachiru-blog.comこの深さ優先探索と兄弟のようなアルゴリズムである幅優先探索を実装していきたいと思います。 はじめに 実装方針 コード 使い方 さいごに 実装方針 実は深さ優先探索ではスタックを…
はじめに 今回は深さ優先探索を実装してみようという記事になります！深さ優先探索とはこちら。 木やグラフを探索するためのアルゴリズムである。アルゴリズムは根から(グラフの場合はどのノードを根にするか決定する)始まり、バックトラックするまで可能な…
はじめに 先日UniRxに関する非常に分かりやすい記事を見つけました。qiita.comいままでUniRxの中身をブラックボックスと捉えて表面上の使い方だけを学んでいたのですが、しっかりと使うためにはやはり内部構造を知るのは欠かせません。そこでこちらの記事で…
はじめに 今回は最大容量付きのLinkedListを実装してみる記事になります！まずLinkedListとはListとは違いインデックスによる要素の指定はできませんが、挿入と削除の操作を高速(計算量)で行うことができるコレクションです。イメージとしてはキューに近い？…
はじめに 今回は最大容量付きのキューを実装してみようという記事になります！C#には標準でキューが扱え、初期容量を設定するコンストラクターも存在します。 docs.microsoft.comところが最初に設定した容量を超えると自動で容量を増やしてくれるという親切…
はじめに 今回はUnityでロジスティック回帰を使った2値分類を実装してみたいと思います。前回や前々回で実装したものは出力値が数値でしたが、今回は分類(離散値)をします。 【Unity】Unityでもゼロから機械学習を作る【単回帰モデル】 - はなちるのマイノー…
はじめに 今回はUnion-FInd木を実装してみようという記事になります！これが使える場面は以下のようなとき。 データの集合を素集合(互いに素である集合)に分割してデータを保持したいとき 例えばきのこの山とたけのこの里の２つの派閥があり、きのこの山とた…
はじめに 昨日に引き続きネタ関連の記事です。どんなものを作ったのかというとはUSBを挿しただけで感染するウイルスというなかなかインパクトのありそうなものです。ただ最初に言っておくと結構前のWindowsUpdateにより基本はできないように変更されています…
はじめに 今回はシーケンスが等しいかどうかを同じ要素なら等しくする記事になります！突然ですが、以下のコードをみてみてください。 static void Main(string[] args) { var a = Enumerable.Range(1, 5); var b = Enumerable.Range(1, 5); Console.WriteLi…
