問題 No.2699
再帰呼び出しを用いたアルゴリズムにおいて、同じ引数に対する計算結果をあらかじめテーブル等に保存しておき、二度目以降の計算時にはその結果を再利用することで処理を効率化する手法を指す用語はどれか。
【正解の解説】
メモ化
これは、料理のレシピで一度測った調味料の分量をメモしておき、二度目は計量をスキップして即座に調理を進めるようなものです。同じ計算を何度も繰り返す無駄を防ぐため、勉強で一度解いた問題の答えをノートの端に控えておくような感覚でプログラムの効率を劇的に高めてくれます。
スポンサーリンク
【その他の選択肢の解説】
動的計画法
メモ化は、この動的計画法という大きな戦略を実現するための具体的なテクニックの一つに過ぎません。動的計画法という言葉が「計画を立てる大きな枠組み」を表すのに対し、メモ化は「計算結果を記録する具体的な作業」であるという点で異なるため注意が必要です。
テールコール
計算結果を保存して使い回すメモ化とは全く目的が異なり、こちらはメモリの無駄遣いを防いでプログラムが途中で止まってしまわないようにする省エネ技術です。言葉の響きが似ていますが、処理の効率化ではなくメモリ管理の仕組みに関する用語として区別しましょう。
分割統治法
有名な「マージソート」などがこれに該当します。分割統治法は、同じ部分問題を何度も重複して解くような場合に非効率になることがあり、その重複する部分問題を効率的に処理するためにメモ化のテクニックが組み合わされて使われることが多いです。