ALGORITMA GREDY INFORMATIKA SMA

🧠 Algoritma Greedy

Materi Pembelajaran untuk Siswa SMA

📚 Apa itu Algoritma Greedy?

Algoritma Greedy adalah strategi pemecahan masalah yang selalu memilih pilihan terbaik saat ini tanpa mempertimbangkan konsekuensi di masa depan.

🎯 Definisi Formal

Algoritma greedy adalah paradigma algoritma yang membuat pilihan optimal lokal pada setiap langkah dengan harapan menemukan optimum global.

"Greedy" = Serakah → Selalu mengambil yang terbaik yang tersedia saat ini

✅ Kelebihan

• • Sederhana dan mudah dipahami
• • Cepat dalam eksekusi (kompleksitas rendah)
• • Efisien untuk masalah tertentu
• • Tidak memerlukan memori besar
• • Mudah diimplementasikan

⚠️ Kekurangan

• • Tidak selalu memberikan solusi optimal
• • Tidak bisa "mundur" untuk memperbaiki pilihan
• • Hanya cocok untuk masalah tertentu
• • Sulit membuktikan kebenaran solusi
• • Bisa terjebak di optimum lokal

💡 Kapan Menggunakan Greedy?

✅ Cocok untuk:

• • Masalah optimasi sederhana
• • Penjadwalan aktivitas
• • Masalah uang kembalian
• • Minimum spanning tree
• • Huffman coding

❌ Tidak cocok untuk:

• • 0/1 Knapsack problem
• • Traveling salesman problem
• • Masalah dengan dependensi kompleks
• • Optimasi multi-objektif

🎭 Analogi dalam Kehidupan Sehari-hari

🍕 Analogi: Makan di Buffet

Situasi: Kamu di buffet dengan piring terbatas

Strategi Greedy: Selalu ambil makanan yang paling enak/mahal yang terlihat saat ini

Masalah: Mungkin ada makanan lebih enak di ujung yang belum kamu lihat!

Pelajaran: Greedy bagus untuk keputusan cepat, tapi tidak selalu optimal secara keseluruhan.

🚗 Analogi: Perjalanan dengan GPS

Situasi: Mencari jalan tercepat ke tujuan

Strategi Greedy: Di setiap persimpangan, pilih jalan yang mendekatkan ke tujuan

Hasil: Kadang berhasil, kadang malah macet karena tidak melihat kondisi lalu lintas keseluruhan

Pelajaran: Informasi lokal saja tidak cukup untuk keputusan optimal.

🎮 Analogi: Game Strategy

🏆 Greedy Player

Selalu ambil poin terbanyak yang tersedia saat ini

🧠 Strategic Player

Pikirkan beberapa langkah ke depan sebelum memutuskan

📊 Hasil

Greedy: cepat tapi tidak selalu menang. Strategic: lambat tapi lebih optimal

💰 Analogi: Berbelanja dengan Budget Terbatas

Skenario: Kamu punya Rp 100.000 untuk belanja kebutuhan sekolah

Pilihan: Buku (Rp 50.000), Pulpen (Rp 15.000), Penggaris (Rp 10.000), Tas (Rp 80.000)

❌ Pendekatan Greedy Buruk

Ambil yang termahal dulu (Tas Rp 80.000) → Sisa Rp 20.000 → Hanya bisa beli pulpen

Total: 2 barang

✅ Pendekatan Greedy Baik

Prioritas kebutuhan: Buku + Pulpen + Penggaris = Rp 75.000

Total: 3 barang + sisa uang

✨ Karakteristik Algoritma Greedy

1. 🎯 Greedy Choice Property

Pilihan terbaik lokal akan menghasilkan solusi optimal global.

Contoh: Dalam masalah uang kembalian, memilih denominasi terbesar selalu menghasilkan jumlah koin minimum.

2. 🏗️ Optimal Substructure

Solusi optimal dari masalah mengandung solusi optimal dari sub-masalah.

Contoh: Jika solusi optimal untuk kembalian Rp 67.000 menggunakan 4 lembar, maka sub-masalah kembalian Rp 17.000 juga harus optimal.

3. 🚫 No Backtracking

Sekali pilihan dibuat, tidak bisa diubah lagi.

Konsekuensi: Algoritma harus yakin bahwa pilihan saat ini adalah yang terbaik untuk selamanya.

🔍 Cara Mengenali Masalah Greedy

