Kategori Algoritma

Saat menghadapi masalah komputasi, kita jarang memulai dari kosong. Sebagian besar masalah dapat dipetakan ke salah satu paradigma algoritma yang sudah teruji: brute force, divide and conquer, greedy, dynamic programming, atau backtracking. Pemahaman terhadap paradigma ini memberi kita kerangka berpikir yang konsisten dan mempercepat diagnosis masalah. Pada Chapter ini kita akan memetakan kategori algoritma utama, melihat kapan masing-masing cocok dipakai, dan mendemokan perbandingan dua paradigma pada masalah maximum subarray yang klasik.

Mengapa Perlu Paradigma Algoritma #

Tanpa kerangka berpikir, mendesain algoritma terasa seperti menebak. Paradigma memberi pola umum yang bisa kita ikuti: bagaimana memecah masalah, kapan memilih solusi optimal lokal, kapan menyimpan hasil antara, dan kapan mencoba seluruh kemungkinan. Dengan menguasai beberapa paradigma, kita bisa memilih pendekatan yang tepat sebelum menulis satu baris kode pun.

mindmap root((Paradigma Algoritma)) Brute Force Coba semua kemungkinan Sederhana, sering lambat Divide and Conquer Pecah masalah jadi bagian Gabungkan solusi Greedy Pilih optimal lokal Cepat, tidak selalu optimal global Dynamic Programming Subproblem tumpang tindih Simpan hasil antara Backtracking Jelajah ruang solusi Mundur saat buntu

Brute Force #

Brute force adalah paradigma paling sederhana: coba seluruh kemungkinan solusi lalu pilih yang terbaik. Brute force selalu menghasilkan jawaban yang benar (selama seluruh ruang solusi dijelajahi), tetapi sering kali sangat lambat untuk input besar.

Karakteristik brute force:

Implementasi: langsung dan mudah dipahami.
Kompleksitas: biasanya polinomial tinggi atau eksponensial.
Kegunaan: verifikasi hasil, baseline kinerja, atau ketika n kecil.

Divide and Conquer #

Divide and conquer memecah masalah menjadi submasalah lebih kecil, menyelesaikan tiap submasalah secara rekursif, lalu menggabungkan solusi. Contoh klasik: merge sort, quick sort, dan binary search.

Tiga langkah divide and conquer:

Divide: pecah masalah menjadi submasalah lebih kecil.
Conquer: selesaikan tiap submasalah secara rekursif.
Combine: gabungkan solusi submasalah menjadi solusi akhir.

Greedy #

Greedy memilih langkah yang tampak optimal pada saat itu tanpa mempertimbangkan dampak global. Paradigma ini cepat dan sederhana, tetapi tidak selalu menghasilkan solusi optimal global. Contoh: algoritma Dijkstra untuk jalur terpendek, Huffman coding untuk kompresi data.

Syarat greedy bekerja optimal:

Greedy choice property: pilihan optimal lokal membawa solusi optimal global.
Optimal substructure: solusi optimal masalah mengandung solusi optimal submasalah.

Dynamic Programming #

Dynamic programming (DP) dipakai ketika masalah memiliki overlapping subproblems dan optimal substructure. DP menyimpan hasil submasalah untuk menghindari komputasi berulang. Contoh: Fibonacci, knapsack, longest common subsequence.

Dua pendekatan implementasi DP:

Top-down (memoization): rekursif + cache hasil.
Bottom-up (tabulation): isi tabel dari kasus dasar ke kasus kompleks.

Backtracking #

Backtracking menjelajahi ruang solusi secara sistematis dan mundur ketika jalur yang dipilih terbukti tidak menghasilkan solusi. Contoh: N-Queens, sudoku solver, permutasi dan kombinasi.

Backtracking cocok ketika:

Ruang solusi besar tetapi terstruktur.
Solusi parsial dapat divalidasi lebih awal.
Tidak ada rumus matematis langsung.

Tabel Perbandingan Paradigma #

Paradigma	Strategi	Kompleksitas Tipikal	Kapan Dipakai
Brute force	Coba semua	`O(n!)` atau `O(2ⁿ)`	Verifikasi, `n` kecil
Divide & Conquer	Pecah & gabung	`O(n log n)`	Sorting, FFT, BST
Greedy	Optimal lokal	`O(n log n)`	MST, Huffman, Dijkstra
Dynamic Programming	Subproblem tumpang tindih	`O(n²)` atau `O(n·W)`	Knapsack, LCS, edit distance
Backtracking	Jelajah & mundur	`O(2ⁿ)` atau `O(n!)`	N-Queens, permutasi

Contoh Kode: Brute Force vs Divide and Conquer #

Masalah maximum subarray: diberikan array bilangan bulat (boleh negatif), cari jumlah maksimum dari subarray yang tidak kosong. Kita akan menyelesaikannya dengan dua paradigma berbeda dan memverifikasi bahwa keduanya menghasilkan jawaban yang sama.

Mekanisme Kedua Pendekatan #

Brute force mencoba seluruh pasangan indeks (i, j) dengan i ≤ j, menjumlahkan data[i..j], dan melacak nilai terbesar. Banyaknya pasangan adalah O(n²).

Divide and conquer membagi array menjadi dua bagian pada indeks tengah. Subarray maksimum berada pada salah satu dari tiga lokasi: sepenuhnya di kiri, sepenuhnya di kanan, atau melintasi tengah. Dua kasus pertama diselesaikan secara rekursif. Kasus ketiga diselesaikan dengan menjumlahkan ke kiri dan ke kanan dari tengah. Kompleksitas: O(n log n).

