【アルゴリズム】問題を効率よく解くための基本アプローチ！「アルゴリズム設計の4大戦略」
基本情報技術者・応用情報技術者試験やプログラミングの学習で必須となる「アルゴリズム設計技法」の代表的な4つのアプローチ（力ずく戦略・分割統治戦略・ダイナミックプログラミング・欲張り選択戦略）のまとめカードです。
1. アルゴリズム設計の4大戦略（要点まとめ）
1. 力ずく戦略（Brute Force / ブルートフォース）
すべての可能性や組み合わせを、「しらみつぶし」に試して解を見つける確実だが単純な方法。
2. 分割統治戦略（Divide and Conquer）
解くのが難しい大きな問題を、「小さな均質（同質）の問題に分割」してそれぞれを解き、最後に結果を統合する方法。
3. ダイナミック・プログラミング（Dynamic Programming / 動的計画法）
分割された部分問題に「同じ問題の重複」が存在する場合、その小問題の解をメモ化（記録）して再利用し「何回も解くこと（重複計算）を回避」する効率的な方法。
4. 欲張り選択戦略（Greedy Algorithm / 貪欲法）
各段階・分割した選択肢の中で「その場で目先の一番良い選択肢（局所最適解）を1つ選び、他は破棄する」ことで、短時間で効率的に解（または近似解）を求める方法。
すべての可能性や組み合わせを、「しらみつぶし」に試して解を見つける確実だが単純な方法。
2. 分割統治戦略（Divide and Conquer）
解くのが難しい大きな問題を、「小さな均質（同質）の問題に分割」してそれぞれを解き、最後に結果を統合する方法。
3. ダイナミック・プログラミング（Dynamic Programming / 動的計画法）
分割された部分問題に「同じ問題の重複」が存在する場合、その小問題の解をメモ化（記録）して再利用し「何回も解くこと（重複計算）を回避」する効率的な方法。
4. 欲張り選択戦略（Greedy Algorithm / 貪欲法）
各段階・分割した選択肢の中で「その場で目先の一番良い選択肢（局所最適解）を1つ選び、他は破棄する」ことで、短時間で効率的に解（または近似解）を求める方法。
2. 各戦略の特徴と代表的なアルゴリズム
| 設計戦略 | 考え方・メリット | 代表例・適用例 |
|---|---|---|
| 1. 力ずく戦略 （ブルートフォース） |
実装が簡単で漏れがない。ただしデータ量が増えると処理時間が膨大になる。 | 全探索、暗号の総当たり攻撃、線形探索（リニアサーチ） |
| 2. 分割統治戦略 | 再帰処理と相性が良く、問題を小さくすることで高速に処理できる。 | マージソート、クイックソート、二分探索（バイナリサーチ） |
| 3. ダイナミック・プログラミング （動的計画法） |
途中の計算結果をテーブル等に保存（メモ化）し、無駄な再計算を防ぐ。 | ナップサック問題（DP解法）、最長共通部分列（LCS）、レーベンシュタイン距離 |
| 4. 欲張り選択戦略 （貪欲法） |
後戻り（バックトラック）せず選択肢を切り捨てるため、非常に高速。 | ダイクストラ法（最短経路）、プリム法・クラスカル法（最小全域木）、お釣りの枚数計算 |
3. まとめ
アルゴリズムを設計・選択する際は、「すべての解を保証したいのか（全探索）」「問題を小さく分解したいのか（分割統治）」「重複計算をなくしたいのか（動的計画法）」「スピード重視で目先の最適を選んで切り捨てるのか（貪欲法）」というアプローチの違いを理解しておくことが重要です！
PR