Olimpiade Sains Nasional (OSN) Informatika SMA menjadi ajang kompetisi bergengsi. Siswa mengasah kemampuan, siswa memecahkan masalah algoritmik. Soal OSN menguji logika, soal OSN menuntut kreativitas. Informatika memiliki peran penting, informatika mendorong inovasi.
5 Contoh Soal OSN Informatika SMA Lengkap dengan Jawaban
Persiapan matang menjadi kunci keberhasilan dalam OSN Informatika SMA. Memahami berbagai tipe soal dan berlatih secara konsisten sangatlah penting. Berikut adalah 5 contoh soal OSN Informatika SMA beserta pembahasan lengkapnya yang dapat membantu Anda dalam mempersiapkan diri:
Soal 1: Pencarian Biner (Binary Search)
Soal: Diberikan sebuah array integer terurut menaik `arr` dengan `n` elemen dan sebuah nilai target `target`. Tuliskan sebuah fungsi untuk mencari index dari `target` dalam `arr`. Jika `target` tidak ditemukan, kembalikan -1.
Contoh:
`arr = [2, 5, 7, 8, 11, 12]`
`target = 13`
Jawaban: -1
`arr = [2, 5, 7, 8, 11, 12]`
`target = 12`
Jawaban: 5
Pembahasan:
Pencarian Biner adalah algoritma yang efisien untuk mencari elemen dalam array terurut. Algoritma ini bekerja dengan berulang kali membagi dua bagian array. Berikut adalah langkah-langkahnya:
- Inisialisasi `low` ke 0 dan `high` ke `n-1`.
- Ulangi langkah-langkah berikut selama `low` <= `high`:
- Hitung `mid` sebagai `(low + high) / 2`.
- Jika `arr[mid]` sama dengan `target`, kembalikan `mid`.
- Jika `arr[mid]` kurang dari `target`, maka `target` pasti berada di bagian kanan array. Set `low` ke `mid + 1`.
- Jika `arr[mid]` lebih besar dari `target`, maka `target` pasti berada di bagian kiri array. Set `high` ke `mid – 1`.
- Jika `target` tidak ditemukan, kembalikan -1.
Kode Python:
def binary_search(arr, target):
low = 0
high = len(arr)
-1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
Soal 2: Algoritma Greedy
Soal: Diberikan sebuah array integer `items` yang merepresentasikan nilai dari barang-barang dan sebuah integer `capacity` yang merepresentasikan kapasitas maksimum dari sebuah tas. Tuliskan sebuah fungsi untuk memilih barang-barang yang akan dimasukkan ke dalam tas sehingga total nilai barang yang dimasukkan maksimal, tanpa melebihi kapasitas tas. Anda hanya bisa mengambil sebagian dari barang (fractional knapsack).
Contoh:
`items = [60, 100, 120]`
`weights = [10, 20, 30]`
`capacity = 50`
Jawaban: 240.0
Pembahasan:
Algoritma Greedy adalah pendekatan yang memilih opsi terbaik pada setiap langkah, dengan harapan mendapatkan solusi optimal secara keseluruhan. Dalam kasus fractional knapsack, kita dapat menghitung nilai per berat dari setiap barang dan mengurutkannya secara menurun. Kemudian, kita mengambil barang dengan nilai per berat tertinggi hingga kapasitas tas terpenuhi.
- Hitung nilai per berat untuk setiap barang (nilai / berat).
- Urutkan barang berdasarkan nilai per berat secara menurun.
- Iterasi melalui barang-barang yang sudah diurutkan:
- Jika berat barang saat ini kurang dari atau sama dengan kapasitas yang tersisa, masukkan seluruh barang ke dalam tas dan kurangi kapasitas yang tersisa.
- Jika berat barang saat ini lebih besar dari kapasitas yang tersisa, masukkan sebagian barang (sesuai dengan kapasitas yang tersisa) ke dalam tas dan hentikan iterasi.
- Kembalikan total nilai barang yang dimasukkan ke dalam tas.
Kode Python:
def fractional_knapsack(capacity, items, weights):
n = len(items)
ratio = [items[i] / weights[i] for i in range(n)]
index = list(range(n))
index.sort(key=lambda i: ratio[i], reverse=True)
total_value = 0
for i in index:
if weights[i] <= capacity:
capacity -= weights[i]
total_value += items[i]
else:
total_value += ratio[i]
- capacity
break
return total_value
Soal 3: Pemrograman Dinamis (Dynamic Programming)
Soal: Diberikan sebuah array integer `coins` yang merepresentasikan denominasi koin dan sebuah integer `amount` yang merepresentasikan jumlah uang yang ingin dibentuk. Tuliskan sebuah fungsi untuk menghitung jumlah kombinasi koin yang berbeda untuk membentuk jumlah uang tersebut.
Contoh:
`coins = [1, 2, 5]`
`amount = 5`
Jawaban: 4
Pembahasan:
Pemrograman Dinamis adalah teknik yang memecah masalah kompleks menjadi submasalah yang lebih kecil dan saling tumpang tindih. Solusi untuk submasalah disimpan untuk menghindari perhitungan ulang. Dalam kasus ini, kita dapat menggunakan tabel 2D `dp` di mana `dp[i][j]` merepresentasikan jumlah kombinasi koin untuk membentuk jumlah uang `j` menggunakan `i` koin pertama.
- Inisialisasi tabel `dp` dengan ukuran `(len(coins) + 1) x (amount + 1)`.
- Inisialisasi baris pertama `dp` dengan 0 (tidak ada cara untuk membentuk jumlah uang apa pun tanpa koin).
- Inisialisasi kolom pertama `dp` dengan 1 (hanya ada satu cara untuk membentuk jumlah uang 0, yaitu dengan tidak menggunakan koin apa pun).
- Iterasi melalui tabel `dp` dari baris 1 hingga `len(coins)` dan dari kolom 1 hingga `amount`:
- Jika nilai koin saat ini kurang dari atau sama dengan jumlah uang saat ini, maka `dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]`. Ini berarti kita dapat membentuk jumlah uang `j` dengan tidak menggunakan koin saat ini (menggunakan solusi dari baris sebelumnya) atau dengan menggunakan koin saat ini (menggunakan solusi untuk membentuk jumlah uang `j - coins[i-1]` menggunakan koin yang sama).
- Jika nilai koin saat ini lebih besar dari jumlah uang saat ini, maka `dp[i][j] = dp[i-1][j]`. Ini berarti kita tidak dapat menggunakan koin saat ini dan hanya dapat menggunakan solusi dari baris sebelumnya.
- Kembalikan `dp[len(coins)][amount]`.
Kode Python:
def coin_change(coins, amount):
dp = [[0]
- (amount + 1) for _ in range(len(coins) + 1)]
for i in range(len(coins) + 1):
dp[i][0] = 1
for i in range(1, len(coins) + 1):
for j in range(1, amount + 1):
if coins[i-1] <= j:
dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]
else:
dp[i][j] = dp[i-1][j]
return dp[len(coins)][amount]
Soal 4: Graf dan Pencarian Jalur Terpendek
Soal: Diberikan sebuah graf berbobot yang direpresentasikan sebagai daftar sisi, di mana setiap sisi memiliki format `(u, v, w)` (simpul u, simpul v, bobot w). Tuliskan sebuah fungsi untuk menemukan jalur terpendek dari simpul sumber `source` ke semua simpul lainnya dalam graf menggunakan algoritma Dijkstra.
Contoh:
`edges = [(0, 1, 4), (0, 2, 2), (1, 2, 5), (1, 3, 10), (2, 3, 3)]`
`source = 0`
Jawaban: `0: 0, 1: 4, 2: 2, 3: 5`
Pembahasan:
Algoritma Dijkstra adalah algoritma untuk menemukan jalur terpendek dari simpul sumber ke semua simpul lainnya dalam graf berbobot non-negatif. Algoritma ini bekerja dengan menjaga jarak terpendek yang diketahui dari simpul sumber ke setiap simpul lainnya. Pada setiap langkah, algoritma memilih simpul dengan jarak terpendek yang diketahui dan memperbarui jarak ke simpul-simpul tetangganya.
- Inisialisasi jarak ke semua simpul dengan tak hingga (infinity) kecuali simpul sumber, yang diinisialisasi dengan 0.
- Buat sebuah set `visited` untuk menyimpan simpul-simpul yang sudah dikunjungi.
- Ulangi langkah-langkah berikut selama masih ada simpul yang belum dikunjungi:
- Pilih simpul `u` yang belum dikunjungi dengan jarak terpendek yang diketahui.
- Tandai simpul `u` sebagai dikunjungi.
- Iterasi melalui semua simpul tetangga `v` dari simpul `u`:
- Jika jarak dari simpul sumber ke simpul `v` melalui simpul `u` lebih pendek dari jarak yang diketahui saat ini ke simpul `v`, perbarui jarak ke simpul `v`.
- Kembalikan jarak terpendek dari simpul sumber ke semua simpul lainnya.
Kode Python:
import heapq
def dijkstra(edges, source):
graph =
for u, v, w in edges:
if u not in graph:
graph[u] = []
if v not in graph:
graph[v] = []
graph[u].append((v, w))
graph[v].append((u, w))
distances = node: float('inf') for node in graph
distances[source] = 0
pq = [(0, source)]
while pq:
dist, u = heapq.heappop(pq)
if dist > distances[u]:
continue
if u not in graph:
continue
for v, weight in graph[u]:
if distances[v] > distances[u] + weight:
distances[v] = distances[u] + weight
heapq.heappush(pq, (distances[v], v))
return distances
Soal 5: Struktur Data (Stack dan Queue), 5 Contoh Soal OSN Informatika SMA Lengkap dengan Jawaban
Soal: Diberikan sebuah string `s` yang berisi tanda kurung `(` dan `)`. Tuliskan sebuah fungsi untuk memeriksa apakah tanda kurung dalam string tersebut seimbang.
Contoh:
`s = "(()())"`
Jawaban: True
`s = "(()"`
Jawaban: False
Pembahasan:
Kita dapat menggunakan stack untuk memeriksa apakah tanda kurung seimbang. Ketika kita menemukan tanda kurung buka `(`, kita memasukkannya ke dalam stack. Ketika kita menemukan tanda kurung tutup `)`, kita memeriksa apakah stack kosong. Jika stack kosong, maka tanda kurung tidak seimbang. Jika stack tidak kosong, kita mengeluarkan tanda kurung buka dari stack.
Jika pada akhir iterasi stack tidak kosong, maka tanda kurung tidak seimbang.
- Buat sebuah stack kosong.
- Iterasi melalui string `s`:
- Jika karakter saat ini adalah tanda kurung buka `(`, masukkan ke dalam stack.
- Jika karakter saat ini adalah tanda kurung tutup `)`, periksa apakah stack kosong. Jika stack kosong, kembalikan False. Jika stack tidak kosong, keluarkan tanda kurung buka dari stack.
- Jika stack kosong, kembalikan True. Jika stack tidak kosong, kembalikan False.
Kode Python:
def is_balanced(s):
stack = []
for char in s:
if char == '(':
stack.append(char)
elif char == ')':
if not stack:
return False
stack.pop()
return not stack
Semoga contoh-contoh soal ini bermanfaat untuk persiapan OSN Informatika SMA! Jangan lupa untuk terus berlatih dan mengembangkan kemampuan problem solving Anda.
Terima kasih sudah membaca artikel ini! Semoga informasi ini bermanfaat dan bisa membantu teman-teman dalam mempersiapkan diri menghadapi OSN Informatika. Jangan ragu untuk kembali lagi nanti, karena kami akan terus menyajikan artikel-artikel menarik dan informatif lainnya. Sampai jumpa!