木の復元の問題です。木の巡回の応用問題となってます。木の復元 | アルゴリズムとデータ構造 | Aizu Online Judge 例 まず、例を見て解き方を考察します。 先行順巡回で P = {1, 2, 3, 4, 5}、中間順巡回で I = {3, 2, 4, 1, 5} という順でノードが訪問され…

木構造を持つデータを探索するアルゴリズムに、木の巡回と呼ばれるものがあります。今回は３種類の木の巡回を取り上げ、それらを実装してみます。 木の巡回 木の巡回とは、ある木に属する全てのノードを順番に１回づつ訪問するアルゴリズムのことを指します…

グラフを描きたくなることってありますよね。ここでいうグラフはmatplotlibで描くような類のものではなくて、ノードとエッジからなる、グラフ理論でいうところのグラフです。 で、そのグラフを綺麗に描くことのできるツールがGraphvizです。DOTなる言語で記…

みんな大好き（？）Inkscapeをコマンドラインでインストールします。フリーのドローソフトの決定版みたいなもんだと勝手に考えてます。 Homebrewが使えるようになっていることが前提です。 環境 Mac OS Mojave バージョン 10.14.3 Inkscapeをインストールす…

もっとも高速なソートであると言われているクイックソートを実装します。前回実装したパーティションを利用します。最後に問題を解きます。 パーティションの記事はここ↓ programgenjin.hatenablog.com 目標 クイックソートを実装できるようになる。 クイッ…

高速ソートアルゴリズムに関して、今回はパーティションを実装します。パーティションはクイックソートで利用されています。 流れとしては、パーティションの説明と実装の後、最後に問題を１題解いてみます。 目標 パーティションを実装できるようになる パ…

今まで初等的なソートアルゴリズムである挿入ソート、バブルソート、選択ソートを実装してきました。 しかし、これらは簡単に実装できるものの、遅いです。そこで、今度はより高速なソートアルゴリズムを実装してみたいと思います。今回はマージソートです。…

探索アルゴリズム第2弾、前回の線形探索に引き続き、今回は二分探索についてまとめました。 * 目標二分探索を実装できるようになる。 二分探索 二分探索は、整列された配列に適用できる高速な探索方法です。あらかじめ整列されている必要があることに注意が…

アルゴリズムとデータ構造について勉強していて、探索アルゴリズムについて学んだのでメモを残しておきます。今回は線形探索です。 実装しながら簡単な説明をして、それから問題を解きます。 目標 線形探索を実装できるようになる。 線形探索 多数の要素が並…

データ構造第3弾、今回は連結リストを実装してみます。 これまでスタックやキューを実装してきましたが、今回はちょっとそれらより難しそうです。 目標 標準ライブラリに入っている連結リストを、自分で実装してみることで理解する。 双方向連結リスト 双方…

C++のヘッダーファイルを書く機会があって、#ifndefだの#endifだのが登場してなんぞこれとなったので、調べたことを簡単にまとめておきます。 目標 いつまでもおまじないで済ますわけにはいかないので、#ifndef~#endifが何者なのかを理解する。 #ifndef、#en…

C++でデータ構造を実装してみるシリーズ。今回はキューを勉強しました。 標準ライブラリにありますが、勉強のために自分で実装します。 目標 キューを自分の手で実装してみる。 キュー キューは先入れ先出し（FIFO: First In First Out）を特徴とするデータ…

プロコンのための勉強の一環としてデータ構造を学習しています。今回はスタックです。 C++の標準ライブラリに入っていますが、勉強のために自分で実装してみます。 目標 スタックを実装する。 スタックとは 後入れ先出し（LIFO: Last In First Out）を特徴と…

初等的ソートアルゴリズム第4弾。今回はシェルソートを実装してみます。挿入ソートの応用です。 挿入ソートがわからない方はこちら↓ programgenjin.hatenablog.com 目標 シェルソートを理解する。例によって問題を解きます。 シェルソート あらかじめある程…

初等的ソートアルゴリズム第3弾。今回は選択ソートです。 目標 選択ソートを理解することを目指します。例によって問題を解くことで理解を深めます。 選択ソート 計算量は。前方のソートずみ部分に、未ソート部分から小さい順に要素を選択して加えていくこと…

木というデータ構造があります。プロコンやグラフ理論の勉強をしていると出てくると思います。木ってなに？という方や、だいたいどんなものかは知っているけど実装したことはないという方に向けて、まず基本的なところをざっくり説明して、それから問題を解…

初等的ソートアルゴリズム第2弾。 今回はやたらと耳にすることが多いバブルソートです。 目標 バブルソートを理解する。実際に問題を解いてみます。 バブルソート 数列を昇順にソートします。計算量はです。 アルゴリズム 昇順になっていない隣接要素がなく…

最近プロコンのためにアルゴリズムの勉強始めたので、メモを残しておきます。まずは基本であるソートをやっていこうかと。今回は挿入ソートです。 目標 挿入ソートを理解する。プロコンの問題を解くことで実装も行う。 挿入ソート 挿入ソートは初等的なソー…

floatfltは周囲に文章が回り込んだ図表を挿入するLatexのパッケージです。 レポートを書いてたところ、小さな表の周りにいちいち大きな空白ができるのが嫌だなー、と思って導入してみたので、その時の手順を紹介します。こんな感じです。 環境 macOS Mojave …

統計や確率論やってるとよく出てくる期待値について。 期待値をただの<>で囲っていてはあまりにもダサいので、かっこよく表記しようと思って調べていたら、braketと言ういい感じのパッケージを見つけたので紹介します。 もしかしたらパッケージ入れなくても…