Pemrograman kompetitif merupakan terjemahan bebas dari istilah competitive programming atau biasa disebut CP. Berikut adalah ‘Shortcut’ algoritma untuk CP.
Sorting & Searching
| Algorithm/Function | Header | Usage | Time Complexity |
|---|---|---|---|
sort() |
<algorithm> |
Mengurutkan rentang (vector, array) | O(N log N) |
stable_sort() |
<algorithm> |
Pengurutan stabil (mempertahankan urutan elemen yang sama) | O(N log N) |
partial_sort() |
<algorithm> |
Mengurutkan k elemen pertama |
O(N log K) |
nth_element() |
<algorithm> |
Menemukan elemen terkecil ke-n |
O(N) rata-rata |
binary_search() |
<algorithm> |
Memeriksa apakah suatu elemen ada dalam rentang yang diurutkan | O(log N) |
lower_bound() |
<algorithm> |
Elemen pertama target | O(log N) |
upper_bound() |
<algorithm> |
Elemen pertama target | O(log N) |
Contoh:
- Untuk mengurutkan
string s ="dcba", Kita hanya perlu
Maka akan keluar output abcd
- Untuk mengurutkan angka
Swap & Reverse
| Function | Header | Usage |
|---|---|---|
swap(a, b) |
<utility> |
Menukar dua nilai |
reverse() |
<algorithm> |
Membalikkan rentang |
iter_swap() |
<algorithm> |
Menukar elemen pada iterator |
Contoh:
Permutations & Combinations
| Function | Header | Usage |
|---|---|---|
next_permutation() |
<algorithm> |
Menghasilkan permutasi leksikografis berikutnya |
prev_permutation() |
<algorithm> |
Menghasilkan permutasi leksikografis sebelumnya |
Contoh:
Numeric Operations
| Fungsi | Header | Penggunaan |
gcd(a, b) |
<numeric> |
Menghitung faktor persekutuan terbesar (FPB) dari dua bilangan a dan b. |
lcm(a, b) |
<numeric> |
Menghitung kelipatan persekutuan terkecil (KPK) dari dua bilangan a dan b. |
accumulate() |
<numeric> |
Menjumlahkan semua elemen dalam suatu rentang (misalnya, vector atau array), atau menerapkan operasi biner lainnya. |
partial_sum() |
<numeric> |
Menghitung jumlah parsial (prefix sums). Setiap elemen menjadi jumlah dari elemen-elemen sebelumnya ditambah dirinya sendiri. |
iota() |
<numeric> |
Mengisi rentang (misalnya, vector atau array) dengan nilai-nilai yang bertambah secara berurutan, dimulai dari suatu nilai awal. |
Contoh:
Min/Max Operations
| Fungsi | Header | Penggunaan |
min(a, b) |
<algorithm> |
Mengembalikan nilai yang lebih kecil antara dua nilai a dan b. |
max(a, b) |
<algorithm> |
Mengembalikan nilai yang lebih besar antara dua nilai a dan b. |
min_element() |
<algorithm> |
Mengembalikan iterator (penunjuk) ke elemen terkecil dalam sebuah rentang (misalnya, vector atau array). |
max_element() |
<algorithm> |
Mengembalikan iterator (penunjuk) ke elemen terbesar dalam sebuah rentang (misalnya, vector atau array). |
Contoh:
String Manipulation
| Fungsi | Header | Penggunaan |
tolower() / toupper() |
<cctype> |
Mengubah karakter menjadi huruf kecil (tolower()) atau huruf besar (toupper()). |
isalpha() / isdigit() |
<cctype> |
Memeriksa apakah karakter adalah huruf alfabet (isalpha()) atau digit angka (isdigit()). |
substr() |
<string> |
Mengekstrak (mengambil) bagian kecil (substring) dari sebuah string. |
stoi() / to_string() |
<string> |
Mengkonversi string menjadi angka (stoi()) atau angka menjadi string (to_string()). |
Contoh:
Leave a Reply