【初心者向け】貪欲法とは？グリーディアルゴリズムの基本から応用まで完全解説

フリーランスボード	20万件以上の案件から、副業に最適なリモート・週3〜の案件を一括検索できるプラットフォーム。プロフィール登録でAIスカウトが自動的にマッチング案件を提案。市場統計や単価相場、エージェントの口コミも無料で閲覧可能なため、本業を続けながら効率的に高単価の副業案件を探せます。フリーランスボード
ITプロパートナーズ	週2〜3日から働ける柔軟な案件が業界トップクラスの豊富さを誇るフリーランスエージェント。エンド直契約のため高単価で、週3日稼働でも十分な報酬を得られます。リモートや時間フレキシブルな案件も多数。スタートアップ・ベンチャー中心で、トレンド技術を使った魅力的な案件が揃っています。専属エージェントが案件紹介から契約交渉までサポート。利用企業2,000社以上の実績。ITプロパートナーズ
Midworks	10,000件以上の案件を保有し、週3日〜・フルリモートなど柔軟な働き方に対応。高単価案件が豊富で、報酬保障制度（60%）や保険料負担（50%）など正社員並みの手厚い福利厚生が特徴。通勤交通費（月3万円）、スキルアップ費用（月1万円）の支給に加え、リロクラブ・freeeが無料利用可能。非公開案件80%以上、支払いサイト20日で安心して稼働できます。Midworks

プログラミングやアルゴリズムを学習する際に必ず出会う重要な概念の一つが「貪欲法（グリーディアルゴリズム）」です。その名前から想像できるように、「目先の利益を追求する」アプローチでありながら、多くの問題で効果的な解を見つけることができる興味深いアルゴリズム手法です。

本記事では、貪欲法の基本概念から具体的な応用例まで、初心者にも分かりやすく詳しく解説します。競技プログラミング、面接対策、実務でのアルゴリズム設計において役立つ知識を網羅的に紹介します。

貪欲法（グリーディアルゴリズム）とは

基本的な定義

貪欲法（Greedy Algorithm）とは、各段階で局所的に最適と思われる選択を行うことで、全体として良い解を求めるアルゴリズム設計手法です。「その時点で最も良いと思える選択を常に行う」という直感的なアプローチが特徴です。

貪欲法の基本的な考え方

貪欲法は以下の原則に基づいて動作します：

局所最適選択: 各ステップで、その時点で最も良いと思われる選択を行う 後戻りしない: 一度下した決定は変更しない 段階的構築: 解を段階的に構築していく 単純明快: アルゴリズムの論理が直感的で理解しやすい

身近な例で理解する

日常生活での貪欲法の例を考えてみましょう：

お釣りの計算:

• 1000円の商品を1500円で支払った場合
• 500円玉1枚、100円玉0枚、50円玉0枚、10円玉0枚という具合に
• 大きな額面の硬貨から優先的に使用する

道案内:

• 目的地まで最短で行きたい場合
• 各交差点で「目的地に最も近づく方向」を選択
• 局所的には正しい判断だが、必ずしも全体最適とは限らない

貪欲法の特徴と性質

利点

計算効率の良さ: 通常、線形時間やO(n log n)程度の効率的な時間計算量 実装の簡単さ: アルゴリズムの論理が直感的で実装しやすい メモリ効率: 大量のメモリを必要としない リアルタイム性: オンラインアルゴリズムとして使用可能

欠点と限界

最適解の保証なし: 必ずしも最適解が得られるとは限らない 問題の制約: 貪欲選択性質を満たす問題にのみ適用可能 証明の困難さ: 正しく動作することの証明が難しい場合がある 短視眼的: 長期的な視点を欠く可能性

貪欲法が有効な条件

貪欲選択性質（Greedy Choice Property）:

• 局所最適選択を行っても、全体最適解に到達できる性質
• 各ステップでの選択が後の選択に悪影響を与えない

最適部分構造（Optimal Substructure）:

