Dan Kunci Jawaban

Soal dan Kunci Jawaban Beserta Pembahasannya

Home » Soal » Soal NLC 2019

Soal NLC 2019

Share on :

Soal NLC 2018 - Tentunya dengan Soal NLC 2019 yang kami sampikan ini akan bisa membuat anda bisa mengerti dan memahami Soal NLC 2019 yang kami sampikan untuk anda semua. Soal yang kami berikan juga akan memberikan pembahasaan dan juga kunci jawabannya sehingga anda tidak perlu kawatir tentang Soal NLC 2019 yang kami sampaikan tersebut.

Ini akan sangat memudahkan buat anda semua yang ingin belajar Soal NLC 2019 tersebut. Disini admin kunci jawaban memberikan banyak sekali soal-soal dan pembahasan untuk bisa anda pelajari juga sehingga anda mengerti tentang soal yang saat ini anda ingin pelajari.

Untuk selengkapnya tentang Soal NLC 2019 tersebut kamu bisa simak dibawah ini selengkapnya untuk anda semua, semoga bisa menjadi manfaat untuk pelajaraan anda saat ini.

Soal NLC 2019

Introduction

“Pak Dengklek sedang berlibur ke desa bebek. Dalam liburannya, secara tak sengaja ia menemukan prasasti kuno ketika sedang menyusuri sawah desa bebek. Di dalam prasasti itu dia menemukan sekumpulan N (1 ≤ N ≤ 1000, N bilangan ganjil) angka acak. Dikatakan bahwa tersembunyi angka hoki di dalam sekumpulan angka itu. Yang dimaksud angka hoki adalah jika sekumpulan angka itu berada dalam keadaan terurut, maka angka yang tepat berada di tengah-tengah kumpulan angka itu adalah angka hoki. Pak Dengklek penasaran akan angka hoki itu, sehingga ia meminta bantuan Anda. Bantulah dia!”
Misalkan contoh masukan dari sekumpulan angka acak di soal adalah seperti di bawah ini:
2 1 3 6 5 8 4 7 10 21 12
Dengan sedikit pemikiran, kita tahu bahwa “angka hoki” yang dimaksud Pak Dengklek adalah median dari kumpulan acak itu. Setelah mengetahui bahwa yang dicari adalah nilai median, apa yang akan kita lakukan? Tentunya dalam mencari median akan lebih mudah juga sekumpulan angka di atas telah dalam keadaan terurut seperti di bawah ini:
1 2 3 4 5 6 7 8 10 12 21
Setelah kumpulan angka tersebut sudah dalam keadaan terurut menaik (ascending), maka nilai median dapat dengan segera ditemukan (rumus mencari median sudah tau kan?). Kenapa dikatakan terurut menaik, karena bisa saja kita mengatur agar sekumpulan angka di atas berada dalam keadaan terurut menurun (descending), misalnya seperti contoh berikut.
21 12 10 8 7 6 5 4 3 2 1
Bagaimana jika kita ingin mengurutkan sekumpulan kata? Misal ada kumpulan kata seperti di bawah ini:
halo
saya
sangat
senang
dan
bersemangat
belajar
pemrograman
kita dapat mengurutkannya secara leksikografis (sesuai urutan kamus, contohnya ‘A‘ muncul sebelum ‘B‘ dan ‘AKU‘ muncul sebelum ‘ANDA‘), seperti:
belajar
bersemangat
dan
halo
pemrograman
sangat
saya
senang
atau bisa juga diurutkan berdasarkan panjang dari kata itu (jika panjang kata sama, urutkan berdasarkan leksikografis), seperti:
dan
halo
saya
sangat
senang
belajar
bersemangat
pemrograman
Dalam pemrograman, hal ini biasa disebut sorting (atau mengurutkan). Dalam mengurutkan sekumpulan data, ada aturan yang dipakai untuk menentukan prioritas, misal bilangan yang lebih kecil muncul lebih dulu, atau kata yang panjangnya lebih pendek muncul terlebih dahulu. Banyak sekali algoritma yang tersedia untuk pengurutan sekumpulan data, ada yang gampang ditulis kodenya, ada juga yang kodenya panjang. Kali ini saya akan bahas beberapa algoritma sorting yang umum dipakai, yaitu:
  1. Bubble Sort (kompleksitas O(N2)).
  2. Quick Sort (kompleksitas expected O(N × log2N), worst case O(N2)).
  3. Merge Sort (kompleksitas O(N × log2N)).
  4. Count Sort (kompleksitas O(N)).
  5. Radix Sort (kompleksitas O(d × N), di mana d adalah panjang digit terpanjang dalam kumpulan data).
  6. Heap Sort (coming soon).
----------------------------------------------------------------

Bubble Sort

