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

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

アルゴリズム

ゼロから始める動的計画法 - コイン問題

問題設定 Project Euler Problem 31 考察 動的計画法による解答 問題を簡単にする なぜ動的計画法か? まずは2次元配列で Rubyのコードに落とし込む プロジェクトオイラー用に微調整 問題設定 Project Euler Problem 31 ターゲットとする問題は以下 Project…

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

メモ用、他にあれば追記する ポータルサイト 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による木のマージ処理が必要で…

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

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