なんとな~くしあわせ?の日記

JavaとかAWSの設定とかをメモする技術ブログ

アルゴリズムまとまってるサイト

メモ用、他にあれば追記する ポータルサイト www.geeksforgeeks.orgwww.csegeek.com 大学の授業シラバス系 ヨークカレッジ・ペンシルベニア校 Lecture Notes イリノイ大学アーバナ・シャンペーン校 Jeff Erickson's Algorithms, Etc. このサイトにあったサイ…

AtCoder - AtCoder Beginner Contest 040 (道路の老朽化対策について) を解いてみた

アルゴリズム 経路圧縮 rankによる木のマージ処理 ABC 040 D問題に使われるアルゴリズム要素はUnion-Findです。Union-Find自体は前回ブログ記事にしていたのですが…これだけでは足りませんでした。ACするためには経路圧縮とrankによる木のマージ処理が必要で…

Instaparseでパーサジェネレータ

Instaparseの位置づけ InstaparseはClojure言語による パーサジェネレータ - Wikipedia であるgithub.comこれのルール記述はBNFの拡張であるEBNFが使われている。 EBNFで構造化言語のルールを記述する さっそくだが、「<p>sample</p>」を読み取るBNFのル…

パーサジェネレータについて調べた

パーサジェネレータの位置づけ パーサ(=構文解析器) パーサジェネレータの利点 パーサジェネレータの実装の種類 パーサジェネレータの位置づけ 少しだけパーサジェネレータについて書く。パーサジェネレータとはパーサを生成できるソフトウェアのことであ…

AtCoder - AtCoder Beginner Contest 012 (バスと避けられない運命) を解いてみた

前回の競プロ! 解法 Rubyによる解答 TLE D言語による解答 AC! 前回の競プロ! ダイクストラ法を学んでようやくスタート地点に立てました。ダイクストラ法については以下のエントリを参照。nantonaku-shiawase.hatenablog.com 解法 Rubyによる解答 TLE アル…

AOJ - ALDS1_12_B (ダイクストラ法) を解いてみた

問題設定 最短経路問題の分類とアルゴリズムの使いどころ グラフをGraphvizでビジュアル化する アルゴリズム 疑似コード 自分の解答 AOJ - ALDS1_12は、重み付きのグラフアルゴリズムです。最短経路 ダイクストラ法 | アルゴリズムとデータ構造 | Aizu Onlin…

AOJ - ALDS1_12_A (プリム法) を解いてみた

問題設定 グラフをGraphvizでビジュアル化する アルゴリズム 疑似コード 自分の解答 コードの工夫など AOJ - ALDS1_12は、重み付きのグラフアルゴリズムです。最小全域木| アルゴリズムとデータ構造 | Aizu Online Judge 問題設定 最小全域木というのは、 重…

AOJ - ALDS1_11_A,B,C (グラフアルゴリズム) を解いてみた

ALDS1_11_A (隣接行列) 自分の解答 ALDS1_11_B (深さ優先探索) アルゴリズム 自分の解答 ALDS1_11_C (幅優先探索) アルゴリズム 自分の解答 AOJ - ALDS1_11は、グラフアルゴリズムです。グラフの表現 | アルゴリズムとデータ構造 | Aizu Online Judge 深さ優…

mavenで本番用/開発用のwarファイル切り替え

成果物の設定情報切り替え ユースケース 実際に使われる環境変数 他のフレームワークでの方法 mavenで本番用/開発用のwarファイル切り替え profile maven resources plugin 環境ごとの切り替えの実装 プロパティファイルの値の置き換え プロパティの置き換え…

Bitnami版Jenkinsとコンソール出力の自動更新

Bitnami JenkinsAWS上で使用するJenkinsにBitnamiが提供しているUbuntuのイメージを使っているのですがbitnami.comどうもこれが原因でビルド結果の自動更新がうまく動いてなかったらしい。 対象チケット [JENKINS-25026] Console output stops populating af…

AOJ - DPL_1 D (最長増加部分列) を解いてみた

