アルゴリズム

1/3ページ
C#

[C#] ランレングス圧縮(連長圧縮)を実装する方法

C# でランレングス圧縮 連長圧縮 – Wikipedia C# で ランレングス圧縮 を実装してみます。ランレングス圧縮についてはWkipediaを引用すると以下のようなものです。 連長圧縮は、データ圧縮アルゴリズムの一つで、可逆圧縮に分類される。ランレングス圧縮、RLE (Run Length Encoding) とも呼ばれる。 連長圧縮では、ある連続したデータを、そのデータ一つ分 […]

[C#] Union-Find木を実装する方法

Union-Find木 とは 素集合データ構造は、データの集合を素集合(互いにオーバーラップしない集合)に分割して保持するデータ構造。このデータ構造に対する以下の2つの便利な操作をUnion-Findアルゴリズムと呼ぶ。 Find: 特定の要素がどの集合に属しているかを求める。2つの要素が同じ集合に属しているかの判定にも使われる。 Union: 2つの集合を1つに統合する。 これら2つの操作をサポ […]

[C#] lower_bound, upper_bound を実装する方法(二分探索)

lower_bound と upper_bound lower_bound と upper_bound という2つの関数があります。これは C++ のSTLライブラリにある関数です。この関数を C# で実装していきます。 lower_bound – cpprefjp C++日本語リファレンス upper_bound – cpprefjp C++日本語リファレンス これらの関 […]

[C#][DP] A – コンテスト(Typical DP Contest) を解く [動的計画法]

C# で動的計画法(DP)を解きたい 最近競技プログラミングをやりだして、動的計画法(DP)というアルゴリズムを知りました。練習でいろいろな問題を解いていこうと思います。そして勉強がてら解けた問題の内容を書いていきます。 Typical DP Contest – Typical DP Contest | AtCoder DPの問題に特化した過去のコンテストがあるのでこれを順に C# で […]

C#

[C#] 連結リストを自前で実装する方法

連結リストを自前で実装する 連結リストとは 連結リスト – Wikipedia 連結リスト (Linked List) とは基本的なデータ構造の1つです。配列のようなインデックスで順序が決まるのではなく、各オブジェクトが持つポインタによって順序を決めるデータ構造です。 連結リストにはいくつかの種類があります。一方向と双方向、循環と非循環などです。今回実装していくのは 双方向連結リスト […]

C#

[C#] キューとスタックを自前で実装する方法

Stack, Queue を自前で実装する C# の場合、データ構造の Stack と Queue は標準ライブラリで提供されますが、自前で実装して理解を深めようと思います。 順番に見ていきます。 Stack (スタック) スタック – Wikipedia Stack は先入れ後出し(FILO)を実現するためのデータ構造です。 Stack は、データを入れる Push と積まれたデータ […]

C#

[C#][VB] 挿入ソートを実装する

挿入ソート 挿入ソートを C#, VB.NET で実装してみます。 挿入ソートは、時間計算量 O(n^2) でバブルソートや選択ソートと同じく高速なソートアルゴリズムとは言えません。ただし、挿入ソートについて言えばある面で有用なソートアルゴリズムです。 挿入ソートは要素数の少ないデータに対して、効率よくソートするアルゴリズムです。 クイックソートなど高速なソートアルゴリズムについては、処理のオーバ […]

Rust ソートアルゴリズム実装(バブルソート、選択ソート、挿入ソート)

Rust を使ってソートアルゴリズムを実装してみる Rust を使ってソートアルゴリズムを実装してみます。バブルソート、洗濯ソート、挿入ソートをそれぞれ実装します。 Rust はクセが強いので、結構苦労しましたが以下を学びました。 配列要素の交換は swap() を使う Clone を実装する型は clone() を使える Copy を実装すると型は配列の要素をそのまま交換できる 10..1 みた […]

C#

[C#] [VB] ブロックソートを実装する方法

ブロックソートとは ブロックソート – Wikipedia ブロックソートとはデータの可逆変換アルゴリズムの一種です。ソートとついていますが、データのソートを効率よくするため ソートアルゴリズムではありません 。また、データの圧縮アルゴリズムでもありません。Wikipediaには次のようにあります。 ブロックソート、ブロックソーティング、Burrows-Wheeler変換 (Burro […]

C#

[C#] Base64のアルゴリズムをを実装する

Base64 のエンコード・デコード Base64 というエンコード方式をC#で実装します。Base64は、64種類の印字可能な英数字のみを用いてエンコードします。 Quoted-printable と同じくメール送信時のエンコードとして用いられるほか、Basic認証や画像ファイルの埋め込みなどにも用いられています。 ここでは、Base64のエンコード・デコード処理を独自に実装していきます。 なお […]

1 3