💻

Informatika SMA - OSN

Persiapan Olimpiade Informatika/Komputer tingkat SMA

🔢 Sistem Bilangan & Logika Boolean

Konversi antar sistem bilangan (biner, oktal, desimal, heksadesimal) merupakan dasar ilmu komputer. Aljabar Boolean digunakan dalam desain sirkuit digital dan ekspresi logika.

📌 Rumus Penting

Biner → Desimal: Σ bit × 2^posisi (dari kanan, mulai posisi 0)

Desimal → Biner: bagi 2 berulang, catat sisa dari bawah ke atas

Oktal: setiap digit = 3 bit biner | Heks: setiap digit = 4 bit biner

AND: 1 jika semua 1 | OR: 1 jika ada 1 | NOT: kebalikan | XOR: 1 jika berbeda

NAND = NOT(AND) | NOR = NOT(OR) | XNOR: 1 jika sama

De Morgan: NOT(A AND B) = NOT A OR NOT B

De Morgan: NOT(A OR B) = NOT A AND NOT B

💡 Contoh

1011₂ = 1×8 + 0×4 + 1×2 + 1×1 = 11₁₀

A3₁₆ = 10×16 + 3 = 163₁₀

175₈ = 1×64 + 7×8 + 5 = 64+56+5 = 125₁₀

NOT(1 AND 0) = NOT(0) = 1

Biimplikasi P↔Q: TRUE jika P dan Q sama-sama T atau sama-sama F

Tautologi: selalu bernilai TRUE untuk semua kombinasi input

Kontraposisi: (P→Q) ekuivalen dengan (¬Q→¬P)

📊 Struktur Data & Kompleksitas

Struktur data adalah cara menyimpan dan mengorganisasi data. Pilihan struktur data yang tepat sangat mempengaruhi efisiensi program. Notasi Big-O mengukur kompleksitas waktu dan ruang.

📌 Rumus Penting

O(1) < O(log n) < O(√n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

Array: akses O(1), insert/delete O(n)

Linked list: akses O(n), insert/delete head O(1)

Hash table: akses/insert/delete rata-rata O(1), worst case O(n)

Binary search tree (BST): operasi rata-rata O(log n)

Heap (priority queue): insert O(log n), extract-min/max O(log n)

Stack dan Queue: semua operasi O(1)

💡 Contoh

Stack (LIFO): push/pop — undo, call stack, evaluasi ekspresi

Queue (FIFO): enqueue/dequeue — antrian BFS, penjadwalan proses

Binary tree: setiap node punya maks 2 anak

BST: kiri < root < kanan, in-order traversal → sorted

Traversal: pre-order (VLR), in-order (LVR), post-order (LRV)

Graf: V = simpul (vertex), E = sisi (edge), undirected/directed/berbobot

Adjacency matrix: O(V²) ruang | Adjacency list: O(V+E) ruang

⚡ Algoritma: Sorting, Searching & Rekursi

Algoritma sorting dan searching adalah pondasi pemrograman kompetitif. Rekursi dan pemikiran divide-and-conquer sangat penting untuk OSN Informatika.

📌 Rumus Penting

Bubble sort: O(n²) time, O(1) space — bandingan berpasangan berulang

Selection sort: O(n²) — cari minimum, pindah ke depan

Insertion sort: O(n²) worst, O(n) best (sudah terurut)

Merge sort: O(n log n) — divide, conquer, merge. Stabil.

Quick sort: O(n log n) avg, O(n²) worst — pivot partition

Binary search: O(log n) — hanya pada array terurut

Rekursi: T(n) = T(n-1) + O(1) → O(n) | T(n) = 2T(n/2) + O(n) → O(n log n)

💡 Contoh

Merge sort array [5,3,8,1]: [5,3]+[8,1] → [3,5]+[1,8] → [1,3,5,8]

Binary search di [1,3,5,7,9], cari 7: mid=5→kanan, mid=7→ketemu

Fibonacci rekursi naif: O(2ⁿ) → dengan memoization: O(n)

Tower of Hanoi n disk: T(n) = 2T(n-1)+1 → O(2ⁿ) langkah

Master theorem: T(n) = aT(n/b) + f(n) → solusi berdasarkan perbandingan f(n) vs n^(log_b a)

🗺️ Graph Traversal & Algoritma Graf

Masalah berbasis graf sangat sering muncul di OSN Informatika. BFS, DFS, Dijkstra, dan spanning tree adalah materi wajib.

📌 Rumus Penting

BFS (Breadth-First Search): O(V+E) — gunakan Queue, jarak terpendek unweighted

DFS (Depth-First Search): O(V+E) — gunakan Stack/rekursi, topological sort

Dijkstra: O((V+E) log V) dengan priority queue — jarak terpendek weighted (non-negatif)

Bellman-Ford: O(VE) — jarak terpendek, bisa bobot negatif

Floyd-Warshall: O(V³) — all pairs shortest path

Kruskal MST: O(E log E) — sort edge, Union-Find

Prim MST: O((V+E) log V) — grow dari satu simpul

💡 Contoh

BFS dari simpul A: level 0={A}, level 1={tetangga A}, level 2={tetangga level 1} dst.

DFS deteksi siklus: jika bertemu simpul yang sudah "dikunjungi tapi belum selesai" → ada siklus

Topological sort: urutkan simpul sehingga semua edge u→v, u sebelum v (DAG)

MST: pohon merentang minimum — V-1 edge, menghubungkan semua simpul dengan bobot total terkecil

Dijkstra: tidak bisa dengan bobot negatif — gunakan Bellman-Ford

Union-Find (Disjoint Set): operasi union dan find, deteksi komponen terhubung

🧩 Dynamic Programming & Pemrograman Kompetitif

Dynamic Programming (DP) memecah masalah besar menjadi submasalah yang tumpang tindih. Kunci: identifikasi state, transisi, dan base case. Ini adalah inti dari soal-soal olimpiade.

📌 Rumus Penting

DP = memoization (top-down) atau tabulation (bottom-up)

DP valid jika ada: optimal substructure + overlapping subproblems

Knapsack 0/1: dp[i][w] = max(dp[i-1][w], val[i]+dp[i-1][w-wt[i]])

LCS: dp[i][j] = dp[i-1][j-1]+1 jika A[i]=B[j], else max(dp[i-1][j], dp[i][j-1])

LIS: O(n²) DP atau O(n log n) dengan binary search + patience sorting

Matrix chain: dp[i][j] = min cost perkalian matriks i hingga j

Edit distance: dp[i][j] = min(insert, delete, replace)

💡 Contoh

Fibonacci DP: dp[0]=0, dp[1]=1, dp[n]=dp[n-1]+dp[n-2] → O(n) waktu, O(1) ruang

Knapsack n=3, kapasitas 5: pertimbangkan tiap barang satu per satu, isi tabel dp

LCS "ABCBDAB" dan "BDCAB": panjang LCS = 4 ("BCAB" atau "BDAB")

Coin change: dp[amount] = min koin untuk mencapai amount tertentu

Bitmask DP: state dengan subset, traveling salesman problem O(2ⁿ × n²)

Prinsip greedy vs DP: greedy ambil pilihan terbaik lokal, DP eksplorasi semua kemungkinan

Mulai Latihan Soal