医学生わくばの欲張り技術ブログ

〜E資格を取りに行く!〜

アルゴリズム

【アルゴリズム(JS実装)】Rabin-Karp Algorithm

// どうも、わくばです! 今回はRabin-Karp algorithmです。どんどん重たくなってきたので、日をまたがないとできなくなってきました(汗)。まだまだですね。。。 Rabin-Karp algorithmはハッシュ関数を用いたマッチングアルゴリズムです。ハッシュ関数という…

【アルゴリズム(JS実装)】Knuth Morris Pratt Algorithm

// どうも、わくばです! 今回はKMP algorithmです。これは意味がわかるまでかなり時間かかってしまいました。なんとなく言いたいことはわかるんですけど、それをアルゴリズムに起こすときにハテナが大量に(笑) KMPは前処理部分と探索部分に分かれていて、探…

【アルゴリズム(JS実装)】Naive String Pattern Matching (Brute Force Approach)

// どうも、わくばです! 今日からPattern Searchingに入りたいと思います。KMP AlgorithmやBoyer Moore Algorithmなどちょっと耳にしたことのある仰々しい名前のアルゴリズムが待っているジャンルなのでちょっと怖いです(小並感)。 まずはNaive String Patt…

【アルゴリズム(JS実装)】Exponential Search

// どうも、わくばです! 今日はExponential Searchです。Exponentialといのは指数関数的という意味です。理系学生は\(e^x\)や\(exp(x)\)でおなじみですよね。 このアルゴリズムは名前の通りで、指数関数的なインターバルを用いて飛び飛びに探索していくアル…

【アルゴリズム(JS実装) 】Interpolation Search

// どうも、わくばです! 今日はInterpolation Searchです。このアルゴリズムはBinary Searchの改造版で基本的な考え方は同じです。したがってソート済みの配列に適用する点は同じです。では何が違うのかというと、Binaryでは真ん中で半分にしていましたが、…

【アルゴリズム(JS実装)】Jump Search

// どうも、わくばです! 今日は Jump Searchです。こちらもソート済みの配列を検索するアルゴリズムです。単純に言うとLinear Searchを端折った感じです。まず決まったintervalで飛び飛びに進んで探索をします。どのintervalにあるかわかったらその中でLine…

【アルゴリズム(JS実装)】Binary Search

// どうも、わくばです! 今日はBinary Searchです。ソートが前提の処理ですが、前回のLinear searchより速いと思います。 仕組みはこんな感じ 基準値を決める 基準値と探している値を比べる 基準値より大きければその基準値より上に的を絞る 基準値より小さ…

【アルゴリズム(JS実装)】Linear Search

// どうも、わくばです! Sortに関してはある程度有名なものをやり終えたので、Searchに入ろうと思います。 今日はLinear Searchです。一番簡単なサーチだと思います。 コードはこんな感じです。 function linearSearch(array, value){ let results = [] for…

【アルゴリズム(JS実装)】Radix Sort

// どうも、わくばです! 今日はRadix Sortです。Bucket Sortに似てますね。Radixというのは基数とか根とか底とかいくつか訳がありますが、この例ではn進法のnのことです。 Radix Sortを簡単に説明すると、例えば10進法で考えるなら 0−9の計10個のバケット…

【アルゴリズム(JS実装)】Bucket Sort

どうも、わくばです! 今日はBucket Sortを勉強しました。バケツを用いた分割統治アルゴリズムで、Counting Sort の一般化と考えられます。実際、バケツサイズを1とすると同じ値のものだけが同じバケツに集約されていくので、Couting Sortと同様の処理にな…

【アルゴリズム(JS実装)】Counting Sort

// どうも、わくばです! 先日。E資格に申し込んだと言ったのですが、試験会場が都心しか空いていないことと、その他大学の実習の都合などいろいろ加味した結果、キャンセルして見送ることにしました。 JDLA認定は二年間有効なので、また機を見て受験しよう…

【アルゴリズム(JS実装)】Shell Sort

// どうも、わくばです! 今日はShell Sortを学びました。これはInsertion Sort の応用なのでコードを見てイマイチピントこなかった方は以前書いたInsertion Sortをぜひ参考にしてみてください*1 Shell Sortは飛び飛びでグループを形成し、グループごとにIns…

Big O notation の計算原理について調べてみた

// どうも、わくばです! アルゴリズムをいくつか勉強しているうちにBig O notationに関してだいぶ適当だったと感じてのでちゃんと調べてみました。が、結局わりと適当でオッケーみたいですね笑 MITのサイトや各種プログラミング学習サイトから引用しながら…

【アルゴリズム(JS実装)】Quick Sort

// どうも、わくばです! E資格の申し込みを完了しました。2万は高いなあww もともとなんでE資格を受けようと思ったかというと、プログラミングの勉強を始めたとき背水の陣を敷くのが目的だったんですよね。挫折者多いですし。個人的に挫折する自信があった…

【アルゴリズム(JS実装)】Merge Sort

// どうも、わくばです! 今日はJDLA認定講座の最後の試験でした。無事合格しましたので、これでやっとE資格試験を受験できます。 なんでこんなにめんどくさいのだ(笑) 機械学習は統計的な処理もしっかり含まれていて、医学でも役立つので何れにせよ頑張り…

【アルゴリズム(JS実装)】Insertion Sort

// どうも、わくばです! 今日はInsertion Sortです。自分より前の要素を比較していって、自分より小さいものが現れたらその後ろに挿入するというアルゴリズムです。 コードは以下のような感じです。 const insertionSort = array => { for (let i = 1; i < …

【アルゴリズム(JS実装)】Selection Sort

// どうも、わくばです! 今日はSelection Sort を学びました。今回はシンプルです。 アルゴリズムの説明はこのサイトが非常にわかりやすいのでぜひ:Selection Sort - InterviewBit コードはこんな感じになりました。 function selectionSort(array, size){…

【アルゴリズム(JS実装)】Binary Heap

// どうも、わくばです! 今日はBinary Heapです。正直コードに落とすのがかなり複雑で時間がかかっていしまいました。ヒープがどんなデータ構造なのかについてはページの最後に参考を用意しておいたのでそちらを御覧ください。*1 結局は優先キューなので、…

【アルゴリズム(JS実装)】Bubble Sort

// どうも!わくばです! 今日から1日1アルゴリズムずつ記事にしていこうかなと思います。今までなんとなく避けてきたんですがそろそろそうも行かなくなってきたので、、、 普段codewarsというサイトでコーディングの勉強をしているんですが、上級になると結…