Belajar Algoritm - Paradigma Desain Algoritma (Overview)

#Pendahuluan

Setelah di episode 2 kita menguasai asymptotic analysis dan Master Theorem, pada episode ini kita menarik pandangan ke atas dan memahami paradigma desain algoritma — kerangka berpikir yang menentukan bagaimana kita mendekati sebuah masalah. Memilih paradigma yang tepat sama pentingnya dengan menulis kode yang benar.

Mengapa paradigma penting? Karena masalah yang sama bisa diselesaikan dengan banyak cara. Sebuah masalah bisa di-brute-force (lambat tapi benar), bisa di-greedy (cepat tapi belum tentu optimal), atau di-dynamic-programming (optimal tapi butuh lebih banyak memori). Memahami kapan menggunakan paradigma mana adalah keterampilan inti seorang algorithm engineer.

#Enam Paradigma Utama

#1. Brute Force

Brute force adalah pendekatan paling dasar: coba semua kemungkinan solusi, lalu pilih yang terbaik. Ia selalu menghasilkan solusi yang benar, tetapi biasanya terlalu lambat untuk input besar.

# Brute force: cari pasangan dengan jumlah target
def two_sum_brute(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

Brute force adalah baseline — tolak ukur untuk membandingkan algoritma yang lebih canggih. Jika kalian tidak bisa menulis brute force, kalian belum memahami masalahnya.

#2. Divide & Conquer

Divide & conquer memecah masalah menjadi sub-masalah yang lebih kecil, menyelesaikan masing-masing secara rekursif, lalu menggabungkan hasilnya. Kunci: sub-masalah harus independen.

Contoh: merge sort (bagi array, sort masing-masing, merge), binary search (bagi search space, tentukan sisi mana).

#3. Greedy

Greedy membuat pilihan lokal optimal di setiap langkah dengan harapan menghasilkan global optimal. Tidak ada retrospeksi — keputusan yang sudah diambil tidak diubah.

Contoh: activity selection (pilih aktivitas yang selesai paling awal), fractional knapsack (ambil item berdasarkan rasio value/weight).

#4. Dynamic Programming

Dynamic programming (DP) adalah generalisasi dari divide & conquer untuk masalah dengan overlapping subproblems — sub-masalah yang sama dihitung berulang kali. DP menyimpan hasil di memo atau tabel agar setiap sub-masalah hanya dihitung sekali.

# Fibonacci dengan DP (memoization)
def fib(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

Tanpa memo, fib(n) membutuhkan Ω(2ⁿ) waktu. Dengan memo, ia menjadi Θ(n) — penghematan eksponensial.

#5. Backtracking

Backtracking mengeksplorasi semua kemungkinan solusi secara sistematis: pilih satu opsi, eksplorasi ke depan, lalu undo (backtrack) jika opsi tersebut tidak mengarah ke solusi. Ini seperti DFS pada pohon keputusan.

Contoh klasik: N-Queens (tempatkan ratu satu per satu, backtrack jika konflik), Sudoku solver, generate semua permutasi.

#6. Randomized

Randomized algorithms menggunakan keacakan (random number) sebagai bagian dari logikanya. Ada dua kategori:

• Las Vegas: selalu benar, waktu eksekusi random (misal QuickSort dengan random pivot — selalu menghasilkan array terurut, tetapi waktu bervariasi).
• Monte Carlo: waktu tetap, hasilnya mungkin salah dengan probabilitas kecil (misal Miller-Rabin primality test).

#Pola Pikir: Memilih Paradigma yang Tepat

Pertanyaan kunci saat menghadapi masalah baru:

1. "Apa struktur masalah?" — Apakah ada overlapping subproblems? → DP. Apakah bisa dipecah independen? → Divide & conquer. Apakah ada greedy choice property? → Greedy.
2. "Apakah brute force bisa diterima?" — Jika input kecil (< 20), brute force mungkin cukup.
3. "Apakah ada constraint yang bisa dimanfaatkan?" — Input terurut? → Binary search. Input terbatas range? → Non-comparison sort. Graph? → BFS/DFS.

#Praktik: Klasifikasikan 10 Masalah

Coba klasifikasikan masalah berikut ke paradigma yang paling tepat:

#Penutup

Pada episode 3 ini, kalian telah memahami:

• Enam paradigma: brute force, divide & conquer, greedy, dynamic programming, backtracking, randomized.
• Pola pikir memilih: struktur masalah → constraint → paradigma.
• Brute force adalah baseline; greedy butuh bukti; DP untuk overlapping subproblems; backtracking untuk eksplorasi sistematis.

Di episode 4 selanjutnya kita mulai FASE 2: SORTING — membahas Insertion Sort, Selection Sort, dan Merge Sort dengan implementasi, analisis, dan benchmark. Pastikan pemahaman paradigma kalian sudah solid, karena sorting adalah arena pertama kita menerapkannya secara konkret. Sampai jumpa di episode 4!