おはやし日記

特にテーマ無しの日記。

AOJ

座標圧縮備忘録

座標圧縮、なるアルゴリズムに出会いました。どうにかわかったつもりになったので記録しておきます。自分用メモ的な精度。 座標圧縮とは 詳しくは参考のサイトを見てください。 簡単に言うと、「座標の広い範囲に散らばっている点について、その相対的な位置…

グラフの関節点と橋を求めて再帰DFSを知る

こんにちは。再帰のDFS(深さ優先探索)っていままでよくわからなくて、スタックを使えばBFS(幅優先探索)の書き換えで済むじゃんと思っていました。過去記事でもスタックDFSを使っています。 o-treetree.hatenablog.com ただ、スタックDFSは「順番がDFSで…

AIZU ONLINE JUDGE GRL_1_A 単一始点最短経路 を解くダイクストラ法の実装

こんにちは。 o-treetree.hatenablog.com ちょっと前にAOJの問題を解いて動的計画法を学びましたが↑、グラフも勉強しようかなって思ってグラフのページを開きました。1番最初にあったのが 単一始点最短経路 です。何も知らない僕は最初幅優先探索でやりまし…

DP(動的計画法)でレーベンシュタイン距離(編集距離)問題を解くまでの過程メモ

昨日は最長増加部分列の問題を解きました https://o-treetree.hatenablog.com/entry/DPL1D 今日は、AOJの編集距離の問題を解きます。 といっても、相変わらずDPテーブルは思いつかなかったので検索してわかりやすかった解説を紹介する感じです。 参考にする…

DP(動的計画法)で最長増加部分列(LIS)問題を解くまでの過程メモ

なんか連載みたいになってんな 前回はDPでナップザック問題を解きました。 AOJでその次にあった最長増加部分列を解きました。 というか、解けなかったので検索して最長増加部分列(LIS)の長さを求める - Qiitaを見てなるほど〜ってなったのを自分なりにまとめ…

DP(動的計画法)でナップザック問題を解くまでの過程メモ

0-1 ナップザック問題 この0-1ナップザック問題が解けたので動的計画法初心者がその思考過程を記録しておく。 その後、簡単な書き換えによって一般ナップザック問題(命名: おはやし)が解けたので追記している。 先にコイン問題 前段階としてコイン問題(何…

DP(動的計画法)でコイン問題を解くまでの過程メモ

これは、https://o-treetree.hatenablog.com/entry/DPL1B(明日投稿)の前段階の記事です。動的計画法(どうてきけいかくほう、英: Dynamic Programming, DP)で「コイン問題」を解いていますが、DPとはなんぞや、みたいなところには触れておらず、解説を見…

プライバシーポリシー ・お問い合わせはこちら