My first Magazine pemrograman-kompetitif-dasar | Page 52

5
Divide and Conquer
Divide and conquer (D&C ) adalah metode penyelesaian masalah dengan cara membagi
masalah menjadi beberapa submasalah yang lebih kecil dan sederhana, kemudian menyelesaikan
masing-masing submasalah tersebut, lalu menggabungkannya kembali menjadi sebuah solusi yang
utuh. Prinsip divide and conquer banyak digunakan pada struktur data lanjutan dan geometri
komputasional.
5.1
Konsep Divide and Conquer
Jika suatu masalah dapat dibagi menjadi beberapa submasalah serupa yang lebih kecil dan
independen, kemudian solusi dari masing-masing submasalah dapat digabungkan, maka divide
and conquer dapat digunakan.
divide
conquer
combine
Gambar 5.1: Ilustrasi proses divide and conquer .
Gambar 5.1 mengilustrasikan proses divide and conquer . Proses tersebut terdiri dari tiga
tahap yaitu:
1. Divide : membagi masalah menjadi masalah-masalah yang lebih kecil. Biasanya menjadi
setengahnya atau mendekati setengahnya.
2. Conquer : ketika sebuah masalah sudah cukup kecil untuk diselesaikan, langsung selesaikan
masalah tersebut.
3. Combine : menggabungkan solusi dari masalah-masalah yang lebih kecil menjadi solusi
untuk masalah yang lebih besar.
42