この記事ではPythonを使ってランレングス圧縮（RLE）を実装していきます。ランレングス圧縮はデータ圧縮アルゴリズムの一種でRLE(Run Length Encoding)とも言われます。連続したデータを、ひとつ分のデータと連続した長さで表現します。たとえば「AAABBCCCCA…

しゃくとり法は以下のような時に使えるアルゴリズムです。〇〇を満たす区間 (連続する部分列) のうち、最小or最大の長さを求めよ、〇〇を満たす区間 (連続する部分列) を数え上げよ。左端と右端のインデックスを条件に合わせて適切に動かすことによって最適…

ひとことに全探索といっても様々な種類があります。この記事では今まで解説してきた全探索アルゴリズムをまとめていきたいと思います。 単純な全探索 順列全探索 bit全探索 深さ優先探索 幅優先探索 単純な全探索 単純な全探索は最も簡単な全探索です。for文…

(adsbygoogle = window.adsbygoogle || []).push({}); statsmodels.apiをインポートしようとしたら下記のようなエラーが出て困ったのでその対処法を記していきます。 ImportError: cannot import name 'factorial'結論から言うと、どうやらscipyのバージョン…

この記事では区間スケジューリング問題をPythonを利用して解いていきます。区間スケジューリング問題はソートと貪欲法を利用することによって解くことができます。貪欲法を知らない方はまずこちらの記事をお読みください。 nashidos.hatenablog.com (adsbygo…

今回は幅優先探索をPythonで実装していきます。本記事では、幅優先探索の基本的な最短経路を求める問題と少し応用的な問題を解いていきます。 幅優先探索(BFS)とは 例題１ 実装 例題２ 実装 まとめ 幅優先探索(BFS)とは 幅優先探索(BFS)はBreadth First Sear…

本記事では、深さ優先探索をPythonを利用して実装していきます。実際に深さ優先探索の典型問題をスタックと再帰関数の2パターンの解き方で実装し、解説していきます。 深さ優先探索(DFS)とは 例題 問題文 再帰関数で実装 スタックで実装 まとめ 深さ優先探索…

「月曜日は上がりやすい」など曜日と価格変動が関係しているという噂を耳にしたことがある人もいるのではないでしょうか。そこで本記事では、実際に曜日と価格変動に関係があるのかをPythonを利用して分析していきます。

Kaggleに登録したものの使い方がわからず困っている人もいるのではないでしょうか。私自身、Kaggle入門者向けの記事を読んでタイタニックの提出はしてみたものの、いざ自分でコンペに参加しようと思うとわからないことが多すぎて放置していました。なので、…

今回の記事ではPythonで貪欲法(Greedy Algorithm)を実装していきます。貪欲法は最適化手法の中でも基本的なアルゴリズムで比較的実装も簡単なので書けるようにしておきましょう。 貪欲法とは 例題 問題文 制約 実装 さいごに (adsbygoogle = window.adsbygoo…

今回は優先度付きキューをPythonのheapqで実装していきます。優先度付きキューとは一言で説明すると最大値、最小値を普通のリストよりも早く見つけることができるアルゴリズムです。通常のリストでは最大値、最小値を見つける計算量が(O(N))であるのにたいし…

本記事ではProgateが終わったら次にすべきことについて私自身の考えを述べていきます。Progateが終わったら次は「自分で何かを作ってみるといい」ということがよく言われますが実際のところはどうなのかについて考察していきます。 「自分で何かを作る」は正…

自分の環境では実行できるのにAtCoderで実行してみるとAttributeError:'module' object has no attribute 'gcd'と表示されて困った方もいるのではないでしょうか。私もAtCoderで初めてgcdを使った時にエラーが出てきて、対処法に困ったのでここに解決策を記…

本記事ではPythonを使って二分探索を実装していきます。二分探索とはソートされたデータを高速に探索することができるアルゴリズムです。ソートされていないものには使えないので注意してください。二分探索はその名の通り、データを2つに分けて探索するとい…

累積和とはその名の通り、累積の和をとる前処理をすることによってクエリの速度を上げることができるアルゴリズムです。実際に累積和の問題をPythonで解いていきます。どれくらい速くなるかを確認していきましょう。

bit全探索 全探索にもいろいろ種類がありますが今回はbit全探索をPythonで実装していきたいと思います。bit全探索とはその名の通りbit演算を利用して行う全探索で、Yes or Noのような2択を網羅的に探索する時に使えます。説明を聞いてもわかりにくいかもしれ…

全探索 問題 問題文 制約 実装 全探索 全探索にはbit全探索やDFSなどいろいろありますが、今回は最も簡単な基本の全探索をPythonで実装していきます。 問題 問題は ABC 051 B-Sum of Three Integersを扱います。B - Sum of Three Integers 問題文 2 つの整数…

はじめて当ブログを開設するにあたって、このブログの目的および内容の確認と軽く自己紹介を書こうと思います。ただし、内容や目的が変わる可能性もあるのでそこのところはご容赦ください…