Apa iku algoritma greedy lan kapan bisa gumana?

Question

IT Interview Practice · Accepted Answer

**Algoritma greedy** nggawe **pilihan optimal lokal** ing saben langkah, ngarep-arap yen bakal nuntun menyang optimum global. Simple lan cepet, nanging bener mung nalika masalah duwe **greedy-choice property** lan **optimal substructure**.

## Gagasan

Jangan ngenthok maneh pilihan kuno — komit ing pilihan terbaik saiki lan maju.

## Conto: coin change karo moneter standar

```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]
```

Iki optimal kanggo moneter Amerika Serikat, nanging **gagal** kanggo set kaya {1, 3, 4} kang greedy menehi 4+1+1 kanggo 6 tinimbang 3+3.

## Nalika greedy bisa gumana

- **Optimal substructure:** solusi optimal ngemot sub-solusi optimal.
- **Greedy-choice property:** optimum lokal iki bagean saka optimum global.

Conto kang bisa gumana: Dijkstra, Kruskal/Prim (MST), Huffman coding, interval scheduling.

## Kompleksitas

Biasane cepet — asring O(n log n) sawise sort.

## Jebakan

Greedy **ora mesthi bener**. Buktekno greedy-choice property utawa test lawan brute-force/DP baseline sadurunge percaya.

## Mengapa penting

Nalika greedy cocok, iku luwih simple lan luwih cepet tinimbang DP utawa brute force.

Ngrumangsani *kapan* iku valid — lan kapan kanthi senyap menehi jawaban salah — minangka tandha kematangan algoritma.

Saweg-saweg algoritma grafik inti duwe jantung greedy.

Gagasan

Conto: coin change karo moneter standar

Nalika greedy bisa gumana

Kompleksitas

Jebakan

Mengapa penting

Pitakon sing gegandhengan