LeetCode (70): Permasalahan Menaiki Tangga

image source: liputan6

Seperti biasa, setiap pagi, aku mencoba untuk mengerjakan persoalan atau problem yang disediakan oleh Leetcode, sebuah website kumpulan persoalan yang biasanya diujikan pada technical test ketika ingin melamar pekerjaan atau magang. Namun, kemarin, aku menemukan sebuah persoalan unik yang berjudul Climbing Stairs. Yang membuat persoalan ini unik bukan tingkat kesulitannya, melain sebagaimana tricky penyelesaiannya. Berikut persoalan Climbing Stairs dari LeetCode.

 Seseorang bisa menaiki tangga dengan naik satu anak tangga atau langsung menaiki dua anak tangga sekaligus. dalam menaiki tangga, bisa saja dapat banyak kombinasi cara menaiki tangga. Jika terdapat tangga setinggi n anak tangga. Tentukan banyak cara menaiki anak tangga.

    Bila Anda diminta untuk menyelesaikan ini, bagaimana kah cara Anda menghitungnya? Sejatinya, ada banyak cara menyelesaikan permasalahan ini. Namun, dalam komputasi, jawaban terbaik disajikan dalam cara termalas atau nilai kompleksitas terkecil. 

    Simpelnya, nilai kompleksitas adalah banyak proses yang dieksekusi oleh sebuah program untuk menyelesaikan permasalahan. Umumnya, hal ini dinotasikan dalam O(x) atau yang kerap disebut Big-O, dengan x bisa berupa n, 1, log n dan lain sebagainya.

    Oke, sebelum lanjut pembahasan permasalahan di atas, coba teman-teman stop di sini terlebih dahulu, dan pikirkan cara terefisien untuk menyelesaikan masalah di atas. Sudah? Oke sekarang bagaimana teman-teman menyelesaikan problem di atas? Apakah teman-teman akan menuliskan semua kombinasi langkah yang mungkin pada ketinggian n?

    Hmm, cara tersebut memang tepat, dan dapat menyelesaikan persoalan di atas. Namun, cara tersebut sangat lah tidak efisien. Mungkin untuk nilai n yang kecil, atau di bawah sepuluh, perulangan yang dieksekusi oleh komputer masih sedikit. Namun, jika nilai n mencapai 1000, atau 1.000.000? Mungkin CPU anda akan meledak bukan? wkwk... Atau mungkin anda akan mendapatkan hasilnya setelah sejuta tahun.. xixixixi

    Oke, ini mulai serius, wkwkw, kita masuk ke pembahasannya. Salah satu metode penting, dalam penyelesaian masalah komputatif ialah pattern recognition. Dengan pattern recognition, kita bisa mereduksi operasi perulangan dengan formula atau pola tertentu. Oke mari kita lihat pada n dengan nilai 1-5.

    n         kombinasi mungkin

    1        1 -> (1)

    2        1+1, 2 -> (2)

    3        1+1+1, 1+2, 2+1  ->  (3)

    4        1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2   ->   (5)

    5        1+1+1+1+1, 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+1+1+1, 1+2+2 .... capek -> (8)

    Ya mungkin untuk kombinasi tiap pola kita bisa pake nilai C(n,r), dengan menghitung banyaknya satu langkah, dan 2 langkah, atau kita bisa menggunakan kombinasi dengan perulangan, tapi sadarkah anda cara tersebut terlalu kompleks boy... mari kita pakai cara pikir orang malas.

    Bagaimana orang malas berpikir? Ya kita tahu "less is better". Jadi, mari kita lihat total kombinasi yang mungkin tadi sebagai sebuah barisan bilangan berikut

    1, 2, 3, 5, 8

    Sebagian orang tidak menyadari, bahwa sebenarnya problem di atas adalah pola bilangan fibonacci dengan perubahan. Yep, pola di atas adalah pola fibonacci, misal g(n) adalah bilangan fibonacci dengan perubahan ke-n, g(1)=1 dan g(2)=2. Bila ditelisik lebih lanjut, dan kita misalkan f(n) adalah bilangan fibonacci biasa ke-n, maka g(n)=f(n+1).

    Wah, sudah mulai terang. Oke, sekarang pertanyaannya, bagaimanakah cara  yang paling optimal menghitung bilangan fibonacci ke-n? Oke, mari kita list bagaimana cara atau algoritma menemukan bilangan fibonacci ke-n, ada interative, recursive with memotion (dynamic programming), recurrsive dan binet formula. Mungkin algoritma tadi sedikit asing di mata teman-teman, oke jadi mari kita bahas satu per satu.

• Recurrsive

        Recursive adalah program yang memanggil fungsi itu sendiri. Untuk mengerjakan program rekursi, kita perli mendefinisikan dua hal, yakni basis atau kapan program berhenti menggil dirinya sendiri, serta rekurens atau bagaimana program memanggil dirinya sendiri. Dalam fibonacci, nilai basis ada ketika n=1 dan n=2, sedangkan rekurensnya ialah f(n-1)+f(n-2). Maka kita dapat merumuskan bentuk rekursi dari permaslahan ini adalah