✅ Ciri-ciri Positif:

• • Ada kriteria jelas untuk "pilihan terbaik"
• • Masalah bisa dipecah menjadi sub-masalah
• • Pilihan lokal tidak mempengaruhi pilihan masa depan
• • Ada pola "ambil yang terbesar/terkecil"

❌ Tanda Bahaya:

• • Pilihan saat ini mempengaruhi pilihan masa depan
• • Ada dependensi kompleks antar elemen
• • Perlu mempertimbangkan banyak faktor sekaligus
• • Solusi optimal memerlukan "pengorbanan" sementara

📋 Langkah-langkah Menyelesaikan Masalah Greedy

🎯 Template Umum Algoritma Greedy

1. Inisialisasi solusi kosong

2. Selama masih ada pilihan:

a. Pilih elemen terbaik berdasarkan kriteria greedy

b. Jika elemen valid, tambahkan ke solusi

c. Hapus elemen dari daftar pilihan

3. Return solusi

Langkah 1: 🎯 Tentukan Fungsi Greedy

Definisikan kriteria untuk memilih elemen "terbaik" pada setiap langkah.

Contoh Kriteria Greedy:

• • Uang kembalian: Pilih denominasi terbesar
• • Knapsack: Pilih rasio nilai/berat tertinggi
• • Penjadwalan: Pilih aktivitas yang selesai paling awal
• • Huffman: Pilih frekuensi terkecil

Langkah 2: 🔄 Implementasi Loop Greedy

Ulangi proses pemilihan sampai tidak ada lagi pilihan atau solusi lengkap.

Poin Penting:

• • Pastikan kondisi berhenti yang jelas
• • Validasi setiap pilihan sebelum ditambahkan
• • Update state/kondisi setelah setiap pilihan
• • Jangan lupa handle edge cases

Langkah 3: ✅ Verifikasi Solusi

Pastikan solusi yang dihasilkan benar dan optimal (jika memungkinkan).

Cara Verifikasi:

• • Test dengan contoh kecil yang sudah diketahui jawabannya
• • Bandingkan dengan metode brute force (untuk input kecil)
• • Buktikan secara matematis (untuk masalah yang sudah dikenal)
• • Cek apakah memenuhi semua constraint masalah

💡 Tips Praktis

✅ Do's:

• • Mulai dengan contoh sederhana
• • Gambar/visualisasi proses
• • Test dengan berbagai input
• • Dokumentasi kriteria greedy dengan jelas

❌ Don'ts:

• • Jangan asumsikan greedy selalu optimal
• • Jangan lupa validasi input
• • Jangan mengabaikan edge cases
• • Jangan kompleksitas berlebihan

💰 Contoh: Masalah Uang Kembalian

🎯 Masalah:

Berikan uang kembalian dengan jumlah koin/uang kertas seminimal mungkin.

Strategi Greedy: Selalu pilih denominasi terbesar yang masih bisa digunakan.

🧮 Simulator Uang Kembalian

Jumlah Kembalian (Rupiah):

🤔 Mengapa Greedy Berhasil di Sini?

Karena sistem mata uang dirancang khusus agar strategi "ambil yang terbesar dulu" selalu memberikan hasil optimal. Ini disebut canonical coin system.

⏰ Contoh: Activity Selection (Penjadwalan Aktivitas)

🎯 Masalah:

Kamu punya banyak kegiatan dengan waktu mulai dan selesai yang berbeda. Pilih sebanyak mungkin kegiatan yang tidak bentrok waktu.

Strategi Greedy: Selalu pilih aktivitas yang selesai paling awal dari yang tersisa.

📅 Simulator Penjadwalan

Aktivitas yang Tersedia:

🤔 Mengapa "Selesai Paling Awal"?

Dengan memilih aktivitas yang selesai paling awal, kita:

• Memberikan waktu maksimal untuk aktivitas berikutnya
• Meminimalkan "pemborosan" waktu
• Memaksimalkan peluang memilih lebih banyak aktivitas

Bukti matematis: Strategi ini terbukti selalu menghasilkan jumlah aktivitas maksimum yang mungkin dipilih.

🎒 Contoh: Fractional Knapsack

🎯 Masalah:

Kamu punya tas dengan kapasitas terbatas. Ada beberapa barang dengan berat dan nilai berbeda. Pilih barang untuk memaksimalkan nilai total.

Strategi Greedy: Pilih barang berdasarkan rasio nilai/berat tertinggi.

