My first Magazine pemrograman-kompetitif-dasar | Page 48

4
Brute Force
Brute force adalah salah satu strategi penyelesaian masalah. Brute force merupakan
strategi yang sederhana, serta pasti menemukan solusi yang kita harapkan, walaupun pada
umumnya memerlukan waktu yang cukup lama.
II Sekilas Info JJ
Pada kompetisi dengan sistem penilaian parsial seperti OSN atau IOI, umumnya subsoal-
subsoal awal dapat diselesaikan dengan brute force .
4.1
Konsep Brute Force
Brute force bukan merupakan suatu algoritma khusus, melainkan suatu strategi penyelesaian
masalah. Sebutan lain dari brute force adalah complete search dan exhaustive search . Prinsip
dari strategi ini hanya satu, yaitu mencoba semua kemungkinan.
Brute force menjamin solusi pasti benar karena menelusuri seluruh kemungkinan. Aki-
batnya, secara umum brute force bekerja dengan lambat, terutama ketika terdapat banyak
kemungkinan solusi yang perlu dicoba. Sebagai contoh, salah satu penggunaan strategi brute
force adalah dalam mengerjakan permasalahan Subset Sum .
Contoh Soal 4.1: Subset Sum
Diberikan N buah bilangan {a 1 , a 2 , ..., a N } dan sebuah bilangan K. Apakah terdapat sebuah
subhimpunan sedemikian sehingga jumlahan dari elemen-elemennya sama dengan K? Bila
ya, maka keluarkan "YA". Selain itu, keluarkan "TIDAK".
Batasan
• 1 ≤ N ≤ 15
• 1 ≤ K ≤ 10 5
• 1 ≤ a i ≤ 10 5
4.2
Penyelesaian dengan Teknik Brute Force
Ingat bahwa prinsip dari strategi brute force adalah menelusuri semua kemungkinan. Dengan
kata lain, kita mencoba membangkitkan seluruh kemungkinan, lalu mencari jawaban dari permasa-
lahan kita melalui seluruh kemungkinan tersebut. Dalam membangkitkan seluruh kemungkinan,
kita dapat melakukannya secara iteratif maupun rekursif.
38