Memahami berbagai jenis algoritma adalah langkah fundamental untuk menjadi seorang programmer yang andal. Setiap jenis memiliki pendekatan unik untuk memecahkan masalah, dan memilih yang tepat dapat secara drastis meningkatkan efisiensi dan kejelasan kode Anda.
Dalam artikel ini, kita akan membahas lima jenis algoritma pemrograman yang paling populer dan sering ditemui dalam pengembangan perangkat lunak dan ilmu komputer. Untuk melihat lebih banyak contoh algoritma dalam kehidupan sehari-hari, Anda bisa membaca artikel utama kami.
1. Divide and Conquer (Pecah dan Taklukkan)
Konsep: Sesuai namanya, algoritma ini bekerja dengan memecah masalah besar menjadi beberapa sub-masalah yang lebih kecil dan sejenis. Sub-masalah ini kemudian diselesaikan secara independen. Akhirnya, solusi dari sub-masalah tersebut digabungkan kembali untuk membentuk solusi dari masalah awal.
Kapan Digunakan: Sangat efektif untuk masalah yang dapat dipecah menjadi bagian-bagian independen, seperti pengurutan (sorting) dan pencarian (searching) pada kumpulan data besar.
Contoh Kasus Terkenal:
- Merge Sort: Algoritma pengurutan yang membagi array menjadi dua bagian, mengurutkan masing-masing bagian, lalu menggabungkannya kembali.
- Quick Sort: Memilih sebuah ‘pivot’, lalu mempartisi array menjadi dua, di mana satu bagian lebih kecil dari pivot dan bagian lainnya lebih besar.
- Binary Search: Mencari elemen dalam array yang sudah terurut dengan berulang kali membagi interval pencarian menjadi dua.
Pseudocode (Merge Sort):
FUNGSI MergeSort(array):
JIKA panjang(array) <= 1 MAKA
KEMBALIKAN array
SET tengah = panjang(array) / 2
SET kiri = MergeSort(array dari awal hingga tengah)
SET kanan = MergeSort(array dari tengah hingga akhir)
KEMBALIKAN Gabungkan(kiri, kanan)
2. Dynamic Programming (Pemrograman Dinamis)
Konsep: Algoritma ini memecahkan masalah kompleks dengan memecahnya menjadi sub-masalah yang lebih sederhana dan tumpang tindih (overlapping). Kunci utamanya adalah menyimpan hasil dari sub-masalah (memoization) agar tidak perlu dihitung berulang kali. Ini adalah optimisasi dari pendekatan rekursif biasa.
Kapan Digunakan: Ideal untuk masalah optimisasi di mana sub-masalah yang sama muncul berulang kali.
Contoh Kasus Terkenal:
- Deret Fibonacci: Menghitung angka Fibonacci ke-n dengan menyimpan hasil yang sudah dihitung sebelumnya untuk menghindari kalkulasi ganda.
- Knapsack Problem: Menentukan kombinasi barang yang dapat dimasukkan ke dalam tas dengan kapasitas terbatas untuk mendapatkan nilai total maksimal.
- Longest Common Subsequence: Menemukan urutan sub-sekuens terpanjang yang ada di antara dua sekuens.
Pseudocode (Fibonacci dengan Memoization):
SET memo = {} // Kamus untuk menyimpan hasil
FUNGSI Fibonacci(n):
JIKA n ada di memo MAKA
KEMBALIKAN memo[n]
JIKA n <= 2 MAKA
KEMBALIKAN 1
SET hasil = Fibonacci(n-1) + Fibonacci(n-2)
simpan hasil ke memo[n]
KEMBALIKAN hasil
3. Backtracking (Lacak Balik)
Konsep: Algoritma ini mencoba membangun solusi secara bertahap. Pada setiap langkah, jika ternyata pilihan yang diambil tidak mengarah pada solusi yang valid, algoritma akan “mundur” (backtrack) ke langkah sebelumnya dan mencoba pilihan lain. Ini seperti menjelajahi labirin; jika bertemu jalan buntu, Anda kembali ke persimpangan terakhir dan mencoba jalan lain.
Kapan Digunakan: Cocok untuk masalah pencarian ruang solusi, seperti teka-teki, permainan, dan masalah penempatan.
Contoh Kasus Terkenal:
- N-Queens Problem: Menempatkan N ratu catur di papan N×N sehingga tidak ada ratu yang bisa saling menyerang.
- Teka-Teki Sudoku: Mengisi papan Sudoku sesuai dengan aturannya.
- Menemukan Jalan di Labirin (Maze Solving).
Pseudocode (Konsep N-Queens):
FUNGSI SolveNQueens(papan, baris):
JIKA baris >= N MAKA
KEMBALIKAN true // Semua ratu berhasil ditempatkan
UNTUK setiap kolom dari 0 hingga N-1:
JIKA amanUntukMenempatkan(papan, baris, kolom) MAKA
tempatkan ratu di papan[baris][kolom]
JIKA SolveNQueens(papan, baris + 1) == true MAKA
KEMBALIKAN true
// Jika tidak mengarah ke solusi, backtrack
hapus ratu dari papan[baris][kolom]
KEMBALIKAN false // Tidak ada solusi dari baris ini
4. Recursive Algorithm (Algoritma Rekursif)
Konsep: Sebuah fungsi atau metode yang memanggil dirinya sendiri untuk menyelesaikan masalah. Setiap pemanggilan rekursif akan memecah masalah menjadi versi yang lebih kecil dari masalah yang sama, hingga mencapai sebuah “kasus dasar” (base case) yang dapat diselesaikan secara langsung tanpa rekursi lebih lanjut.
Kapan Digunakan: Berguna untuk masalah yang secara alami dapat didefinisikan dalam terminologi dirinya sendiri, seperti struktur data pohon (tree) atau faktorial.
Contoh Kasus Terkenal:
- Perhitungan Faktorial:
faktorial(n) = n * faktorial(n-1). - Tree Traversal: Mengunjungi setiap node dalam sebuah struktur data pohon (In-order, Pre-order, Post-order).
- Towers of Hanoi.
Pseudocode (Faktorial):
FUNGSI Faktorial(n):
// Kasus dasar (base case)
JIKA n == 0 MAKA
KEMBALIKAN 1
// Langkah rekursif
SELAIN ITU
KEMBALIKAN n * Faktorial(n - 1)
5. Randomized Algorithm (Algoritma Acak)
Konsep: Algoritma ini menggunakan elemen keacakan (randomness) sebagai bagian dari logikanya. Hasilnya mungkin berbeda dalam setiap eksekusi, bahkan dengan input yang sama. Tujuannya seringkali untuk mencapai performa rata-rata yang baik dalam menghadapi berbagai skenario input.
Kapan Digunakan: Berguna ketika pendekatan deterministik terlalu lambat atau kompleks, atau untuk menghindari skenario kasus terburuk (worst-case).
Contoh Kasus Terkenal:
- Randomized Quick Sort: Varian dari Quick Sort di mana elemen pivot dipilih secara acak, bukan elemen pertama atau terakhir. Ini membantu menghindari kasus terburuk di mana array sudah terurut.
- Monte Carlo Method: Menggunakan sampling acak untuk mendapatkan hasil numerik, misalnya untuk memperkirakan nilai Pi.
Pseudocode (Randomized Quick Sort):
FUNGSI RandomizedQuickSort(array):
JIKA panjang(array) <= 1 MAKA
KEMBALIKAN array
pilih pivot secara acak dari array
partisi array menjadi 'kurang_dari_pivot', 'sama_dengan_pivot', 'lebih_dari_pivot'
SET hasil_kiri = RandomizedQuickSort(kurang_dari_pivot)
SET hasil_kanan = RandomizedQuickSort(lebih_dari_pivot)
KEMBALIKAN hasil_kiri + sama_dengan_pivot + hasil_kanan
Dua pendekatan yang sering dibahas adalah algoritma Greedy dan Brute Force.