貪欲法の考え方
最善の一手を選び、後戻りしません
「貪欲法の考え方」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。
貪欲法とは
貪欲法アルゴリズムは、現時点で最善に見える選択を常に取りながら、答えを段階的に組み立てます。後から選択を取り消すことはありません。⚡
最善の一手を選ぶ
その時点で、次の1つだけを考えます。どの選択が局所的に最も役立つでしょうか。選択したら、次の判断に進みます。
後戻りしない
貪欲法は選択を確定し、決して取り消しません
貪欲法が速い理由
貪欲法は各段階で一度だけ判断するため、ソート後の計算量は通常 O(n) または O(n log n) です。この速さが、競技プログラミングでの最大の利点です。
ソートする習慣
貪欲法の解法の多くは、まず要素をソートすることから始めます。順序を明らかにすると、各段階でどの要素を選ぶべきかが見えてきます。
items.sort(key=lambda x: x.cost)貪欲選択性
貪欲法が機能するのは、局所的な最善の選択が、全体として最善の答えの一部にもなる場合だけです。これを貪欲選択性と呼びます。
常に正しいとは限らない
今この場で最善の手を選んでも、全体としては失敗することがあります。異なる額面の硬貨を使う硬貨交換問題は、貪欲法で間違った合計になる典型例です。
証明するかテストする
貪欲法を信頼する前に、交換法による証明で正当性を説明するか、小さな入力に対して全探索と比較するストレステストを行ってください。
交換法による証明
交換による証明では、貪欲法の選択を最適解に組み込み、結果が悪化しないことを示します。これが成り立てば、貪欲法を安全に使えます。
小さな貪欲ループ
ほぼすべての貪欲法に共通する形は、ソートしてから1回走査し、ルールに合うものを選ぶことです。
items.sort()
for x in items:
if fits(x):
take(x)貪欲法を使う場面
選択肢を順位付けできる明確な順序があり、1つのルールが常に有効なら、貪欲法を試してください。選択同士が複雑に影響し合う場合は、DP を検討しましょう。
クイックチェック
貪欲法のアプローチを信頼できるかどうか判断したいとします。
まとめ
貪欲法は、通常は最初にソートしたうえで、最善の局所的な選択を行い、後戻りしません。高速ですが、貪欲な選択が成り立つことを証明できる場合にのみ正しく機能します。🚀
よくある質問
「貪欲法の考え方」レッスンは無料ですか？
はい。「貪欲法の考え方」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。
「貪欲法の考え方」で何を学びますか？
最善の一手を選び、後戻りしません ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Competitive Programming Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。
「貪欲法の考え方」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCompetitive Programming Academyレッスンでコードを書いて実行できますか？
はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。