貪欲法とDP：使い分け
貪欲選択性質と交換論法を使って、貪欲法で解ける問題とDPが必要な問題の特徴を見分けます。
「貪欲法とDP：使い分け」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
貪欲法とDPの概要
貪欲法と動的計画法は、どちらも最適化問題、つまり最大値、最小値、または最適な構成を求める問題を解決します。貪欲法は、過去の決定を見直さず、各ステップで局所的に最適な選択を行います。DPはすべての可能性を探索しますが、メモ化によって再計算を避けます。どちらを適用すべきかを理解していれば、誤った貪欲法や、必要以上に複雑なDPテーブルのデバッグに何時間も費やさずに済みます。
# Greedy: always take the locally best option
# Example: coin change with coins [1, 5, 10, 25]
# Greedy: take as many 25s as possible, then 10s, etc.
# This works for standard denominations but NOT all coin sets!
# DP: explore all possibilities via memoisation
# Example: coin change with coins [1, 3, 4] and target 6
# Greedy would pick 4, then 1, 1 → 3 coins
# DP finds: 3 + 3 → 2 coins (optimal!)
print('Greedy can fail when local optimum != global optimum')貪欲選択性
問題が貪欲選択性を持つとは、局所的に最適な（貪欲な）選択を行うことで、常に全体最適解を構成できることです。形式的には、最適解の中に貪欲な選択から始まるものが存在するため、バックトラッキングは必要ありません。これを証明するには通常、交換論法を使います。任意の最適解が貪欲な選択を含まないと仮定し、その選択を入れ替えても解が悪化しないことを示します。
# Exchange argument example: Activity Selection
# Greedy: always pick the activity that ends earliest
# Proof: suppose optimal solution starts with activity A (not earliest-ending)
# Let G be the earliest-ending activity.
# Replace A with G in the solution:
# - G ends no later than A, so G does not conflict with any activity A allowed
# - The solution remains valid with at least as many activities
# Therefore greedy choice (earliest end) is always safe.
activities = [(1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11), (8,12), (2,14)]
activities.sort(key=lambda x: x[1]) # sort by end time
print('Sorted by end:', activities[:4], '...')最適部分構造
貪欲法とDPはどちらも最適部分構造を必要とします。つまり、全体問題の最適解が、部分問題の最適解を含むという性質です。両者の違いは、部分問題の最適解をすべての選択肢を調べずに貪欲に決められるか、それとも複数の選択肢を比較する必要があるかです。選択を行った後の部分問題の構造が同じなら、貪欲法が機能します。複数の選択肢を比較する必要があるなら、DPを使います。
# Greedy works: activity selection
# Making the greedy choice (earliest-ending) leaves a sub-problem
# that is structurally identical (activity selection on remaining activities)
# and the greedy choice for the sub-problem is still valid.
# DP needed: 0/1 knapsack
# After choosing to include/exclude item i, the remaining sub-problem
# depends on WHICH item we chose — different choices yield different sub-problems.
# No single greedy rule works for all inputs.
print('Greedy: sub-problem is unique after each choice')
print('DP: sub-problem depends on which choice was made')部分問題の重複はDPの合図
再帰的な分解の中で同じ部分問題が複数回解かれる場合は、メモ化を使うDPが必要です。再帰木を描き、繰り返し現れるノードを探してください。フィボナッチ数列では、fib(5) の再帰木の中で fib(3) が2回計算されます。コイン交換問題で硬貨が[1,3,4]、目標値が6の場合、目標値3、2、1の部分問題が複数回現れます。部分問題の重複と最適部分構造がそろえば、DPを使います。
# Recursion tree for coin change [1,3,4], target=6
# bt(6) → bt(5) → bt(4) → bt(3) (repeated!)
# → bt(2) → bt(1) (repeated!)
# → bt(3) (repeated!)
# → bt(2) (repeated!)
# Without memoisation: exponential time
# With DP table: O(target * len(coins)) time
def coin_change_dp(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for a in range(1, amount + 1):
for c in coins:
if c <= a:
dp[a] = min(dp[a], dp[a - c] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
print(coin_change_dp([1, 3, 4], 6)) # 2 (3+3)
print(coin_change_dp([2], 3)) # -1 (impossible)古典的な貪欲法の問題
貪欲法が正しいことを証明できる問題には、次のものがあります。(1) アクティビティ／区間スケジューリング — 終了時刻が最も早いものを選ぶ貪欲法です。(2) 最小全域木 — Prim法とKruskal法です。(3) ハフマン符号化 — 頻度が最も低い2つのノードを常に結合します。(4) 分割可能ナップサック — 価値/重量比が最も高い順にアイテムを選びます。(5) Jump Game — 到達可能な最大のインデックスを追跡します。これらはすべて、交換論法によって正しさを証明できます。
# Fractional Knapsack: greedy works
def fractional_knapsack(items, capacity):
# Sort by value/weight ratio descending
items.sort(key=lambda x: x[1]/x[0], reverse=True)
total = 0
for weight, value in items:
if capacity <= 0: break
take = min(weight, capacity)
total += take * (value / weight)
capacity -= take
return total
items = [(10, 60), (20, 100), (30, 120)] # (weight, value)
print(fractional_knapsack(items, 50)) # 240.0
# 0/1 Knapsack: greedy FAILS
# Must use DP (can't take fractions)貪欲法が失敗する場合：反例
反例を見つけることは、貪欲法の仮説を否定する最も速い方法です。硬貨が[1, 3, 4]、目標値が6のコイン交換問題では、貪欲法（大きい硬貨から選ぶ）は4、次に1+1を選び、3枚になります。DPなら3+3で2枚です。0/1ナップサックでは、比率に基づく貪欲法は最も比率のよいアイテムを選びますが、容量をより有効に満たす組み合わせを見逃す場合があります。1分以内に反例を構成できるなら、DPに切り替えてください。
# Counterexample: coin change with non-standard coins
def greedy_coins(coins, amount):
coins.sort(reverse=True)
count = 0
for c in coins:
while amount >= c:
amount -= c
count += 1
return count if amount == 0 else -1
def dp_coins(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for a in range(1, amount + 1):
for c in coins:
if c <= a: dp[a] = min(dp[a], dp[a-c] + 1)
return dp[amount] if dp[amount] < float('inf') else -1
coins, target = [1, 3, 4], 6
print('Greedy:', greedy_coins(coins[:], target)) # 3 (4+1+1)
print('DP: ', dp_coins(coins, target)) # 2 (3+3)比較表：貪欲法とDP
主な違いを並べて比較します。時間計算量 — 貪欲法は通常 O(n log n)（主にソートが支配的）で、DPは O(n × states) です。空間計算量 — 貪欲法の補助領域は O(1)、DPは O(states) です。正しさ — 貪欲法には証明が必要ですが、DPは状態と漸化式が正しければ常に正しい結果になります。適用範囲 — 貪欲法はスケジューリング、全域木、ハフマン符号化に、DPはナップサック、配列アラインメント、負の重みを持つ最短経路に適しています。
# Performance comparison
import time
def time_it(func, *args):
start = time.time()
result = func(*args)
return result, time.time() - start
# Large coin change test
coins = [1, 5, 10, 25, 100]
amount = 10000
def dp_coins(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for a in range(1, amount + 1):
for c in coins:
if c <= a: dp[a] = min(dp[a], dp[a-c]+1)
return dp[amount]
result, elapsed = time_it(dp_coins, coins, amount)
print(f'DP coin change(amount={amount}): {result} coins in {elapsed:.4f}s')判断フレームワーク
面接での判断フローチャートです。(1) 交換論法によって貪欲選択性を証明できますか。はい → 貪欲法です。(2) 部分問題が重複しますか（同じ状態に複数の経路で到達しますか）。はい → DPです。(3) 問題はすべての解を数える、または列挙することを求めていますか。→ DPまたはバックトラッキングです。(4) 自然な順序を持つ単一の最適値を求めていますか。貪欲法を疑ってください。(5) 迷ったらDPを実装してください。漸化式が正しければ、遅くても常に正しい結果になります。
# Decision questions to ask:
questions = [
'1. Is there a natural ordering (by time, ratio, size)?',
'2. Does making the greedy choice leave a smaller same-type problem?',
'3. Can I construct a counterexample quickly?',
'4. Are sub-problems reused across different choice sequences?',
'5. Does the problem involve counting or listing (not just optimising)?',
]
for q in questions:
print(q)
print()
print('Greedy signals: scheduling, spanning tree, Huffman, jump game')
print('DP signals: knapsack, edit distance, LCS, coin change (general)')区間問題：貪欲法とDP
区間問題は、貪欲法を使うものとDPを使うものに分かれます。重ならない区間（削除数を最小化する場合）では、終了時刻でソートして区間を貪欲に選ぶと、貪欲法が最適であることを証明できます。重み付き区間スケジューリング（重みの合計を最大化する場合）では、重い区間が多数の軽い区間と重なる可能性があるため、すべての有効な部分集合を比較する必要があり、DPを使います。区別するポイントは、すべての区間の重みが同じか（貪欲法）、重みが異なるか（DP）です。
# Non-overlapping intervals: greedy works
def erase_overlap_intervals(intervals):
if not intervals: return 0
intervals.sort(key=lambda x: x[1])
count = 0
last_end = float('-inf')
for start, end in intervals:
if start >= last_end:
last_end = end # keep this interval
else:
count += 1 # remove this interval
return count
print(erase_overlap_intervals([[1,2],[2,3],[3,4],[1,3]])) # 1
print(erase_overlap_intervals([[1,2],[1,2],[1,2]])) # 2問題のシグナルを見抜く
問題文によく現れるシグナルには、次のようなものがあります。「操作回数の最小値」、「最大利益」、「最適な選択」 → 貪欲法またはDPの可能性があるため、重複を確認します。「方法の数を数える」 → 常にDPです。「有効なスケジュールを1つ見つける」 → 貪欲法の可能性があります。「すべての可能性」 → バックトラッキングです。「隣接するものは選べない」 → DPです（House Robber）。「会議、区間、タスク」 → 貪欲法である可能性が高いです。シグナルをアルゴリズムの系統に対応付けると、面接問題の診断をすばやく行えます。
# Signal-to-algorithm mapping
signals = {
'minimum steps/coins/operations': 'DP (unless trivially greedy)',
'maximum profit/value with constraint': 'DP (knapsack family)',
'count ways to reach/achieve': 'DP (always)',
'all combinations/permutations': 'Backtracking',
'schedule tasks within time': 'Greedy (sort by deadline/end)',
'cannot pick adjacent': 'DP (house robber pattern)',
'free to pick any subset': 'DP or Greedy (check overlap)',
'interval merging/selecting': 'Greedy (sort by end time)',
}
for signal, algo in signals.items():
print(f'{signal!r}: → {algo}')貪欲法の正しさの証明
貪欲アルゴリズムの正しさを証明するには、交換論法を使います。(1) 貪欲解Gと最初の選択が異なる最適解OPTがあると仮定します。(2) 目的関数の値を悪化させずに、OPTに貪欲な選択を入れ替えられることを示します。(3) 数学的帰納法により、貪欲解がどの最適解にも劣らないことを示します。面接では完全な証明までは必要ありませんが、交換論法の直感を説明できれば、深い理解を示せます。
# Exchange argument demo: earliest-finish-time activity selection
# Suppose OPT starts with activity A (not earliest-ending)
# Let G = earliest-ending activity available
# A.end >= G.end (G ends earlier or same time)
# Swap A for G in OPT:
# - G.end <= A.end, so G does not conflict with anything A allowed after it
# - OPT remains valid with the same number of activities
# - Repeat: after swap, OPT begins with G, matching greedy first choice
# By induction, OPT can be transformed to match G activity by activity
# without losing activities → greedy is optimal
print('Exchange argument: any OPT can be modified to match Greedy without loss')
print('This proves Greedy >= OPT in objective value')理解度チェック
このレッスンで学んだData Structures & Algorithms — Coding Interview Prepの概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、貪欲選択性が成り立つ場合、貪欲法は正しく、交換論法によって証明できること、部分問題が重複し（同じ部分問題に複数の経路で到達し）、1つの貪欲なルールでは解決できない場合はDPが必要になること、そして貪欲法の仮説を否定する最も速い方法は、標準的でない入力で反例を構成することを学びました。次は、終了時刻でソートする貪欲法のアプローチを使って、区間スケジューリングと区間のマージを解きます。
よくある質問
「貪欲法とDP：使い分け」レッスンは無料ですか？
はい。「貪欲法とDP：使い分け」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「貪欲法とDP：使い分け」で何を学びますか？
貪欲選択性質と交換論法を使って、貪欲法で解ける問題とDPが必要な問題の特徴を見分けます。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。
「貪欲法とDP：使い分け」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。