最長増加部分列の基本 問題設定 アルゴリズム 線形探索版のプログラム - O(N^2) 二分探索版のプログラム - O(N log N) サンプルプログラム 線形探索版のプログラム - O(N^2) 二分探索版のプログラム - O(N log N) AOJ - DPL_1 Dは、最長増加部分列(Longest I…

JRubyに挑戦2

REST APIを作ってみる 作りたいもの Hanami - ドキュメント 新規アプリの追加 新規Action/Viewの追加 新規Entity/Repositoryの追加 モデルは単数形になることに注意 employeeのDBのテーブルを作成 JSONを返す部分を追記 hanami-modelについての見解 もとの記…

JRubyに挑戦1

JRuby ターミナル 日本語化 JRuby on Rails Hanami on Jruby Hanamiについての見解 MVCにService層を追加する Hanamiの試みとは? もとの記事は JRuby - FreeStyleWiki JRuby 環境構築最初はJavaでSpring-bootを使おうとしたけど、連携の面倒さに辟易したの…

SQLもプログラミング言語…っぽい4

SQL

このシリーズも4回目になる。お題は以下の通り テーブルの正規化 正規化とはなんぞや? 非正規形 第1正規形 第2正規形・第3正規形 外部結合の設定 LEFT JOIN 書籍の紹介 履歴管理 実際的な設計 概念的な話 テーブルの正規化 正規化とはなんぞや? ここが分…

AOJ - ALDS1_7_A, B, C (木構造) を解いてみた

勝手に解いてろとか言わないで… 木構造を使うときの基本 ALDS1_7_A - 根付き木 get_depth ( id, nodes ) get_children ( id, nodes ) ALDS1_7_B - 二分木 get_depth ( id, nodes ) get_height ( id, nodes ) get_sibling ( id, nodes ) ALDS1_7_C - 木の巡回…

MyBatisエラー別対応とか

Wikiの方に書いた記事によくアクセスがあるようなので、はてなに移しておく。 MyBatisのエラー別対応 エラーメッセージ:"Mapped Statements collection does not contain value for クラス名" エラーメッセージ:"Mapped Statements collection already con…

アルゴリズム学びフローを作成してみる

AOJの本 本の内容とレビュー 見通しを立ててみる プロコンで解いた問題を格納 AOJの本 この本を買ってみた。プログラミングコンテスト攻略のためのアルゴリズムとデータ構造…プログラミングコンテスト攻略のためのアルゴリズムとデータ構造作者: 渡部有隆,Oz…

動的計画法で組み合わせの総数 nCr を求めてみる

もっと早い組み合わせの総数 (combination)の求め方 動的計画法 - DP(Dynamic Programming) Combinationのための動的計画法 Rubyによるサンプルプログラム 処理内容を表で表現してみる 実際使う時は 参考 もっと早い組み合わせの総数 (combination)の求め方 …

CloudflareとLet’s Encryptを同時に使ってると、Let’s Encryptが更新できない件

tls: handshake failure 解決策 Cloudflare側の設定 There were too many requests of a given type :: Error creating new authz :: Too many invalid authorizations recently.. Skipping. 解決策 tls: handshake failure Let's Encryptで更新かけるとき、…

AOJ - DSL_1_A (Union-Find) を解いてみた

AOJ - DSL_1_A quick find で求めてみる quick-unionで求めてみる DSL_1_Aは、Coursera Algorithm I で最近習ったばかりのUnion-Findです AOJ - DSL_1_A 互いに素な集合 Union Find| データ構造ライブラリ | Aizu Online Judge quick find で求めてみる 自分…

Hadoop Hive用にDockerのイメージを作ってみた

動機 Hiveのテスト時にいちいちEMRを起動したくない リポジトリ https://hub.docker.com/r/hiroyuking/docker-hiveserver2/ https://hub.docker.com/r/hiroyuking/docker-bigtop/ 参考にしたもの DockerとDocker Composeについては以下のサイトqiita.comApac…

文系エンジニアだがCourseraの機械学習コースを修了した

動機 以下の記事をQiitaで見つけて、これはいいなと思い受講してみました。qiita.com qiita.com 感想 学習期間 2月初旬に始めていたはずなのだが、結局終わったのは5月下旬。4ヶ月かかっている。 本来3ヶ月で終わるべきだが補習授業みたいな感じで期間を…

AOJ - ITP1_7_D (行列の積) を解いてみた

AOJ - ITP1_7_D 行列の積をプログラムに起こすと? 問題の内容 問題の解法 行列計算の参考リンク ITP1_7_Dは、今自分の中でブームの行列の積の問題です。生で計算しないにしても、機械学習にも大いに関係があります。 AOJ - ITP1_7_D Matrix Multiplication …

AOJ - ITP1_7_B (組み合わせ) を解いてみた

偉そうに書いてるが、これは序の口の問題である。。。 AOJ - ITP1_7_B 解法1 algorithm - Finding all possible combinations of numbers to reach a given sum - Stack Overflow アルゴリズム 処理フロー 結果 解法2 Given an array A[] and a number x, …

Bash/Octaveで順列・組み合わせ

Bashで計算しようとしたのだが、結論から言うと遅すぎて使えない。Octaveで計算すると早かったのでそっちを推奨する。 Bash 順列 (nPr) bash - Generate combinations of elements with echo - Stack Overflow 参考になったが、これはCombinationではなくPer…

Javaで簡単な組み合わせの総数 nCr を求めてみる

Aizu Online Judgeをやっていて、求められんかな?と思ったので。 速さとかは遅いと思う。 Java 実働してるやつ 参考 ソースコード 所感 Ruby 実働してるやつ ソースコード Java 実働してるやつ [Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ 参考 stackoverflow.com ソー…

Apache PigでZipファイルをロード

github.com 経緯 仕事でHadoopを使うとき、gzip/bzipは標準で読み込めるがzipは読み込めなかった。困る。 Hadoopの本流でzipファイルを読む機能がマージされてないまま放置されていることに気づく Hadoopがzipをサポートしていない理由 | Tech Blog [MAPREDU…

Hadoop関連ソフトウェアを手っ取り早くパッケージでインストールする

Apache Bigtop Bigtop - Apache Bigtop Bigtop is an Apache Foundation project for Infrastructure Engineers and Data Scientists looking for comprehensive packaging, testing, and configuration of the leading open source big data components. Bi…

Apache PigでShift_JISテキストをUTF-8化

Apache PigでShift_JISテキストをUTF-8化 hdfs上にファイルを取り込む際、デフォルトの文字コードはUTF-8らしい。 どうやって取り込むか悩んだが、UDFという方法を見つけた。 User Defined Function:UDF Pig ユーザー定義関数メモ(Hishidama's Apache Pig U…

Msys2でSSL certificate problem: unable to get local issuer certificateが出たとき

エラー内容 git cloneしようとして、以下のようなエラー fatal: unable to access 'https://gitlab-xxxx/yyyy/xxxx.git/': SSL certificate problem: unable to get local issuer certificate 原因 対象のGitサーバが使用している証明書のRoot証明書がmsys2…