Kode Program #

cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

// Brute force: coba semua pasangan (i, j) dan jumlahkan subarray
int maxSubarrayBrute(const std::vector<int>& data) {
    int n = (int)data.size();
    int terbaik = INT_MIN;
    for (int i = 0; i < n; ++i) {
        int jumlah = 0;
        for (int j = i; j < n; ++j) {
            jumlah += data[j];
            if (jumlah > terbaik) {
                terbaik = jumlah;
            }
        }
    }
    return terbaik;
}

// Divide and conquer: bagi dua, selesaikan kiri & kanan, periksa perpotongan
int maxSubarrayDC(const std::vector<int>& data, int kiri, int kanan) {
    if (kiri == kanan) {
        return data[kiri];
    }
    int tengah = kiri + (kanan - kiri) / 2;

    int terbaikKiri  = maxSubarrayDC(data, kiri, tengah);
    int terbaikKanan = maxSubarrayDC(data, tengah + 1, kanan);

    // Subarray yang melintasi tengah
    int jumlahKiri = INT_MIN;
    int total = 0;
    for (int i = tengah; i >= kiri; --i) {
        total += data[i];
        if (total > jumlahKiri) jumlahKiri = total;
    }
    int jumlahKanan = INT_MIN;
    total = 0;
    for (int i = tengah + 1; i <= kanan; ++i) {
        total += data[i];
        if (total > jumlahKanan) jumlahKanan = total;
    }
    int terbaikLintas = jumlahKiri + jumlahKanan;

    return std::max({terbaikKiri, terbaikKanan, terbaikLintas});
}

int main() {
    std::vector<int> data = {-2, 1, -3, 4, -1, 2, 1, -5, 4};

    int hasilBrute = maxSubarrayBrute(data);
    int hasilDC    = maxSubarrayDC(data, 0, (int)data.size() - 1);

    std::cout << "Array: ";
    for (int v : data) std::cout << v << " ";
    std::cout << "\n";
    std::cout << "Max subarray (brute force)    : " << hasilBrute << "\n";
    std::cout << "Max subarray (divide & conquer): " << hasilDC << "\n";
    std::cout << "Konsisten? "
              << (hasilBrute == hasilDC ? "ya" : "tidak") << "\n";

    return 0;
}

Output yang Dihasilkan:

text
Array: -2 1 -3 4 -1 2 1 -5 4 
Max subarray (brute force)    : 6
Max subarray (divide & conquer): 6
Konsisten? ya

Bedah Kode Baris-per-Baris #

Mari kita telaah bagian-bagian penting dari program di atas:

Baris 7 (int terbaik = INT_MIN;): inisialisasi dengan nilai int paling kecil agar setiap subarray non-kosong langsung menjadi kandidat terbaik. Menggunakan 0 sebagai inisialisasi akan salah ketika seluruh elemen negatif.
Baris 9 (for (int j = i; j < n; ++j)): loop dalam yang menjumlahkan data[i..j] secara inkremental. Triknya: jumlah += data[j] setiap iterasi, tanpa harus menjumlahkan ulang dari awal.
Baris 17 (if (kiri == kanan) return data[kiri];): kasus dasar rekursi: submasalah dengan satu elemen.
Baris 20 (int terbaikKiri = maxSubarrayDC(data, kiri, tengah);): panggilan rekursif untuk separuh kiri. Inilah inti conquer pada divide and conquer.
Baris 25–31 (loop tengah ke kiri): menjumlahkan ke arah kiri dari tengah untuk menemukan jumlah maksimum subarray yang berakhir tepat di tengah.
Baris 32–38 (loop tengah + 1 ke kanan): menjumlahkan ke arah kanan dari tengah + 1 untuk menemukan jumlah maksimum subarray yang dimulai tepat setelah tengah.
Baris 40 (std::max({terbaikKiri, terbaikKanan, terbaikLintas})): menggunakan initializer list overload dari std::max yang tersedia sejak C++11 untuk mencari maksimum tiga nilai sekaligus.

Strategi Memilih Paradigma #

Tidak ada paradigma yang selalu menang. Pemilihan tergantung pada struktur masalah, ukuran input, dan kebutuhan optimalitas. Berikut panduan praktis:

Mulai dari brute force untuk memahami masalah dan memverifikasi jawaban.
Identifikasi subproblem: jika ada tumpang tindih, pertimbangkan DP.
Cek greedy choice property: jika pilihan optimal lokal tetap optimal global, greedy sangat cepat.
Cek independensi bagian: jika masalah dapat dipecah tanpa interaksi antar bagian, divide and conquer cocok.
Cek struktur solusi parsial: jika solusi dapat divalidasi parsial, backtracking dapat memangkas ruang pencarian.

Ringkasan #

Pada Chapter ini kita telah memetakan lima paradigma algoritma utama:

Brute force: coba seluruh kemungkinan, paling sederhana tetapi paling lambat.
Divide and conquer: pecah, selesaikan rekursif, gabungkan.
Greedy: pilih optimal lokal, cepat tetapi tidak selalu optimal global.
Dynamic programming: simpan hasil subproblem tumpang tindih.
Backtracking: jelajah ruang solusi dengan mundur saat buntu.

Pada Chapter berikutnya kita akan membahas strategi belajar DSA secara efektif agar dapat menyerap materi yang luas ini tanpa kewalahan.