• 問題の最適解が、部分問題の最適解から構成される性質
• 動的プログラミングでも重要な概念

代表的な貪欲法の問題

アクティビティ選択問題

問題設定: 複数の活動があり、それぞれに開始時間と終了時間が設定されている。時間的に重複しない最大数の活動を選択する。

貪欲戦略: 終了時間が最も早い活動を優先的に選択

アルゴリズムの流れ:

1. 活動を終了時間順にソート
2. 最初の活動を選択
3. 前に選択した活動と重複しない最も早く終了する活動を選択
4. すべての活動を検討するまで繰り返し

時間計算量: O(n log n) – ソート処理が主要な計算量

フラクショナルナップサック問題

問題設定: 容量制限のあるナップサックに、異なる価値と重量を持つアイテムを入れる。アイテムは分割可能で、価値の合計を最大化したい。

貪欲戦略: 単位重量あたりの価値が高いアイテムから優先的に選択

アルゴリズムの流れ:

1. 各アイテムの価値密度（価値/重量）を計算
2. 価値密度の高い順にソート
3. 容量が許す限り、価値密度の高いアイテムから順に追加
4. 容量が不足する場合は、アイテムを分割して追加

最小スパニングツリー問題

クラスカル法:

• 辺を重みの小さい順にソート
• 閉路を作らない辺を順次追加
• 貪欲戦略：最小重みの辺を優先選択

プリム法:

• 任意の頂点から開始
• 現在の木に隣接する最小重みの辺を追加
• 貪欲戦略：隣接辺の中で最小重みを選択

ダイクストラ法（最短経路問題）

問題設定: 重み付きグラフにおいて、指定した頂点から他のすべての頂点への最短経路を求める。

貪欲戦略: 未確定の頂点の中で、始点からの距離が最小の頂点を選択

アルゴリズムの流れ:

1. 始点の距離を0、他の頂点の距離を無限大に初期化
2. 未訪問の頂点の中で距離が最小の頂点を選択
3. 選択した頂点から隣接する頂点への距離を更新
4. すべての頂点を訪問するまで繰り返し

ハフマン符号化

問題設定: 文字の出現頻度に基づいて、効率的な可変長符号を生成する。

貪欲戦略: 出現頻度が最小の2つのノードを優先的にマージ

アルゴリズムの流れ:

1. 各文字を出現頻度とともにノードとして作成
2. 優先度キュー（最小ヒープ）に全ノードを挿入
3. 頻度が最小の2つのノードを取り出してマージ
4. マージしたノードを優先度キューに戻す
5. ノードが1つになるまで繰り返し

貪欲法の証明手法

交換論法（Exchange Argument）

最適解と貪欲解が異なる場合、最適解の一部を貪欲解の要素と交換しても解の品質が悪化しないことを示す手法。

証明の流れ:

1. 最適解OPTと貪欲解GREEDYを比較
2. 両者が異なる最初の選択点を特定
3. OPTの選択をGREEDYの選択に置き換え
4. 置き換え後も解の品質が保たれることを証明

先頭滞在性質（Staying Ahead）

貪欲アルゴリズムが、各ステップで最適解と同じかそれ以上の性能を維持することを示す手法。

証明の流れ:

1. 各ステップでの貪欲解の状態を定義
2. 対応する最適解の状態と比較
3. 貪欲解が最適解以上の性能を持つことを帰納的に証明

貪欲法が失敗する例

0-1ナップサック問題

問題設定: アイテムが分割不可能なナップサック問題

貪欲戦略の失敗例:

• 容量10のナップサック
• アイテムA：価値10、重量10
• アイテムB：価値9、重量9
• アイテムC：価値9、重量9

価値密度順だとA（1.0）、B（1.0）、C（1.0）で決まらず、重量順だとBとCを選ぶことになり、価値18となる。しかし、Aを選ぶ方が価値10で、この場合は価値密度だけでは判断できない。

最長経路問題

問題設定: グラフにおいて最長の経路を求める問題

