貪欲法（Greedy）とは｜競技プログラミング初心者向けにわかりやすく解説

貪欲法（Greedy）とは

貪欲法（Greedy Algorithm、グリーディ）は、「その場その場で一番得な選択をし続ける」アルゴリズムです。

「貪欲」というと欲張りで悪いイメージですが、競技プログラミングではほめ言葉です。先のことは考えず、今この瞬間に一番良さそうな選択肢を選ぶだけで、不思議と全体の最適解が得られる——というシチュエーションが結構あって、その性質をうまく使うのが貪欲法です。

貪欲法のいいところは、実装が短くて速いことです。動的計画法（DP）のように表を埋めなくてもよいし、全探索のようにすべてのパターンを試す必要もありません。「その場で一番いい選択肢」を順番に取っていくだけで、答えが出てしまいます。

ただし、いつでも貪欲法で正解できるわけではないのが厄介なところで、「この問題は貪欲で解いていいのか？」を見極められるかどうかが、貪欲法を使いこなすカギになります。

まずはイメージから：おつりの硬貨問題

貪欲法の考え方は、次のような身近な問題を考えるとわかりやすいです。

500円・100円・50円・10円・5円・1円の硬貨が無限にある。N 円のおつりを、できるだけ少ない枚数で支払いたい。何枚必要か？

例えば N = 730 円なら、どう払うのが少ない枚数で済むでしょうか？

直感的には、**「大きい硬貨から先に使う」**のが良さそうです。実際にやってみましょう。

1. 500円玉を 1 枚使う → 残り 230 円
2. 100円玉を 2 枚使う → 残り 30 円
3. 10円玉を 3 枚使う → 残り 0 円

合計 6 枚で支払えました。

この「大きい硬貨から優先して使う」というのが、まさに貪欲法の考え方です。「先のことを考えず、今その瞬間に一番大きい硬貨を使う」だけで、最少枚数が達成できているのです。

落とし穴：硬貨の種類が変わると…？

ところが、硬貨の種類が [1円, 4円, 5円] だけだったらどうでしょう？

N = 8 円を払いたいとき、貪欲法で「大きい硬貨から使う」と、

1. 5円玉 1 枚 → 残り 3 円
2. 1円玉 3 枚 → 残り 0 円

で 4 枚になります。でも、本当の最少は 2 枚です（4円玉 × 2 枚）。

つまり、貪欲法はいつでも正解とは限りません。硬貨の種類によっては、先のことを考えずに大きい順に使うと損をするケースがあるのです。

「貪欲で解けるか？」を考えるときは、**「今の選択が後の最適解を壊さないか？」**を意識する必要があります。これが貪欲法の最大のポイントです。

典型例：区間スケジューリング問題

貪欲法の典型問題として、もう一つ有名なのが区間スケジューリング問題です。

1 つの会議室があり、N 個の会議の希望が来ている。会議 i は時刻 s[i] に始まり時刻 t[i] に終わる。会議は重ねて開けない。できるだけ多くの会議を開くには、どれを採用すればよいか？

直感的には、いくつか作戦が思いつきます。

• 作戦 A：早く始まる会議から選ぶ
• 作戦 B：短い会議から選ぶ
• 作戦 C：早く終わる会議から選ぶ

正解は 作戦 C：早く終わる会議から選ぶ です。

なぜ「早く終わる順」なのか

ある会議を選ぶと、その終了時刻以降しか次の会議は開けません。だから、できるだけ早く終わる会議を選んでおけば、残り時間がたくさん残り、その先により多くの会議を詰め込めます。

これが「今、一番得な選択（早く終わる会議を取る）をし続ければ、全体の最適解になる」という貪欲法の典型的な構図です。

C++ での実装

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<pair<int, int>> meetings(N); // (終了時刻, 開始時刻)
    for (int i = 0; i < N; i++) {
        int s, t;
        cin >> s >> t;
        meetings[i] = {t, s}; // 終了時刻を先頭に
    }

    // 終了時刻が早い順にソート
    sort(meetings.begin(), meetings.end());

    int count = 0;
    int last_end = 0; // 直前に選んだ会議の終了時刻
    for (auto [t, s] : meetings) {
        if (s >= last_end) { // 直前の会議が終わってから始まるなら採用
            count++;
            last_end = t;
        }
    }

    cout << count << endl;
    return 0;
}

ポイントは 2 つです。

1. 終了時刻でソートしてから順に見る
2. 直前に選んだ会議の終了時刻以降に始まる会議だけを採用

ソートの計算量が支配的なので、全体で O(N log N) で解けます。N が 10 万を超えても一瞬です。

貪欲法が成立する条件

ここまでで見たように、貪欲法は「ハマる問題」と「ハマらない問題」があります。一般論として、貪欲法が正しく動くには次の条件が必要です。

今のステップで一番得な選択をしても、それより後の選択を最適にする余地が残っていること。

これを言い換えると、「今、目の前の最善を取ったときの解 ≧ それ以外の選び方の解」が常に成り立つ、ということです。逆に言えば、「今の最善が、後で振り返ると損だった」というケースがあると、貪欲法は失敗します。

