Apa itu algoritma greedy, dan kapan mereka bekerja?

Question

Accepted Answer

Sebuah **algoritma greedy** membuat **pilihan optimal secara lokal** di setiap langkah, berharap mengarah ke optimum global. Algoritma ini sederhana dan cepat, tetapi hanya benar ketika masalah memiliki **properti pilihan greedy** dan **substruktur optimal**.

## Idenya

Jangan pernah mempertimbangkan kembali pilihan masa lalu — berkomitmen pada opsi terbaik langsung dan lanjutkan.

## Contoh: pertukaran koin dengan koin kanonik

```python
def greedy_coins(amount, coins=(25, 10, 5, 1)):
    result = []
    for coin in coins:                 # largest first
        while amount >= coin:
            amount -= coin             # take as many as possible
            result.append(coin)
    return result

greedy_coins(36)                       # -> [25, 10, 1]
```

Ini optimal untuk koin US, tetapi **gagal** untuk himpunan seperti {1, 3, 4} di mana greedy memberikan 4+1+1 untuk 6 daripada 3+3.

## Kapan greedy bekerja

- **Substruktur optimal:** solusi optimal berisi sub-solusi optimal.
- **Properti pilihan greedy:** optimum lokal adalah bagian dari optimum global.

Contoh yang bekerja: Dijkstra, Kruskal/Prim (MST), pengkodean Huffman, penjadwalan interval.

## Kompleksitas

Biasanya cepat — sering O(n log n) setelah penyortiran.

## Jebakan

Greedy **tidak selalu benar**. Buktikan properti pilihan greedy atau uji terhadap baseline brute-force/DP sebelum mempercayainya.

## Mengapa ini penting

Ketika greedy berlaku, itu jauh lebih sederhana dan lebih cepat daripada DP atau brute force.

Mengetahui *kapan* itu valid — dan kapan itu secara diam-diam memberikan jawaban yang salah — adalah tanda dari kedewasaan algoritma.

Banyak algoritma grafik dasar adalah greedy pada intinya.