🎒 Simulator Knapsack

Kapasitas Tas (kg):

Barang yang Tersedia:

⚖️ Perbandingan: Greedy vs Algoritma Lain

🏃‍♂️ Greedy Algorithm

Kecepatan: ⚡⚡⚡

Sangat cepat, kompleksitas rendah

Memori: 💾

Hemat memori

Optimalitas: ⚠️

Tidak selalu optimal

🧠 Dynamic Programming

Kecepatan: ⚡⚡

Lebih lambat dari greedy

Memori: 💾💾💾

Butuh banyak memori

Optimalitas: ✅

Selalu optimal

📊 Contoh Perbandingan: 0/1 Knapsack

Algoritma	Hasil	Waktu	Optimal?
Greedy (rasio nilai/berat)	Nilai: 160	O(n log n)	❌ Tidak
Dynamic Programming	Nilai: 220	O(nW)	✅ Ya
Brute Force	Nilai: 220	O(2^n)	✅ Ya

🎯 Kapan Menggunakan Masing-masing?

🏃‍♂️ Gunakan Greedy jika:

• • Butuh solusi cepat
• • Memori terbatas
• • Solusi "cukup baik" sudah memadai
• • Masalah terbukti cocok untuk greedy

🧠 Gunakan DP jika:

• • Butuh solusi optimal
• • Ada overlapping subproblems
• • Memori cukup tersedia
• • Waktu eksekusi tidak kritis

🔍 Gunakan Brute Force jika:

• • Input sangat kecil
• • Butuh solusi pasti optimal
• • Algoritma lain terlalu kompleks
• • Untuk verifikasi hasil

🎯 Latihan Soal

Soal 1: Penjadwalan Aktivitas

Kamu punya beberapa kegiatan dengan waktu mulai dan selesai. Pilih aktivitas sebanyak mungkin tanpa bentrok waktu.

Aktivitas:

A: 09:00 - 10:30

B: 10:00 - 11:00

C: 11:00 - 12:00

D: 10:30 - 11:30

E: 12:00 - 13:00

F: 11:30 - 12:30

Jawaban:

Strategi: Pilih aktivitas yang selesai paling awal terlebih dahulu.

Hasil: A (09:00-10:30) → C (11:00-12:00) → E (12:00-13:00) = 3 aktivitas

Soal 2: Huffman Coding (Konsep)

Untuk mengompres teks "ABRACADABRA", frekuensi huruf: A=5, B=2, R=2, C=1, D=1. Bagaimana algoritma greedy membantu membuat kode yang efisien?

Penjelasan:

Strategi Greedy: Gabungkan dua node dengan frekuensi terkecil berulang kali.

Huruf yang sering muncul (A) dapat kode pendek, yang jarang (C,D) dapat kode panjang. Ini menghasilkan kompresi optimal!

🧠 Kuis Interaktif

Pertanyaan 1: Konsep Dasar

Apa ciri utama algoritma greedy?

Selalu mencari solusi optimal global Memilih pilihan terbaik saat ini tanpa melihat masa depan Menggunakan rekursi untuk menyelesaikan masalah Menyimpan semua kemungkinan solusi

Pertanyaan 2: Aplikasi Praktis

Untuk masalah uang kembalian Rp 37.000 dengan denominasi [50000, 20000, 10000, 5000, 1000], berapa lembar minimum yang dibutuhkan dengan algoritma greedy?

3 lembar 4 lembar 5 lembar 6 lembar

Pertanyaan 3: Strategi Greedy

Dalam masalah Activity Selection, mengapa kita memilih aktivitas yang "selesai paling awal" bukan yang "mulai paling awal"?

Karena lebih mudah dihitung Karena memberikan waktu maksimal untuk aktivitas berikutnya Karena aktivitas yang mulai awal pasti lebih penting Tidak ada alasan khusus

Pertanyaan 4: Keterbatasan Greedy

Masalah mana yang TIDAK cocok diselesaikan dengan algoritma greedy?

Fractional Knapsack Activity Selection 0/1 Knapsack Huffman Coding

🏆 Skor Anda

Jawab semua pertanyaan untuk melihat skor!

💡 Tips: Algoritma greedy sangat berguna untuk optimasi sederhana, tapi selalu periksa apakah memberikan solusi optimal!

🎓 Selamat belajar! Jangan lupa praktik dengan berbagai contoh soal.