Bubble sort adalah salah satu algoritma pengurutan yang sederhana dan gampang di-coding. Ide dasarnya adalah dalam setiap looping, cari bilangan terkecil dan tempatkan di paling kiri (untuk ascending sort), potongan kodenya adalah sebagai berikut:

1
2
3
4
5
6
7
8
for i := 1 to N do
    for j := 1 to N - 1 do
        if data[j] > data[j + 1] then
        begin
            temp := data[j];
            data[j] := data[j + 1];
            data[j + 1] := temp;
        end;
Perhatikan potongan kode di atas, jelas untuk setiap looping ke-i selesai, kita akan mendapatkan bilangan terbesar ke-i pada posisi data[N-i+1]. Kompleksitas Bubble sort adalah O(N2), artinya untuk kumpulan data sebanyak 1.000 buah data, algoritma ini membutuhkan 1.000.000 kali operasi untuk mengurutkan data tersebut. Untuk banyak data yang relatif kecil (sekitar di bawah 5.000) algoritma ini berjalan relatif cepat.

Mungkin kalian bertanya-tanya, kenapa algoritma ini dinamai Bubble Sort. Dari yang pernah saya baca atau dengar, kalau kalian lihat di danau, gelembung gas dalam danau yang paling besar akan muncul ke permukaan pertama kali :).

Selain Bubble Sort, ada juga varian algoritma sorting lain yang sama-sama mempunyai kompleksitas O(N2) seperti Insertion Sort dan Selection Sort, tapi tidak saya bahas karena menurut saya mereka bertiga agak mirip (bahkan saya sendiri bingung membedakan Bubble Sort dan Insertion Sort) dan kompleksitas pun sama-sama O(N2), jadi rasanya cukup mempelajari salah satu saja.

-------------------------------------------------------

Quick Sort

Seperti yang disebutkan sebelumnya, kompleksitas Bubble Sort adalah O(N2), artinya jika jumlah data sebanyak 10.000 data (N = 10.000), maka Bubble Sort akan melakukan sekitar 100 juta operasi untuk mengurutkan sekumpulan data itu. Konversi yang umum dipakai adalah 1 detiknya komputer mampu melakukan 100 juta operasi sederhana, artinya untuk jumlah data yang relatif besar (misal, N = 1.000.000) maka Bubble Sort memerlukan waktu yang cukup lama (N = 1 juta, berarti sekitar 1012 operasi, jika 1 detiknya = 100 juta operasi, maka waktu yang diperlukan sekitar 10.000 detik atau hampir 3 jam!).

Lalu apa yang harus dilakukan untuk jika kita ingin mengurutkan data yang banyaknya relatif besar? salah satu caranya adalah dengan menggunakan Quick Sort. Sesuai namanya, Quick Sort dengan kompleksitas O(N × log2N) merupakan teknik sorting yang cukup cepat, dengan jumlah data sebanyak 1 juta, Quick Sort hanya melakukan sekitar 20 juta operasi, masih di bawah 1 detik :D.
Ide dasar dari Quick Sort adalah jika kita mempunyai sekumpulan angka lalu kita jejerkan dari kiri ke kanan, kita dapat mengambil angka yang berada di tengah-tengah/ pivot dan semua angka di sebelah kiri dari pivot yang lebih besar dari pivot dipindahkan ke sebelah kanan pivot, kemudian semua angka di sebelah kanan dari pivot yang lebih kecil dari pivot dipindahkan ke sebelah kiri pivot. Jika proses ini diulang-ulang untuk sub-jangkauan data yang lebih kecil, pada akhirnya kita akan mendapatkan barisan data yang terurut menaik (ascending).

Potongan kode dari Quick Sort disertakan di bagian bawah (Peringatan: Quick Sort menggunakan procedure dan konsep rekursif, jika kalian belum mengerti tentang kedua topik ini, disarankan untuk memperkuat dasar procedure dan rekursif terlebih dahulu).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
procedure quicksort(terkiri,terkanan: longint);
var kiri, kanan, temp, pivot: longint;
begin
   if terkiri < terkanan then
   begin
      kiri := terkiri;
      kanan := terkanan;
      pivot := data[(kiri + kanan) div 2];
      while kiri <= kanan do
      begin
         while data[kiri] < pivot do inc(kiri);
         while data[kanan] > pivot do dec(kanan);
         if kiri <= kanan then
         begin
            temp := data[kiri];
            data[kiri] := data[kanan];
            data[kanan] := temp;
            inc(kiri);
            dec(kanan);
         end;
      end;
      quicksort(terkiri,kanan);
      quicksort(kiri,terkanan);
   end;
