二分木 | Programming Place Plus アルゴリズムとデータ構造編【データ構造】 第７章
トップページ – アルゴリズムとデータ構造編 この章の概要 この章の概要です。 木構造 二分木 再帰的な性質 走査 まとめ 練習問題 参考リンク 更新履歴 木構造 この章では、木構造（ツリー）というデータ構造を紹介します。連結リスト（第３章）と同様に、非常に重要なデータ構造です。 まず、木構造の概念図を見てください。 木構造 この概念図において、○ の部分を節（ノード）と呼びます。各節が線で結ばれていることが分かると思いますが、この線の部分を枝と呼びます。この概念図で、上下を逆さまにしてみれば、木のような形をしていることが分かると思います。これが木構造と呼ばれる理由です。 ここで、ある節から見て、その１つ下にある節のことを子と呼び、逆に１つ上の節を親と呼びます。 この辺りの用語は、家系図を見るように考えればいいです。兄弟、従弟、先祖、子孫などの用語もあります。ちなみに「兄弟」は broth
8時間を0.01秒に短縮 「アルゴリズムの素晴らしさが2分で分かる動画」が今すぐ勉強したくなる分かりやすさ
※本記事はアフィリエイトプログラムによる収益を得ています アルゴリズムの素晴らしさを2分で解説した動画が、とても分かりやすくためになると人気です。なるほど、これがアルゴリズムと仕組みかぁ。 最短経路をアルゴリズムで算出しよう この動画では、迷路を最短手数で解くアルゴリズムについて解説。迷路はマス目状になっており、全部で8900億個の手順が存在するものとなっています。全ての経路を試せば最短手順を導き出せますが、普通のコンピュータでは約8時間かかってしまう計算になります。 全パターンの網羅は非常に時間がかかります そこで計算の手順を変更。スタートに0を書き、その隣1を、また隣に2……と繰り返していきます。こうして進めていくと最終的にゴールは34となり、この34が最短手数となることが分かります。今度はゴールから34，33，32とたどっていけば、最終手数で進む経路の1つが導き出せました。 数字を振
オセロAI世界1位になってオセロAIをｶﾝｾﾞﾝﾆﾘｶｲｼﾀ話 - Qiita
オセロAIを作り始めた日のこと あれは2021年4月のこと、今思い返せば偶然が重なって起きた出来事でした。 第一の偶然は、ゲームAI(ゲームを自動プレイするAI)世界4連覇の方になぜかゲームAIの初歩的な話を30分程度教わっていたことです。 第二の偶然は、Twitterの知り合いが「オセロソフトRTA」なる競技をやっているのを目にしたことです。なんじゃそりゃ、と思った私はすぐに、その競技が 「オセロで遊ぶプラットフォームをどれだけ早く作るか」を競うものだとわかりました。 面白い、やってみよう。 YouTubeでライブ配信しながら、私はオセロソフトRTAをやってみました。その時のライブはこちら。3時間で完成できれば良いと思っていたのですが、思ったよりも早く終わってしまいました。 オセロAIでも作るか。 こうして私のオセロAI制作が開始しました。 何をしたら良いかわからなかった オセロAIを作
最適輸送の解き方
最適輸送問題（Wasserstein 距離）を解く方法についてのさまざまなアプローチ・アルゴリズムを紹介します。 線形計画を使った定式化の基礎からはじめて、以下の五つのアルゴリズムを紹介します。 1. ネットワークシンプレックス法 2. ハンガリアン法 3. Sinkhorn アルゴリズム 4. ニューラルネットワークによる推定 5. スライス法 このスライドは第三回 0x-seminar https://sites.google.com/view/uda-0x-seminar/home/0x03 で使用したものです。自己完結するよう心がけたのでセミナーに参加していない人にも役立つスライドになっています。 『最適輸送の理論とアルゴリズム』好評発売中！ https://www.amazon.co.jp/dp/4065305144 Speakerdeck にもアップロードしました: https
シンプルかつ高速な文字列照合アルゴリズムを紹介します - エムスリーテックブログ
こんにちは！ エンジニアリンググループ マルチデバイスチーム 新卒1年目の小林です。 エムスリーでは、2週間に1度、Tech Talkという社内LT会（現在はリモートで）が開催されています。これは、とある回の発表テーマリストです。 Tech Talkのとある回の発表テーマリスト このように、最近エムスリーでは文字列が流行っている（？）ようなので、その勢いに乗って私も文字列照合アルゴリズムについて書きたいと思います！（業務とは全然関係ない話です） Knuth-Morris-PrattやBoyer-Mooreアルゴリズムは解説記事がたくさん出ていると思うので、この記事ではシンプルかつ高速なQuick-SearchとQuite-Naiveアルゴリズムについて説明し、速度比較を行った結果についてご紹介します。 文字列照合アルゴリズムとは テキストとパターンという文字列が与えられたときに、中に出現す
競技プログラミングで解法を思いつくための典型的な考え方 | アルゴリズムロジック
競技プログラミングの問題を解くためには２つのステップがあります。 問題で要求されていることを言い換える知っているアルゴリズムやデータ構造を組み合わせて解く 必要な（知っておくべき）アルゴリズムやデータ構造は色々なところで学ぶことができます。 しかし、「問題の言い換え」や「アルゴリズムを思いつく」というのは、非常に様々なバリエーションがあり、問題をたくさん解かないとなかなか身につきません。 そこで、この記事は以下のことを言語化し、練習のための例題を提示することを目標とします。 問われていることを、計算しやすい同値なことに置き換える方法アルゴリズムを思いつくための考え方競技プログラミングで「典型的」と思われる考え方 ※一部問題のネタバレを含むので注意 ※良く用いられるアルゴリズムやデータ構造については競技プログラミングでの典型アルゴリズムとデータ構造 を参考にして下さい。 入力の大きさ(制約)
アルゴリズムと数学的思考力 - 怠惰を求めて勤勉に行き着く
厳しい。年始早々厳しさを感じている。自分のプログラミング力にだ。伸び悩んでいる。 端的に言って、数学力のなさが自分のプログラミング能力に制限をかけている。例えばこの問題。 560. Subarray Sum Equals K 入力として与えられる配列 nums のうち、合計が k となる部分配列の個数を数え上げよ。どうも有名な問題らしいが… まず大前提として、部分配列なので i, j の2重ループで始点・終点を定めて sum(nums[i, j]) = k になるものを数え上げれば必ず答えが得られる。最悪計算量は O(N^3) ただし i < nums.length < 20000 という制約があるので N^3 では遅すぎるから何か考えてくださいというのがスタート地点。 ここで、結果の変わらない累積和を何度も求めているので nums[i, j] = k を求めたい場合、 nums[0, j
RDBMSで使われるB木を学ぼう （1/3）－ ＠IT
第5回 RDBMSで使われるB木を学ぼう はやしつとむ アナハイムテクノロジー株式会社 2009/6/22 オブジェクト指向によって、アルゴリズムは隠ぺいされていることが多くなった。しかし、「用意されていない処理」が求められたときに対応できるだろうか（編集部） 第3回「AVL木で木構造を学ぼう」、第4回「もっとAVL木で木構造を学ぼう」と2回連続でAVL木について解説しました。 今回はAの後だからBというわけではありませんが、B木（B-Tree）を取り上げます。 B木の変種であるB+木やB*木は、OracleやPostgreSQL、Firebirdなどのリレーショナルデータベースでインデックスとして利用されている、メジャーな木構造です。 筆者はDelphi 2009でサンプルプログラムを作成していますが、Delphiをお持ちでない方は下記のURLからTurboDelphiをダウンロードして
深さ優先探索 - Algoful
深さ優先探索(Depth First Search)とは 深さ優先探索とは、木構造やグラフの探索を行うためのアルゴリズムです。始点となるノードから目的のノードが見つかるか子のないノードにたどり着くまで探索を繰り返し、そのあとは探索の終わってないノードまで戻って再度探索を繰り返します。 探索するのノードは スタック(FILO) を使って管理することになります。あるいは再帰的に呼び出す方法を用います。 アルゴリズム 始点のノードを探索待ちスタックに追加する。 探索待ちスタックにノードがあれば取り出す。なければ全ノード探索完了。 取り出したノードが目的ノードであれば探索完了。 取り出したノードに隣接するノードの内、未探索のノードを探索待ちスタックに追加する。 2. の処理にもどる。 先入れ後出しのスタックに探索待ちのノードを格納することで、始点から末端のノードまでの探索が一直線に行われることにな
リレーショナルデータベースの仕組み (1/3) | POSTD
リレーショナルデータベースが話題に挙がるとき、私は何かが足りないと思わずにはいられません。データベースはあらゆるところで使われており、その種類も、小規模で便利なSQLiteからパワフルなTeradataまで様々です。しかし、それがどういう仕組みで機能しているかを説明したものとなると、その数はごくわずかではないでしょうか。例えば「リレーショナルデータベース 仕組み」などで検索してみてください。ヒット数の少なさを実感できると思います。さらにそれらの記事は短いものがほとんどです。逆に、近年流行している技術（ビッグデータ、NoSQL、JavaScriptなど）を検索した場合、それらの機能を詳しく説明した記事はたくさん見つかると思います。 リレーショナルデータベースは、もはや大学の授業や研究論文、専門書などでしか扱われないような古くて退屈な技術なのでしょうか？ 私は開発者として、理解していないものを
『みんなのデータ構造』発売および予約開始のお知らせ – 技術書出版と販売のラムダノート
ご来店ありがとうございます。 本日より、新刊『みんなのデータ構造』の発売を開始しました。紙書籍の発送は7月25日前後を予定しています。電子書籍は購入後すぐにお読みいただけます。 『みんなのデータ構造』は、Pat Morin氏による “Open Data Structures” を翻訳して書籍として出版するものです。Pat Morin氏による原文は、クリエイティブコモンズ継承ライセンス（CC BY）で公開されており、誰でも自由に教材として活用できるだけでなく、内容に手を入れて別のライセンスで再配布したり、販売したりできるようにされています。堀江氏、陣内氏、田中氏による翻訳と、ラムダノート株式会社による編集も、すべてCC BYで公開しており、同様に自由に利用していただくことが可能です。 書籍版『みんなのデータ構造』（紙書籍および電子書籍）につきましては、クリエイティブコモンズライセンスではなく
gonp〜Goによるdiffのアルゴリズム実装〜 - Qiita
この記事は、2015年のGo Advent Calendarの25日目の記事です。 Go Advent Calendarのその2とその3ができる前、最終日だけ空いてて滑り込みで登録したのはいいけど、なんかネタないかなーと思いつつ、自分のgithubリポジトリを漁っていたらdiffのアルゴリズムをGoで実装したやつが出てきたので紹介してみます。 gonpはGoによるdiffのアルゴリズム実装です。元々は昔々C++で書いたdtlというdiffライブラリの簡易移植で、diffを取るのに必要な以下の要素を求めることができます。 編集距離（Edit Distance） LCS（Longest Common Subsequence） SES（Shortest Edit Script） diffのアルゴリズムにはさまざまな種類があり、中でもdiffに限らず様々な用途に応用可能な動的計画法が有名です。ただ
通勤・通学中に理解する深さ優先探索と幅優先探索【アルゴリズム】 - あのねノート。
2014-01-31 通勤・通学中に理解する深さ優先探索と幅優先探索【アルゴリズム】 まとめ やり方 まえおき まえおき は みつかりませんでした。 深さ優先探索の例 例から入る 0という名前の点から探索を始める 0につながってるのは1か2か3だけど、テキトーに3を選ぶ 3につながってるのは0か4か5だけど、0は訪問済みなので選択肢は4か5 テキトーに4を選ぶ 4につながってるのはは2か6だけど(3は訪問済み)、テキトーに2を選ぶ 2につながってるのは0と4だけど、どっちも訪問済み 直前に来た4に戻って行けるとこを探す 4につながってるのは2と3と6だけどまだ行ってない6を選ぶ 6から行けるとこはどこもない(4は訪問済み) 戻って4から行けるところを探すけどどこも訪問済み 更に戻って3から行けるところを探す 5を選ぶ(0と4は訪問済み) 5から行けるとこはどこもない(3は訪問済み) 戻って
Introduction To TopCoder, 今日からはじめるTopCoder - フリーフォーム フリークアウト
移転しました http://please-sleep.cou929.nu/20091005.html
BW変換（Burrows Wheeler Transform）を書いた - About connecting the dots.
「高速文字列解析の世界」を読んでて，BW変換のところがよくわからなかったので，実際に書いてみました． 高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学) 作者: 岡野原大輔出版社/メーカー: 岩波書店発売日: 2012/12/27メディア: 単行本購入: 15人 クリック: 324回この商品を含むブログ (5件) を見る 概要 BW変換ってなんぞやを一言でいうと，「変換すると，似たような記号がたくさん並ぶようになる，文字列の可逆変換」です．具体例をみせると，以下はWikipediaのBW変換の最初のパラグラフを，実際にBW変換してみた結果です． 元の文章*1 Compression techniques work by finding repeated patterns in the data and encoding the duplications
マイコンのテクニック アルゴリズム
マイコン系 プログラムのテクニック アルゴリズム 2000/1月再着工 現在工事中 チャタリング取り 割算を使わない整数の平方根の算出 その他関数近似 10進 １００進 割算 DDA ステップモータの回し方 MOD n の平均 プログラムの流れ Win95で斜め楕円の描画 楕円をベジェスプラインで近似する 楕円の周長 直線,円系 の アルゴリズム 今までニフテイとかに投稿した内容をまとめています。推考していないので ボロボロとミスがあるようです。 論理演算の利用 AND OR 演算を利用すると分岐無しに色々な計算が出来ます 分岐無しにすると処理時間が固定になり便利な事が多いですね 最近のCPUは分岐が少ない方が速い事も多いようです /************************************************************ 符号無し同士の加算をし、結果がオーバ
割り算を使わずに割り算する — KaoriYa
前回から間が開いてしまいましたが、やっと当初のゴール=割り算を使わずに割り算をしてみましょう。 まずは補助関数を1つ定義しましょう。 int msb(int a) { int c = 0; while (a != 0) { a >>= 1; ++c; } return c; } この msb() は most significant bit の位置を求める関数です。 加えて前回の引き算で定義した sub() を使います。 以上を踏まえて mydiv() を見てみましょう。 この関数では商(戻り値) q = a / b と余り *r = a % b の両方が求まります。 int mydiv(int a, int b, int *r) { int q = 0; int c = msb(a) - msb(b); for (; c >= 0; --c) { int d = sub(a, b <<
Super Technique 講座〜ハッシュテーブル
ハッシュテーブルは、中級の基本技である。「ハッカー」と呼ばれる程のプログラマならば、使いなれた自作ハッシュライブラリを持っていて当然である。また、これは非常に検索が速く便利なために、awk から Perl に至るスクリプト言語で、言語仕様に採り入れられてよく「連想配列」などと呼ばれている。要するに、 $List{'http'} = 80; のように、配列なのに文字列を添字として取るような書き方をするアレである。これは「キー」である文字列に対して、「値」である何かのオブジェクトを返すという動作であり、そういう動作こそが「ハッシュテーブル」以外の何者でもない。ものすごく便利なので、ぜひマスターされたい。→ Java 講座の「ハッシュテーブル」 準備～リスト版線形探査 ハッシュテーブルの原理 ライブラリの実装 他の応用 Java の Hashtable クラス 準備～リスト版線形探査 ハッシュテ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Game Programming Patterns を読んだ - kumar8600の日記
忘れないうちにメモをしろ 2000-5～9