ホーム

アルゴリズムとデータ構造 - ハッシュマップ

アルゴリズムとデータ構造

概要 アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 ハッシュマップ ハッシュ値を添え字とした配列 ハッシュの衝突処理 開番地法 衝突が生じた際に、ハッシュ関数とは別の関数を使って別の番地を求める方法。 連鎖法 衝突が生じても新しい番地を求めずに、衝突した番地に衝突したキー同...

ハッシュマップ

隣接リストと隣接行列

アルゴリズムとデータ構造

概要 グラフを表現するためのデータ構造である隣接リストと隣接リストについてまとめる。 隣接リストや隣接行列は有向グラフでも無向グラフでも利用できる。 隣接リスト(Adjacency List) 各頂点(ノード)ごとに隣接する頂点をリストとして持つデータ構造。 // 無向グラフの例 A---B | / | | / | C---D // 隣接リストで表現すると、次のような形になる A: [B...

グラフ 隣接行列 隣接リスト

スタックとキューの実装

アルゴリズムとデータ構造

Goでスタックとキューをそれぞれ実装してみた。 スライスを使ったパターンと連結リストを使ったパターンをそれぞれ実装している。 個人的にはスライスを使ったパターンの方が実装は楽かなと思う。 スタックのpush、pop、キューのenqueue、dequeueの時間計算量はそれぞれO(1)で実装できるが、一部サボってO(N)になってしまっているものがある。 スタック ソースコード:stack 連結リスト...

スタック キュー

連結リストのランナーテクニック

アルゴリズムとデータ構造

連結リストの走査で役立つランナーテクニックについてまとめる。 世界で闘うプログラミング力を鍛える本 ~コーディング面接189問とその解法で紹介されていて初めて知った。 ランナーテクニックとは 連結リストの先頭から走査していくポインタと、そのポインタより先から走査していくポインタの2種類を用意して、同時に走査していく方法。 これが何に役立つかというと、例えば次のような例題を解くのに役立つ。 例題 単...

アルゴリズム データ構造 ランナーテクニック Tips

再帰処理の苦手なところ

アプリケーション

再帰処理はプログラマーの嗜み!エレガントにかけて当たり前!・・・と自信を持って言いたいところだが、自分は正直なところ苦手である。 日頃再帰処理を書く機会といえばコーディングクイズくらいで実際のところあまり書く機会がない.. 再帰処理はケースによってはメモ化や末尾最適化までエレガントにやらないと計算量が大きくなったり、メモリを食うだけのコードになってしまうが、アルゴリズムによってはシンプルなコードに...

再帰

アルゴリズムとデータ構造の基本の復習

アルゴリズムとデータ構造

概要 コーディングクイズを解く日課を再開するに当たって、リハビリを兼ねてアルゴリズムとデータ構造の基本について復習。 配列 連続した配置でメモリを確保する 単一のデータ型 サイズは一般的には固定だが、言語によっては動的(可変長配列) サブアレイ 配列内から連続した形で取り出される配列 [1, 2, 3, 4, 5] →[2, 3, 4] サブシーケンス 要素順を変更せずに、一部の要素...

アルゴリズム データ構造

プログラマ脳

アプリケーション

コードを読む能力も書く能力も高い人の頭の中はどうなっているのか?自分とは何が違うのか?ということはエンジニアであれば誰しも考えたことがあると思う。(たぶん) プログラマ脳という本は、認知科学のアプローチを用いて、コーディングという創造的なプロセスを科学していく本で、脳が筋肉でできている人が読むべき内容だった。 脳筋の下りは半分冗談として、最近コーディングクイズの日課を再開したのだが、データ構造やア...

認知科学 コードリーディング

カウントソートの実装

アルゴリズムとデータ構造

カウントソートとは ソートアルゴリズムの中でも比較を使わずにソートする変わった?アルゴリズム。 比較せずに要素をカウントすることでソートができる。 カウントしてソートすることができるというのは不思議!と思ったので調べてみた。 前提 累積和について知っておく必要がある。 cf. qiita.com - 累積和とは(超初心者用) 実装 ソースコードは以下。 count_sort package mai...

カウントソート

バックトラッキングの実装

アルゴリズムとデータ構造

バックトラッキングとは 指定された制約を満たすような組み合わせを探索するアルゴリズム。  重複しない組み合わせ(nCr)を全て探索するようなときに使える。 実装 ソースコードは以下。 backtrack 与えられた配列からN個の重複しないサブシーケンスを取得する処理。 以下は4C3の例。 package main import "fmt" func backtrack(rs...

バックトラック