end;
Procedure di atas dapat dipanggil di program utama dengan quicksort(1,N); dimana N adalah banyaknya data (asumsikan array kalian mulai dari indeks ke-1, kalau mulai dari indeks ke-0 bisa disesuaikan sendiri, format sebenarnya adalah quicksort(indeks_terawal,indeks_terakhir);).
Untuk Quick Sort, sebenarnya saya juga ada animasinya, tapi dalam bahasa C++ dan visualisasi animasi tersebut menggunakan terkiri sebagai pivot, bukan (terkiri + terkanan) div 2 seperti potongan kode di atas, jadi daripada membuat kalian bingung tidak saya sertakan.

---------------------------------------------------------

Merge Sort
Walaupun Quick Sort adalah algoritma sorting yang cukup cepat (bahkan yang tercepat di antara semua algoritma sorting O(N × log2N), menurut tutorial pengurutan dari PJJ TOKI – thx Veni!) tapi runtime Quick Sort sendiri boleh dikatakan tidak stabil. “Artinya, dijamin 99,9999% bahwa Quick Sort akan berjalan dengan sangat cepat, tetapi pada kasus-kasus tertentu Quick Sort akan berjalan agak lambat, dan kalau sedang sial, untuk input tertentu (worst case) Quick Sort akan berjalan dengan waktu O(N2). Namun pada umumnya (average case), Quick Sort berjalan dengan waktu O(N × log2N)“ – tutorial pengurutan TOKI.

Selain Quick Sort, ada 1 lagi algoritma sorting dengan kompleksitas O(N × log2N) dan runtime-nya cukup stabil, yaitu Merge Sort. Ide dasar dari Merge Sort adalah membagi sekumpulan angka menjadi 2 bagian yang lebih kecil, kemudian per bagian diselesaikan masing-masing. Bagian yang telah mengecil itu akan terus dibagi 2 sampai dirasa sudah cukup kecil (1 elemen), tiap bagian yang kecil itu diurutkan masing-masing. Bagian besar sebelumnya akan memanggil 2 bagian kecil yang telah terurut tadi untuk digabungkan menjadi 1 kumpulan besar yang terurut.

Source code dari Merge sort adalah sebagai berikut: (Peringatan: sama seperti Quick Sort, Merge Sort juga menggunakan konsep rekursif ditambah 1 procedure tambahan)
1
2
3
4
5
6
7
8
9
10
procedure sort(terkiri, terkanan: longint);
begin
   if terkiri < terkanan then
   begin
      sort(terkiri, (terkiri + terkanan) div 2);
      sort(((terkiri + terkanan) div 2) + 1, terkanan);
      merge(terkiri,(terkiri + terkanan) div 2, ((terkiri + terkanan) div 2) + 1, terkanan);
   end;
end;

sedangkan potongan kode dari procedure merge() adalah sebagai berikut:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
procedure merge(a1, b1, a2, b2: longint);
var i, awal: longint;
    temp: array[1..1000000] of longint;
begin
   i := a1;
   awal := a1;
   while ((a1 <= b1) and (a2 <= b2)) do
   begin
      if data[a1] <= data[a2] then
      begin
         temp[i] := data[a1];
         inc(a1);
      end else
      begin
         temp[i] := data[a2];
         inc(a2);
      end;
      inc(i);
   end;
   while (a1 <= b1) do
   begin
      temp[i] := data[a1];
      inc(a1);
      inc(i);
   end;
   while (a2 <= b2) do
   begin
      temp[i] := data[a2];
      inc(a2);
      inc(i);
   end;
   for i := awal to b2 do data[i] := temp[i];
end;
Merge Sort dipanggil di program utama dengan sort(1, N); di mana N adalah banyaknya data. Perhatikan dalam procedure merge() digunakan 1 array temporer tempat kedua bagian kecil diurutkan, dan kemudian di bagian akhir data-data yang telah terurut itu akan dikembalikan kepada array.

Cukup panjang ya untuk sebuah algoritma sorting jika dibandingkan dengan Quick Sort dan yang lain. Mungkin karena alasan ini juga Quick Sort yang lebih populer digunakan dalam programming contest walaupun runtime-nya kurang stabil.
 --------------------------------------------------------------------

Count Sort

Kalau dari tadi kita membicarakan algoritma sorting yang konvensional, sekarang kita akan membicarakan yang agak “unik”. Namanya Count Sort (atau Counting Sort), kompleksitasnya hanya O(N + M) di mana N adalah banyaknya data dan M adalah selisih antara bilangan terbesar dan terkecil dalam kumpulan data. Oleh karena itu Count Sort dalam beberapa kasus bisa lebih cepat dibanding algoritma O(N × log2N) lain.
Ide dasar dari Count Sort sendiri adalah menghitung berapa banyak angka “1” di kumpulan data, berapa banyak angka “2”, angka “3”, angka “4”, dan seterusnya. Setelah itu kita looping sekali lagi untuk mengeluarkan angka “1” sesuai jumlahnya di kumpulan data, angka “2” sesuai jumlahnya, angka “3”, angka “4”, dan seterusnya. Kedengarannya gampang ya?
Potongan kode dari Count Sort adalah sebagai di bawah ini (sebelumnya, set nilai di array cnt dengan 0, bisa dengan fillchar atau looping sekali).