貪欲戦略の限界:

• 各ステップで最大重みの辺を選択
• 局所最適が全体最適につながらない
• NP困難問題であり、効率的な解法は知られていない

硬貨問題（特殊な硬貨システム）

通常の硬貨システム: 1円、5円、10円、50円、100円、500円では貪欲法で最適解 特殊な硬貨システム: 1円、3円、4円の硬貨で6円を作る場合

• 貪欲法：4円 + 1円 + 1円 = 3枚
• 最適解：3円 + 3円 = 2枚

貪欲法の実装パターン

ソートベースのパターン

多くの貪欲法問題では、まず適切な基準でデータをソートしてから処理を行います。

一般的な流れ:

1. 問題の性質に応じた比較関数を定義
2. データを貪欲基準に従ってソート
3. ソート済みデータを順次処理
4. 制約条件をチェックしながら解を構築

優先度キューベースのパターン

動的に最適な要素を選択する必要がある場合に使用されます。

一般的な流れ:

1. 優先度キューを初期化
2. 初期状態の要素をキューに追加
3. キューから最優先要素を取り出し
4. 取り出した要素に基づいて新しい要素を生成・追加
5. キューが空になるか条件を満たすまで繰り返し

区間スケジューリングパターン

時間軸上での最適化問題でよく使用されるパターンです。

一般的な流れ:

1. 区間を適切な基準（開始時間、終了時間等）でソート
2. 最初の区間を選択
3. 前に選択した区間と競合しない区間を順次選択
4. すべての区間を検討完了まで繰り返し

競技プログラミングでの貪欲法

よく出題される問題パターン

スケジューリング問題: 活動選択、会議室予約、タスク割り当て 選択問題: アイテム選択、部分集合選択 構築問題: 最小スパニングツリー、最短経路 並び替え問題: ソート、辞書順最小/最大

解法の判断基準

問題の性質を確認:

• 局所最適選択が全体最適につながるか
• 最適部分構造を持つか
• 貪欲選択後の問題が元の問題と同じ構造か

計算量の妥当性:

• 制約条件から必要な計算量を見積もり
• 貪欲法の計算量が制約を満たすか確認

デバッグと検証

小さなテストケース: 手計算で確認可能なサイズで動作確認 境界条件のテスト: 空入力、単一要素、最大サイズ等 反例の確認: 貪欲戦略が失敗する可能性を検討

実世界での応用

資源配分問題

CPU使用率最適化: プロセススケジューリングでの貪欲戦略 帯域幅配分: ネットワーク帯域の効率的配分 予算配分: 限られた予算での最大効果を求める投資判断

経路最適化

カーナビゲーション: リアルタイムでの最短経路計算 配送ルート: 宅配業務での効率的ルート計画 ネットワークルーティング: データパケットの最適経路選択

データ圧縮

ハフマン符号: テキストデータの効率的圧縮 画像圧縮: JPEG等での量子化テーブル最適化 動画圧縮: ビットレート配分の最適化

機械学習

特徴選択: 重要度が高い特徴量から順次選択 決定木構築: 情報利得が最大の分割を貪欲選択 クラスタリング: K-means等での中心点更新

貪欲法の最適化テクニック

データ構造の選択

ソート済み配列: 静的データでの高速アクセス 優先度キュー: 動的な最優先要素取得 Union-Find: グラフ問題での効率的な集合管理 セグメント木: 区間に対する効率的な操作

前処理の活用

累積和: 区間和の高速計算 座標圧縮: 値域が大きい場合の空間効率化 インデックス作成: 検索効率の向上

枝刈りの技法

上界の利用: 理論的上限値による早期終了 実行可能性チェック: 制約違反の早期検出 単調性の利用: 単調性を利用した探索範囲の削減

学習のためのステップ

基礎固め

1. 典型問題の理解: アクティビティ選択、フラクショナルナップサック等
2. 証明手法の習得: 交換論法、先頭滞在性質の理解
3. 実装パターンの習得: ソート、優先度キュー等の基本パターン

