Algoritma Greedy pert 2

Greedy vs Algoritma Lain: Kapan Harus Dipilih?

Setiap algoritma punya karakter masing-masing. Greedy itu seperti “jalan pintas”. Kadang berhasil, kadang gagal total. Jadi gimana membedakan kapan harus pakai Greedy, Dynamic Programming, atau Divide & Conquer?

✔ Greedy vs Dynamic Programming (DP)

Greedy:

• pilihan terbaik untuk saat ini
• tidak memikirkan masa depan
• super cepat

Dynamic Programming:

• mempertimbangkan semua pilihan
• mesti simpan hasil sub-masalah
• lebih lambat tetapi pasti optimal

Kalau masalahnya butuh keputusan yang benar-benar optimal, dan terdapat hubungan antar submasalah, DP hampir selalu lebih tepat. Tapi kalau masalah punya sifat greedy-choice, ya greedy jauh lebih efektif.

 

---

✔ Greedy vs Divide and Conquer

Divide & Conquer: memecah masalah jadi beberapa bagian, selesaikan masing-masing bagian, lalu gabungkan.

Contohnya:

• Merge Sort
• Quick Sort
• Binary Search

Greedy tidak memecah masalah. Dia langsung memilih. Divide and Conquer cocok buat pencarian dan pengurutan, bukan optimasi. Greedy cocok buat optimasi lokal.

---

Studi Kasus Lengkap: Greedy Dalam Kehidupan Nyata

Di bagian ini, kita akan bahas beberapa contoh yang benar-benar terjadi dalam dunia industri, penelitian, dan kehidupan sehari-hari. Tujuannya biar kamu makin paham bahwa Greedy itu bukan hanya teori di kelas, tapi benar-benar dipakai.

---

📌 Studi Kasus 1: Aplikasi Ride-Hailing (Grab/Gojek)

Pernah pesan ojek atau mobil online? Aplikasi harus memilih driver terdekat untuk efisiensi waktu. Pilihan “driver terdekat” adalah keputusan greedy.

Alurnya:

1. dari semua driver, pilih yang jaraknya paling dekat
2. berikan pesanan ke driver tersebut
3. selesai

Apakah ini selalu optimal? Tidak selalu, tapi cukup optimal dan sangat cepat. Karena kalau aplikasi sampai menghitung semua kemungkinan rute untuk mencari keputusan “paling optimal”, server bisa jebol. Itulah alasan greedy dipakai.

---

📌 Studi Kasus 2: Kompresi File (Huffman Coding)

Saat kamu meng-compress file ZIP, sistem menggunakan Huffman Encoding — sebuah algoritma terkenal yang memakai teknik greedy.

Tujuannya: membuat kode paling pendek untuk karakter yang paling sering muncul.

Misalnya huruf “e” muncul paling banyak → dikasih kode paling pendek. Huruf “z” jarang muncul → dikasih kode lebih panjang.

Huffman selalu memilih dua node dengan frekuensi terkecil (keputusan lokal) untuk digabungkan menjadi node baru. Itu pendekatan greedy.

---

📌 Studi Kasus 3: Mengatur Iklan di Media Sosial

Platform seperti Facebook dan TikTok punya algoritma untuk memilih iklan yang ditampilkan ke pengguna. Mereka memakai pendekatan greedy: pilih iklan yang memberikan “skor” tertinggi untuk saat ini.

Ini bukan solusi optimal, tetapi cepat dan efisien untuk skala miliaran pengguna.

---

📌 Studi Kasus 4: Pengisian Baterai Mobil Listrik

Mobil listrik seperti Tesla menggunakan greedy dalam mengatur energi. Misalnya sistem memilih jalur supercharger:

• charger paling dekat
• charger dengan antrian terendah

Sistem tidak menghitung “semua rute terbaik sampai 1000 km ke depan”. Itu terlalu berat. Greedy cukup.

---

Contoh Implementasi Greedy (Dengan Pseudocode + Flowchart)

Kita ambil contoh paling populer: Activity Selection Problem.

Tujuan: pilih kegiatan sebanyak mungkin yang tidak bentrok.

Langkah Greedy:

1. Urutkan kegiatan berdasarkan waktu selesai
2. Pilih kegiatan yang selesai paling cepat
3. Ambil kegiatan berikutnya yang mulai setelah kegiatan sebelumnya selesai

---

Pseudocode Lengkap

START
Sort activities by finish time
Select first activity
last_finish = finish time of first activity

FOR each activity i:
    IF start[i] >= last_finish:
        select activity i
        last_finish = finish[i]
END FOR

PRINT selected activities
END

---

Flowchart Deskripsi (teks)

• Mulai
• Input daftar kegiatan
• Urutkan berdasarkan waktu selesai
• Pilih kegiatan pertama
• Perulangan: cek kegiatan berikutnya
• Jika waktu mulai lebih besar/sama → ambil
• Jika tidak → lewati
• Ulangi sampai habis
• Selesai

---

Implementasi Greedy dalam Kode (Python)

activities = [(1,4), (3,5), (0,6), (5,7), (8,9)]

# Sort by finish time
activities.sort(key=lambda x: x[1])

selected = []
selected.append(activities[0])
last_finish = activities[0][1]

for act in activities[1:]:
    if act[0] >= last_finish:
        selected.append(act)
        last_finish = act[1]

print("Kegiatan terpilih:", selected)

Keluaran:

Kegiatan terpilih: [(1,4), (5,7), (8,9)]

Itu adalah hasil optimal.

---

Latihan Soal Greedy + Pembahasan

Di bawah ini ada beberapa latihan soal yang sering muncul di materi SMA/Kelas XI. Semua lengkap dengan pembahasan gaya santai.

📌 Soal 1 — Koin

Pecahan: 500, 200, 100 Buat nilai 900.

Pembahasan:

• ambil 500 → sisa 400
• ambil 200 → sisa 200
• ambil 200 → sisa 0

Total koin = 3 Greedy berhasil.

---

📌 Soal 2 — Gagalnya Greedy

Pecahan: 4, 3, 1 Nilai: 6

Greedy:

• ambil 4 → sisa 2
• ambil 1 → sisa 1
• ambil 1 → sisa 0

Total = 3 koin

Solusi optimal:

• 3 + 3 = 2 koin

Greedy gagal. Ini contoh yang bagus untuk menjelaskan batasannya.

---

📌 Soal 3 — Jadwal Kegiatan

Kegiatan:

A: 1–2
B: 1–3
C: 3–4
D: 0–6
E: 5–7
F: 8–9

Greedy memilih yang selesai paling cepat:

• A (1–2)
• C (3–4)
• E (5–7)
• F (8–9)

Total 4 kegiatan.

---

Andi Bronnanjar

Kualitas makhluk berdasarkan seberapa manfaat untuk sesama maupun lingkungan alam sekitar.

Bagikan Artikel ini