Problem Solving Paradigm

Question 1

Apa itu Divide and Conquer?

Answer 1

Metode penyelesaian masalah dengan cara membagi masalah menjadi beberapa submasalah yang lebih kecil dan sederhana, kemudian menyelesaikan masing-masing submasalah dan menggabungkannya kembali menjadi sebuah solusi yang utuh.

Question 2

Sebutkan beberapa algoritma yang menggunakan Divide and Conquer!

Answer 2

• Binary Search
• Binary Expo
• Merge Sort
• Segment Tree
• Fenwick Tree

Question 3

Apa kompleksitas waktu dari Binary Search?

Answer 3

O(logN)

Question 4

Apa yang dimaksud dengan Brute Force?

Answer 4

Metode yang memeriksa semua kemungkinan untuk menemukan solusi, sangat berguna untuk masalah yang kecil namun memakan waktu.

Question 5

Apa itu Dynamic Programming?

Answer 5

Metode penyelesaian masalah yang mengoptimalkan brute force dengan menyimpan hasil submasalah yang telah diselesaikan.

Question 6

Sebutkan dua cara implementasi Dynamic Programming!

Answer 6

• Top-down: diimplementasikan secara rekursif dengan memoisasi
• Bottom-up: diimplementasikan secara iteratif

Question 7

Apa perbedaan antara Greedy dan Dynamic Programming?

Answer 7

Greedy memilih opsi terbaik lokal tanpa mempertimbangkan keseluruhan, sementara DP mencoba semua kemungkinan untuk menemukan solusi optimal.

Question 8

Sebutkan dua tipe problem yang bisa diselesaikan menggunakan Dynamic Programming!

Answer 8

• Mencari suatu hal yang optimal
• Mencari banyak cara suatu hal

Question 9

Apa itu Game Theory?

Answer 9

Bagian dari ilmu matematika yang mempelajari interaksi antar agen yang bersifat rasional dan strategi yang dipilih.

Question 10

Apa yang dimaksud dengan Greedy Choice?

Answer 10

Langkah pemilihan yang paling menguntungkan dalam teknik Greedy.

Question 11

Berapa banyak cara untuk membentuk kata ‘MAS’ dari ‘MASSSASAASAMMSAS’?

Answer 11

A. 22
B. 23
C. 24
D. 25
E. 26

Question 12

Berapa nilai k yang dipilih Kwak untuk menyelesaikan PR?

Answer 12

10

Question 13

Berapa banyak jalur yang dapat dilalui Pak Dengklek dari (1, 1) ke (6, 6) dalam grid 6x6?

Answer 13

15

Question 14

Berapa banyak kemunculan subsekuens ‘OSN’ pada string ‘SONOSONO’?

Answer 14

2

Question 15

Berapa banyak operasi minimum yang diperlukan agar tidak ada orang yang saling berhadapan dalam string biner ‘1100101110’?

Answer 15

4

Question 16

Apa rumus untuk menghitung mod dari dua bilangan?

Answer 16

(a*b) mod m = (a mod m) * (b mod m)

Question 17

Isi titik-titik berikut: 10! mod 11 = …

Answer 17

10

Question 18

Apa yang dimaksud dengan subsekuens dalam konteks ini?

Answer 18

Urutan karakter yang dipilih dari string asli tanpa mengubah urutannya.

Question 19

Jika N=10, berapa banyak pecahan koin minimal untuk penukaran 13 koin dengan koin 7, 2, 3, 6?

Answer 19

3