赤黒木の本質 - Qiita
この記事はデータ構造とアルゴリズム Advent Calendar 2019 16日目の記事です。 15日目は@minaminaoさんによる「すごいTrie」です。 17日目は@takilogさんによる「Fréchet距離の計算アルゴリズム」です。 はじめに この記事では有名なデータ構造である赤黒木がなぜあのようなトリッキーな定義になっているのかその本質について解説します。 赤黒木の定義を見てトリッキーと思うかどうかは個人差あるかと思いますが、少なくとも僕が初めて赤黒木を学んだ時はなぜこのような定義になっているのか、そしてどうやって思いついたのか見当がつかずとても不思議に感じました。 しかし、その後赤黒木の成り立ちやその基になったデータ構造について知ると、トリッキーに見えた定義がとても自然であることを実感しました。 おそらく知っている人は当たり前に知っている内容だとは思いますが、知らない人
ハルヒ問題（最小超置換問題）の紹介 - Qiita
はじめに 皆さんこんにちは、「データ構造とアルゴリズムAdvent Calendar」の作成者、文字列大好き文字列初心者の@kgotoです。 一昨年と去年は「文字列アルゴリズムAdvent Calendar」を作り、去年は念願の完走をしました。有り難いことに反響も大きかったです！ 今年は「データ構造とアルゴリズム」と対象を広げて、一瞬でカレンダーの枠が埋まるのでは！？とドキドキしていたのですが、蓋を開けてみるとなんとまだ11日も空きがあります！！ ちょっと寂しいですね。。。 もちろん無理に参加してくれとは言いませんが、この記事を読んでちょっとでも面白いと思った方は絶対参加お願いします！ さて、前置きはこれくらいにして本題に入っていきましょう。 データ構造とアルゴリズムAdvent Calendar第1日目では先々月にニュースサイトGigazineにも掲載されて話題になった「ハルヒ問題」を紹
初期化配列の実装 - Qiita
こんにちは、最近ハマっている初期化配列について紹介したいと思います。 はじめに 皆さんプログラミングをする時に配列を使ってますか？使ってない人はほとんどいないのではないでしょうか？ 長さNの固定長配列AはN個の要素を格納でき、かつ任意の位置に保存された要素A[i]を最悪定数時間（以下、定数時間）で読み書き可能な最も基本的なデータ構造の一つです。配列の様々な操作の中で読み書きについで頻出する重要な操作が、配列の全ての要素を指定した値に書き換える初期化操作です。配列の初期化は配列長に対して線形な時間がかかるため、配列長が長い場合や、初期化が頻出する処理では配列の初期化操作が大きなボトルネックとなります。この問題を解決するデータ構造が初期化配列です。本記事ではシンプルな初期化配列の実装法、folkloreアルゴリズムを紹介したいと思います。 初期化配列とは通常の読み書きに加え、配列の全ての要素を
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