実戦では、「貪欲で解けそうだな」と思ったら、まず小さい反例で試すのが大事です。

• ランダムな小さいケースを 5〜10 個作って、貪欲解と全探索（または DP）の解を比べる
• 一致しないケースが出たら、その問題は貪欲では解けない

これを習慣にしておくと、コンテスト本番で**「貪欲だと思って書いたら WA」**という事故を減らせます。

計算量：貪欲法はなぜ速いのか

貪欲法の計算量は、多くの場合「ソート + 1 回のループ」で決まります。

処理	計算量
入力をソート	O(N log N)
順に処理する	O(N)
合計	O(N log N)

DP のように表を埋めることもなく、全探索のように指数時間にもならないので、N が 10 万・100 万でも余裕で間に合うのが貪欲法の強みです。

「速いけど正しいとは限らない」アルゴリズムなので、正しさの確認とセットで使う、というのが鉄則です。

典型問題と問題演習

貪欲法を使う典型問題としては、

• 区間スケジューリング問題：終了時刻でソートして取る
• おつりの硬貨問題（硬貨の種類が「都合のいい」場合）：大きい硬貨から使う
• 作業の順序付け：締め切り・所要時間でソートして処理する
• 辞書順最小を作る系の問題：先頭から最小の文字を貪欲に選ぶ
• クッキー配りなどのマッチング系：両方をソートして近い順に組む

など、ソートしてから順に見るだけで解ける問題が多いのが特徴です。**「実際にこういう問題を解いてみたい！」**という方は、ぜひ記事末尾のHaruCoder の無料体験から挑戦してみてください。難易度順に問題が並んでいるので、段階的にレベルアップできます。

つまずきやすいポイント

1. 「これ貪欲で解けそう」を信じすぎる

これが一番の落とし穴です。冒頭の硬貨問題のように、直感的には貪欲で行けそうに見えるのに、実は反例があるパターンは多いです。

✅ 貪欲だと思ったら、必ず小さい反例で確認する
❌ 「なんとなく貪欲で行けそう」で実装に入る

特に「最大化／最小化」を求める問題では、全探索や DP で書ける小さいケースを併用して、ランダムテストで一致するかを確認するのが安全です。

2. ソートの基準を間違える

貪欲法は「何でソートするか」で答えが大きく変わります。区間スケジューリングの例で見たように、「早く始まる順」と「早く終わる順」では結果が違います。

問題を読んだら、まず「何を最大化／最小化したいか？」を明確にして、そのために何の順で見ると後悔しないかを考えるクセを付けましょう。

3. 同点（タイ）の処理を忘れる

ソートしたときに、同じ値が複数あるケースを考えていないと、たまに WA になります。例えば「終了時刻が同じ会議が 2 つある場合、どちらを先に選ぶ？」のような場面です。

多くの問題では「同点のときはどちらでもよい」のですが、条件付きの貪欲法では同点の処理が答えに影響することがあるので、コーナーケースとして必ず確認しましょう。

4. 証明を後回しにしすぎる

「動けばよし」で貪欲法を書くと、後でハマることがあります。練習段階では、

• 交換論法：最適解の中で「貪欲が選ぶ方」と「選ばない方」を入れ替えても解の質が落ちないことを示す
• 帰納法：「k 番目までは貪欲が最適」を仮定して、「k+1 番目も最適」が示せれば OK

といった正しさの説明を、ノートに 2〜3 行でいいので書いてみると、貪欲法の感覚が早く身につきます。

まとめ

貪欲法のポイントをもう一度整理しておきましょう。

• その場で一番得な選択をし続けるアルゴリズム。実装が短く、計算量も O(N log N) 程度で速い
• ソート + 1 回のループで書けることが多く、典型問題は決まったパターンに落ちる
• いつでも正しいとは限らない。「今の最善が後の最適を壊さないか」を必ず吟味する
• 怪しいときは、小さいケースでの反例チェックやDP との比較で正しさを確認する

貪欲法は「正しく使えれば最強、間違えれば WA」という、ちょっとクセのあるアルゴリズムですが、JOI 一次予選・二次予選でも頻出で、知っているだけで一気に解ける問題が増えます。ぜひマスターしてください。

練習問題に挑戦しよう

アルゴリズムは「読んで理解した」だけでは使えるようになりません。実際に自分の手で書いて、問題を解くことで初めて身につきます。

HaruCoder のオンライン受講では、貪欲法を使う問題を難易度順に用意しており、提出すれば自動で採点されます。「次に何を解けばいいかわからない」という悩みもなく、段階的にステップアップできます。

また、まだ競技プログラミングを始めたばかりで「そもそもどうやって問題を解くの？」という方は、先に以下の記事を読んでみてください。

• 競技プログラミングの始め方 — ブラウザだけで 1 問解く流れを画像付きで解説
• JOIの難易度全解説 — 貪欲法が実際に役立つコンテストの全体像