```

int solve(int n):

if(n==1) return 1

else if(n==2) return 2

else return solve(n-1)+solve(n-2)

```

        Bagaiaman komplesitasnya? Untuk tiap perulangannya dia akan memanggil dua buah fungsi anakan, untuk menyelesaikan problem ini perlu sebanya 2^(n-1) operasi, yang dapat didekati dalam big-O menjadi O(2^n).    

• Recurrsive with memozation.

        Ini merupakan cara yang lebih mangkus dari reccurrsive biasa. Caranya dengan menyimpan nilai solve yang sebelumnya sudah dikomputasi, sehingga tidak perlu memanggil fungsi f(n) yang dengan n-nya sudah dipanggil sebelumnya. Sebelum memanggil fungsi solve, kita harus men-set agar semua n bernilai -1.

```

int solve(int n, vector<int>& arr):

if(n==1) return 1

else if(n==2) return 2

else if(arr[n]!=-1) return arr[n]

else return arr[n] = solve(n-1)+solve(n)

```

    Dengan metode ini, kita hanya perlu memanggil solve(n) untuk tiap nilai n sekali, sehingga kompleksitasnya dapat direduksi menjadi n kali operasi untuk tiap kali program dijalankan, atau didekati dengan big-O dengan nilai O(n).

• Iterative

        Nyatanya, recurrisive memakan terlalu banyak memori, sehingga kita perlu mencari algoritma yang lebih baik. Jawabannya adalah iterasi. Ya cara yang bisa dibilang cukup ga keren karena hanya menggunakan for, wkwk. Kita hany perlu menjumlahkan nilai f(i) sehingga mendapat nilai f(n-2) serta f(n-2) melalui perulangan.

```

int solve(int n):

    fa =1;

    fb=2;

    for(int i=3;i<=n-1;i++){

        int temp = fa+fb;

        fa = fb;

        fb=fa;

    }

    return fa+fb

```

        Cara ini adalah cara paling intuitive, yang hanya berupa pengartian dari logika manusia ke logika komputer. Nyantanya, cara ini menyimpan memori yang sangat sedikit, tanpa array, dan hanya memakan n kali operasi atau didekati dengan big-O bernilai O(n).

• Binet Formula     

        Mungkin, kita merasa, cara-cara di atas sudah sangat efisien, dan bahkan logika dasar kita mengatakan, tidak mungkin ada cara yang lebih efisieeennn... WKWKWK... tidak bestie, Anda salah, ingat di atas langit masih ada langit. Asik, wkwk, nah nyatanya cara paling efisien ialah dengan menggunakan Binet Formula. Dengan cara ini kita hanya perlu sebaris kode dengan nilai Big-O senilai O(1). Keren bukan? Ya itulah the power of knowledge wkwkwk... Sebelum baca next paragraf, ada beberapa pembuktian yang dapat kamu baca, satu, dua, dan hampiran. Dua hal tadi menjadi pembuktian mengenai pendekatan Deret Fibonacci dengan Binet Formula.

        Okay, let's take a look. Kita sadar, buhwa untuk tiap g(n)=f(n+1), artinya untuk anak tangga setinggi n, nilainya setara dengan fibonacci ke-n+1. Nah, kita tidak akan menggunakan rumus binet, seluruhnya, pada kalkulus kita telah belajar limit, sehingga kita dapat mendekati nilai f(n) dengan hamipiran atau limit n->tak hingga. Sehingga didapat hampiran dari nilai F(n) adalah

 f(n) = 1/sqrt(5) * (1+sqrt(5))^n

sehingga didapat pendekatan g(n) dengan formula

g(n) = f(n+1) = 1/sqrt(5) * (1+sqrt(5))^(n+1)

        Yang jika kita rumuskan dalam pseudo c++ menjadi, (kita pake round buat mendapatkan nilai pembulatannya yak wkwk..)

```

int solve(int n):

    return round(pow(1+sqrt(5),n+1)/sqrt(5));

```

        Menyenangkan bukan? BUKAN!!! wkwkwk... kita bisa selesaikan dengan 1 operasi dan hanya satu baris kode... Oke selamat kamu telah menyelsaikan probelm ini, ingat di luar sana masih ada jutaan problem komputasi yang harus diselesaikan. Semangat menggapai mimpi, sampai jumpa di FAANG.

        Kalau kamu suka dengan tulisan ini, dan ingin menyupport risqi untuk terus menulis, bagikan dan jangan lupa komen di bawah xioxixixixi.. terima kasih...

Tulisan ini dibuat dalam rangka #10DaysOfWriting oleh Risqi, semoga tidak wacana...