1
2
3
4
5
6
7
8
for x := 1 to N do inc(cnt[data[x]]);
now := 1;
for x := data_terkecil to data_terbesar do if(cnt[x] > 0) then
    for y := 1 to cnt[x] do
    begin
       data[now] := x;
       inc(now);
    end;
Dari potongan kode di atas kita tahu bahwa ukuran array dari cnt haruslah menjangkau dari bilangan terkecil hingga bilangan terbesar dalam data, maksudnya jika masukan data adalah sebagai berikut:
7 1 10 3 100 -1 -5 -100 1532
Maka ukuran dari cnt haruslah menjangkau dari -100 hingga 1532. Seperti yang bisa ditebak, Count Sort tidak dapat digunakan jika jarak antara data terbesar dan data terkecil dalam kumpulan data terlalu besar, misalnya seperti di bawah ini:
-12345678912 1 2 1234567890
Banyak data pada input di atas memang kecil, hanya 4 elemen, namun bilangan terbesarnya 1234567890 dan bilangan terkecilnya -12345678912, tidak mungkin kita bisa menyediakan array dengan ukuran sebesar itu.
Kelemahan lain Count Sort adalah hanya bisa digunakan untuk mengurutkan bilangan bulat, tidak bisa bilangan desimal atau kalimat.
-------------------------------------------------------------

Radix Sort

Selain Count Sort, ada 1 lagi algoritma sorting dengan kompleksitas waktu O(N) (sebenarnya O(d × N), di mana d adalah panjang digit terpanjang dalam kumpulan data), yaitu Radix Sort. Sepengetahuan saya, jarang sekali sampai ada yang menggunakan Radix Sort dalam programming contest karena algoritma O(N × log2N) seperti Quick Sort sendiri sudah lebih dari cukup. Saya sertakan di sini cuma untuk menambah pengetahuan kalian saja. Kalau tidak berminat, halaman ini bisa di-skip.
Ide dasar dari Radix Sort adalah mengurutkan kumpulan data berdasarkan angka satuan, puluhan, ratusan, ribuan, dan seterusnya. Source code dari Radix Sort adalah sebagai berikut:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
procedure radixsort(N: longint);
var temp: array[1..10000] of longint;
    bucket: array[0..9] of longint;
    i, largest, exp: longint;
begin
   largest := 0;
   exp := 1;
   for i := 1 to N do if data[i] > largest then largest := data[i];
   while largest div exp > 0 do
   begin
      for i := 0 to 9 do bucket[i] := 0;
      for i := 1 to N do inc(bucket[(data[i] div exp) mod 10]);
      for i := 1 to 9 do bucket[i] := bucket[i] + bucket[i - 1];
      for i := N downto 1 do
      begin
         temp[bucket[(data[i] div exp) mod 10]] := data[i];
         dec(bucket[(data[i] div exp) mod 10]);
      end;
      for i := 1 to N do data[i] := temp[i];
      exp := exp * 10;
   end;
end;
Kalau potongan kode di atas cermati, mungkin kalian akan bertanya-tanya, “bagaimana jika kumpulan data memiliki nilai negatif atau 0 (nol)?” Memang, kode di atas hanya bekerja untuk kumpulan data yang tidak mengandung bilangan negatif dan bilangan terbesarnya tidak nol. Untuk mensiasati kumpulan data dengan bilangan negatif, dapat dibuat menjadi 2 bagian; kumpulan bilangan negatif dan non-negatif. Setelah masing-masing diurutkan baru digabungkan.

sumber: felikjunvianto.wordpress.com




LIHAT JUGA SOAL LAINNYA :

Anda sedang membaca Artikel tentang Soal NLC 2019 dan anda bisa menemukan Artikel Soal NLC 2019 ini dengan URL http://kuncijawaban4.blogspot.com/2017/03/soal-nlc-2017.html, Terimakasih Telah membaca Artikel Soal NLC 2019 Anda boleh menyebar Luaskan atau MengCopy-Paste nya jika Artikel Soal NLC 2019 ini sangat bermanfaat bagi anda, Namun jangan lupa untuk meletakkan Link Soal NLC 2019 sebagai Sumbernya.
23.37

0 komentar on Soal NLC 2019 :

Post a Comment and Don't Spam!

Langganan: Posting Komentar (RSS)