再帰関数を学ぶと、どんな世界が広がるか - Qiita
0. はじめに 再帰関数は初めて学ぶときに壁になりがちで なんとなくわかった...けれど どんな場面で使えるのだろう...いい感じの例を探したい！ という気持ちになりがちです。再帰関数は、なかなかその動きを直感的に想像することが難しいため、掴み所が無いと感じてしまいそうです。 そこで本記事では 再帰関数の動きを追いまくることで、再帰関数自体に慣れる 再帰的なアルゴリズムの実例に多数触れることで、世界を大きく広げる！ ことを目標とします。特に「再帰関数がどういうものかはわかったけど、使いどころがわからない」という方のモヤモヤ感を少しでも晴らすことができたら嬉しいです。なお本記事では、ソースコード例に用いるプログラミング言語として C++ を用いておりますが、基本的にはプログラミング言語に依存しない部分についての解説を行っています。 追記 1. 再帰関数とは 再帰の意味はとても広いです。自分自
意外と解説がない！動的計画法で得た最適解を「復元」する一般的な方法 - Qiita
NTTデータ数理システムでアルゴリズムを探求している大槻 (通称、けんちょん) です。 好きなアルゴリズムは最小カットやマッチングですが、会社ではなぜか「動的計画法が好きな人」と呼ばれています。今回は動的計画法を用いて得られた最適解を復元するための汎用的な方法について紹介します。 0. はじめに 動的計画法を用いて効率的に解くことのできる最適化問題は数多くあります。パッと思いつくだけでも ナップサック問題 迷路などの最短路問題 区間スケジューリング問題 音声認識パターンマッチング問題 レーベンシュタイン距離 発電計画問題 分かち書き 隠れマルコフモデル ... などなど、多種多様な分野の問題を動的計画法によって効率よく解くことができます。このように、分野横断的な活用をできることが、動的計画法をはじめとした数理工学的手法の特長であり醍醐味であると常々感じています。今回は動的計画法によって得ら
特集！知らないと損をする計算量の話 - Qiita
1. はじめに 今回は実務プログラミングにおいて知らず知らずのうちに遅いコードになっていそうな例をいくつか挙げて、それを計算量の観点から高速化してみたいと思います。 2. 計算量を意識することにどんな意味があるか 身近な例として、Qiita Contribution ランキングの作成を考えてみましょう。ランキングを作成するためには、各ユーザーの Contribution 数を大きい順に並び替える処理、すなわちソートが必要になります。 Qiita ユーザー数は現在およそ $30$ 万人です。標準ライブラリの sort を用いれば、それほどの計算時間はかからないと思います。しかし仮にこれを愚直な sort アルゴリズム (例えば、挿入ソートやバブルソートなど) で実行したら恐ろしいことになります。 愚直なソートは、並び替える要素の個数の 2 乗に比例した時間がかかります。すなわち $n$ を並
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