応用力の向上

1. 問題変化への対応: 制約条件や目的関数の変更に対する柔軟性
2. 複合問題の解決: 複数の貪欲戦略を組み合わせた問題
3. 近似アルゴリズム: 最適解が困難な問題での近似解法

実践的なスキル

1. 計算量解析: 実装の効率性評価
2. 正当性の論証: アルゴリズムの正しさの証明
3. 実装技術: 効率的で読みやすいコードの作成

まとめ

貪欲法は、その直感的でシンプルなアプローチでありながら、多くの重要な問題で最適解を効率的に求めることができる強力なアルゴリズム設計手法です。「その場その場で最善の選択をする」という人間的な判断プロセスに近い考え方は、理解しやすく実装しやすいという大きな利点があります。

貪欲法を効果的に活用するためには、以下のポイントを理解することが重要です：

適用条件の判断: 貪欲選択性質と最適部分構造を満たす問題の識別 証明手法の習得: 交換論法や先頭滞在性質による正当性の証明 実装パターンの理解: ソートや優先度キューを活用した効率的な実装 限界の認識: 貪欲法が適用できない問題の特徴と代替手法

競技プログラミング、面接対策、実務でのシステム設計において、貪欲法の知識は頻繁に活用される重要なスキルです。基本的な問題から始めて段階的に理解を深め、様々な応用問題にチャレンジすることで、アルゴリズム設計能力を大幅に向上させることができるでしょう。

現代のソフトウェア開発において、効率的なアルゴリズムの設計は競争優位性を生み出す重要な要素です。貪欲法をマスターすることで、複雑な問題に対してもシンプルで効果的な解決策を提案できるエンジニアになることができます。

■らくらくPython塾 – 読むだけでマスター

■プロンプトだけでオリジナルアプリを開発・公開してみた！！

AI駆動開発/生成AIエンジニアコースの開発アプリ紹介

■AI時代の第一歩！「AI駆動開発コース」はじめました！

テックジム東京本校で先行開始。

AI駆動開発/生成AIエンジニアコース（初心者向け）

■テックジム東京本校

「武田塾」のプログラミング版といえば「テックジム」。
講義動画なし、教科書なし。「進捗管理とコーチング」で効率学習。
より早く、より安く、しかも対面型のプログラミングスクールです。

テックジム東京本校

＜短期講習＞5日で5万円の「Pythonミニキャンプ」開催中。

【最速・確実】プログラミング攻略「永田町Pythonミニキャンプ」【5日間で5万円】

＜オンライン無料＞ゼロから始めるPython爆速講座

【無料・オンライン】ゼロからはじめるPython爆速講座

フリーランスボード	20万件以上の案件から、副業に最適なリモート・週3〜の案件を一括検索できるプラットフォーム。プロフィール登録でAIスカウトが自動的にマッチング案件を提案。市場統計や単価相場、エージェントの口コミも無料で閲覧可能なため、本業を続けながら効率的に高単価の副業案件を探せます。フリーランスボード
ITプロパートナーズ	週2〜3日から働ける柔軟な案件が業界トップクラスの豊富さを誇るフリーランスエージェント。エンド直契約のため高単価で、週3日稼働でも十分な報酬を得られます。リモートや時間フレキシブルな案件も多数。スタートアップ・ベンチャー中心で、トレンド技術を使った魅力的な案件が揃っています。専属エージェントが案件紹介から契約交渉までサポート。利用企業2,000社以上の実績。ITプロパートナーズ
Midworks	10,000件以上の案件を保有し、週3日〜・フルリモートなど柔軟な働き方に対応。高単価案件が豊富で、報酬保障制度（60%）や保険料負担（50%）など正社員並みの手厚い福利厚生が特徴。通勤交通費（月3万円）、スキルアップ費用（月1万円）の支給に加え、リロクラブ・freeeが無料利用可能。非公開案件80%以上、支払いサイト20日で安心して稼働できます。Midworks