【アルゴリズム】問題を効率よく解くための基本アプローチ！「アルゴリズム設計の4大戦略」

基本情報技術者・応用情報技術者試験やプログラミングの学習で必須となる「アルゴリズム設計技法」の代表的な4つのアプローチ（力ずく戦略・分割統治戦略・ダイナミックプログラミング・欲張り選択戦略）のまとめカードです。

1. アルゴリズム設計の4大戦略（要点まとめ）

1. 力ずく戦略（Brute Force / ブルートフォース）
すべての可能性や組み合わせを、「しらみつぶし」に試して解を見つける確実だが単純な方法。

2. 分割統治戦略（Divide and Conquer）
解くのが難しい大きな問題を、「小さな均質（同質）の問題に分割」してそれぞれを解き、最後に結果を統合する方法。

3. ダイナミック・プログラミング（Dynamic Programming / 動的計画法）
分割された部分問題に「同じ問題の重複」が存在する場合、その小問題の解をメモ化（記録）して再利用し「何回も解くこと（重複計算）を回避」する効率的な方法。

4. 欲張り選択戦略（Greedy Algorithm / 貪欲法）
各段階・分割した選択肢の中で「その場で目先の一番良い選択肢（局所最適解）を1つ選び、他は破棄する」ことで、短時間で効率的に解（または近似解）を求める方法。

2. 各戦略の特徴と代表的なアルゴリズム

設計戦略	考え方・メリット	代表例・適用例
1. 力ずく戦略 （ブルートフォース）	実装が簡単で漏れがない。ただしデータ量が増えると処理時間が膨大になる。	全探索、暗号の総当たり攻撃、線形探索（リニアサーチ）
2. 分割統治戦略	再帰処理と相性が良く、問題を小さくすることで高速に処理できる。	マージソート、クイックソート、二分探索（バイナリサーチ）
3. ダイナミック・プログラミング （動的計画法）	途中の計算結果をテーブル等に保存（メモ化）し、無駄な再計算を防ぐ。	ナップサック問題（DP解法）、最長共通部分列（LCS）、レーベンシュタイン距離
4. 欲張り選択戦略 （貪欲法）	後戻り（バックトラック）せず選択肢を切り捨てるため、非常に高速。	ダイクストラ法（最短経路）、プリム法・クラスカル法（最小全域木）、お釣りの枚数計算

---

3. まとめ

アルゴリズムを設計・選択する際は、「すべての解を保証したいのか（全探索）」「問題を小さく分解したいのか（分割統治）」「重複計算をなくしたいのか（動的計画法）」「スピード重視で目先の最適を選んで切り捨てるのか（貪欲法）」というアプローチの違いを理解しておくことが重要です！

【アルゴリズム・計算理論】現代数学・情報科学の最大未解決問題！「P = NP? 問題」と「NP完全問題」

基本情報・応用情報技術者試験から高度情報処理技術者試験（ITストラテジスト、エンベデッドなど）まで、計算量理論の根本概念として知られる「P = NP? 問題」と「NP完全問題」のまとめカードです。

1. P = NP? 問題 とは

「クラスNPが、クラスPを、真に含むこと（P ≠ NP）の証明」

「答えの正しさを確認するのが簡単な問題（NP）」は、「解くこと自体も簡単な問題（P）」なのか、それとも「解くのが本質的に難しい問題を含んでいるのか（P ≠ NP）」という、いまだ証明されていない未解決問題です。

2. NP完全問題 とは

NPに属する問題の中で「最も難しい問題のグループ」です。以下のどちらかを証明することで、P = NP? 問題全体の決着がつきます。

【NP完全問題と P = NP 決着の条件】

・NP完全問題が、ひとつでも、Pに属さないこと（P ≠ NP）の証明
➔ 「NPには、どうしても多項式時間で解けない難しい問題が存在する」と証明される。

あるいは

・NP完全問題が、ひとつでも、Pに属すること（P = NP）の証明
➔ 「一番難しい問題すら多項式時間で解けるため、NPの全問題が効率よく解ける」と証明される。

3. クラスP と クラスNP の基本概念

クラス	意味・定義	具体的な例
クラス P	現実的な時間（多項式時間）で「解くことができる」問題。	ソートアルゴリズム、最短経路問題（ダイクストラ法など）
クラス NP	提示された答えが正しいかどうかを、現実的な時間で「判定・検証できる」問題。	数独（N×N）、巡回セールスマン問題、素因数分解問題
NP完全	NPの中で最も難しく、すべてのNP問題を効率よくこの問題に変換（還元）できる問題。	3-SAT（3充足可能性問題）、ナップサック問題、ナップサック問題の判定版

---

4. まとめ

「解くのが難しい問題（NP）」のうち、どれか1つでも効率よく解く方法（Pに属すること）が発見されれば、すべてのNP問題が一気に解ける（P = NP）ことになります。現代の暗号技術（RSA暗号など）は「解くのが難しい（P ≠ NPである）」ことを前提に構築されています。

【知識:基礎理論】データを賢く縮める！「シャノン・ハフマンの符号化」

コンピュータが扱う「0」と「1」の組み合わせ（符号）。すべての記号を同じ長さにせず、よく出る文字には短い符号を、滅多に出ない文字には長い符号を割り当てることで、データ全体のサイズを劇的に小さくできます。

■ 符号化の基本概念

特定の規則に従って、データ（文字や数値）をビット列に変換することを符号化（エンコード）と呼びます。特に、出現確率を利用した圧縮は「エントロピー符号化」の基礎となります。

手法	手順とアルゴリズムの考え方
1. シャノン符号化 (Shannon Coding)	「上から下へ」分割する方式 1. 記号を発生確率の高い順に並べる。 2. 確率の合計がなるべく均等になるよう2つのグループに分割する。 3. 各グループに「0」と「1」を割り当てる。 4. 記号が1つになるまで分割を繰り返す。
2. ハフマン符号化 (Huffman Coding)	「下から上へ」統合する方式（より効率的） 1. 確率が低い順に2つの記号を選び、枝で結んで合計確率を持つ親ノードを作る。 2. 親ノードを新しい記号と見なし、再び低い順に2つ選ぶ作業を繰り返す（ハフマン木の作成）。 3. 根から各記号までの道筋（左右）を「0」と「1」に対応させる。

具体的な例（ハフマン符号化）

例えば、「A(60%)、B(30%)、C(10%)」という確率の記号がある場合：

• 手順： 低い「B」と「C」を合体させて1つのグループ（40%）とし、次に残った「A（60%）」と合体させます。
• 結果： 最も多い「A」には「0」などの短い符号、少ない「B」「C」には「10」「11」などの長い符号が割り当てられます。
• メリット： すべてを2ビット（AA=00, B=01, C=10）で表すより、平均ビット数が少なくなります。

試験対策の重要ポイント

• 可変長符号：記号によってビット長が異なる符号のこと。ハフマン符号はその代表例です。
• 一意復号可能：短い符号が長い符号の「接頭辞」にならない（例：Aが0なら、Bは01にできない）ように設計されており、どこで区切るか迷わずに解凍できます。
• データ圧縮：ZIPファイルやJPEG、MPEGなどの圧縮技術の根幹として使われています。

※シャノン符号化は歴史的に重要ですが、現在の実用シーンではより圧縮効率が高いハフマン符号化が主流となっています。