二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜 - Qiita
0. はじめに 二分探索法は単純ながらも効果が大きく印象に残りやすいもので、アルゴリズム学習のスタート地点に彩られた花という感じです。二分探索というと「ソート済み配列の中から目的のものを高速に探索する」アルゴリズムを思い浮かべる方が多いと思います。巨大なサイズのデータを扱う場面の多い現代ではそれだけでも十分実用的ですが、二分探索法はもっとずっと広い適用範囲を持っています。 本記事では、二分探索法のエッセンスを抽象化して、適用範囲の広い「二分探索法の一般形」を紹介します。同時に無数にある二分探索の実装方法の中でも「めぐる式二分探索」がバグりにくいと感じているので、紹介したいと思います。 注意 1: 二分探索の計算時間について 二分探索の計算時間について簡単に触れておきたいと思います。例えば「$n$ 個の要素からなるソート済み配列から目的の値を探索する」というよく知られた設定であれば、 単純な
LIS でも大活躍！ DP の配列使いまわしテクニックを特集 - Qiita
0. はじめに 動的計画法の解法に対しては、「一次元 DP」や「二次元 DP」といった呼称でよびたくなりがちです。たとえば ${\rm dp}[i] := i$ 番目の地点まで到達するまでの最小コスト というような DP テーブルを用いるような DP1 は一次元 DP であり、 ${\rm dp}[i][w] := N$ 個の品物のうち最初の $i$ 個の品物の中から、重さが $w$ を超えない範囲でいくつか選んだときの、選んだ品物の価値の総和の最大値 というような DP テーブルを用いるような DP2 は二次元 DP である、といった具合です。後者はいわゆるナップサック問題に対する DP として有名ですね！ 二次元 DP の配列を再利用して一次元へ しかし今回は、DP を一次元や二次元とよぶことにあまり意味がないかもしれない...という話をします。たとえばナップサック DP は、なんと実
アルゴリズムとは何か！？ ～ 文系理系問わず楽しめる精選 6 問 ～ - Qiita
今の場合は A さんが 31 歳の場合のストーリーでしたが、A さんが 20 歳～ 35 歳のうちのどの年齢であったとしても、似たようなストーリーで必ず 4 回の質問で当てることができます！(他の例も是非考えてみてください。) ちなみに、このような「真ん中で切ってどちらかに絞って行く」タイプのアルゴリズムには二分探索法という名前がついています。応用情報技術者試験でも頻出のテーマですので馴染みのある方も多いと思います。 1-2. つまり、アルゴリズムとは 上の年齢当てゲームという問題では、相手の年齢を当てる「方法・手順」を二分探索法に基づいて導きました。このようにアルゴリズムとは、 問題を解くための方法・手順 のことです。さて、アルゴリズムと聞くと「コンピュータ上で実装されたプログラム」のことを思い浮かべる方も多いと思いますが、必ずしもコンピュータと関係がある必要はなく、日常生活でも多々登場
ソートアルゴリズムを極める！ 〜 なぜソートを学ぶのか 〜 - Qiita
NTT データ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。 今回はソートについて記します。 0. はじめに データ構造とアルゴリズムを学ぶと一番最初に「線形探索」や「ソート」が出て来ます。これらのテーマは応用情報技術者試験などでも頻出のテーマであり、アルゴリズムの Hello World とも呼ぶべきものです。 特にソートは、 計算量の改善 ($O(n^2)$ から $O(n\log{n})$ へ) 分割統治法 ヒープ、バケットなどのデータ構造 乱択アルゴリズムの思想 といった様々なアルゴリズム技法を学ぶことができるため、大学の授業でも、アルゴリズム関連の入門書籍でも、何種類ものソートアルゴリズムが詳細に解説される傾向にあります。本記事でも、様々なソートアルゴリズムを一通り解説してみました。 しかしながら様々な種類のソートを勉強するのもよいが、「ソートの使い方」や
ビット演算 (bit 演算) の使い方を総特集！ 〜 マスクビットから bit DP まで 〜 - Qiita
はじめに はじめまして。 NTTデータ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。 C や C++ を使用しているとしばしばビット演算を行う場面が出て来ます。 計算機リソースが限られている状況では、ビットを用いることでデータ量を少なく済ませたり、計算コストを小さく抑えたりすることができるメリットがあります。 本記事では、ビット演算を用いて実現できる処理について、簡単なものから高度なものまで集大成します。極力わかりやすく頑張って執筆しました。特に前半 4 つはビットの説明の中でもかなりわかりやすい方だと思います。後半の 7 つのテーマは比較的高度なアルゴリズムの話題ですので、フラグ管理やマスクビットについて詳しく学びたい方は前半 4 つを中心に読んでいただいて、後半 6 つは必要に応じて読んでいただければと思います。反対にビットの知識はあってビットを用いたアルゴリズ
実世界で超頻出！二部マッチング (輸送問題、ネットワークフロー問題）の解法を総整理！ - Qiita
0. はじめに --- 二部マッチング問題は実世界で超頻出 はじめまして。NTTデータ数理システムでアルゴリズムを探求している大槻 (通称、けんちょん) です。 好きなアルゴリズムはタイトルにもある二部マッチングですが、会社ではなぜか「DP が好きな人」と呼ばれています。 以前に動的計画法 (DP) の典型パターンを整理した記事を執筆したのですが、DP と並んで超頻出の話題として二部マッチング問題があります。二部マッチング問題とは、例えばマッチングアプリなどに見られるように、2 つのカテゴリ間で最適なマッチングを構成していく問題です。実問題で登場する二部マッチングは以下のように多岐にわたります: マッチングアプリで男女のペアを最適化する (「男」と「女」) インターネット広告分野で、ユーザの興味に合う広告を出す (「ユーザ」と「広告」) 企業検索サービスなどで、ユーザの検索履歴に合う企業を
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
