Yuki's Tech Blog

仕事で得た知見や勉強した技術を書きます。

アルゴリズム

アルゴリズムとデータ構造関連で知ったことをまとめる part 1

目次 目次 概要 アルゴリズムに関する基本的な用語 全探索 線形探索 アルゴリズム 設計技法 貪欲法 区間スケジューリング問題 二分探索 データ構造に関する基本的な用語 データ構造とは グラフ 有向グラフ、無向グラフ サイクル 木 根付き木 葉 親、子 二分…

主要なソートについてまとめる

目次 目次 概要 バブルソート バブルソートとは 具体的な手順 サンプルコード 選択ソート 選択ソートとは 具体的な手順 サンプルコード 挿入ソート 挿入ソートとは 具体的な手順 サンプルコード クイックソート クイックソートとは 具体的な手順 サンプルコ…

問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本で知ったことをざっくりまとめてみた (part 3)

目次 目次 確率を実数で表す 期待値とは 確率変数とは 確率分布とは 試行とは 事象とは 期待値の線形性 小数とは 割り算の結果を小数にしたい時 小数部の桁数を指定して値を出力したい時 乱数とは 参考記事 確率を実数で表す 確率は%を使って表すことが多い…

問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本で知ったことをざっくりまとめてみた (part 2)

目次 目次 ユークリッドの互除法とは なぜ計算量がO(log(A+B))になるのか? 最大公約数を求めるアルゴリズム N個の自然数の最大公約数を求める N個の数の最小公倍数を求めるプログラム n個の物から2個選んで500円になるような選び方を求める AtCorderの実行…

問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本で知ったことをざっくりまとめてみた (part 1)

目次 目次 コンピュータと2進法の関係 なぜコンピュータでは2進法を使うのか 円周率(Πとは) ルートと平方根の違い C++のint 剰余(mod) 論理演算とは ビット演算の流れ 3つ以上のAND, OR, XORに対する性質 多項式関数 単調増加とは 常用対数とは 数学の関数と…

アルゴリズムとAPG4bについてざっくりまとめてみた(part 2)

目次 目次 メモリとは 計算量とは 時間計算量とは ステップ数とは 空間計算量 オーダー記法とは オーダー記法の書き方 ログ 入力に適した計算量のアルゴリズムを選択する プログラムの実行を1秒以内に収めたい場合 複数の入力がある場合のオーダー記法 STLの…

アルゴリズムとAPG4bについてざっくりまとめてみた

目次 目次 アルゴリズムとは より良いアルゴリズムとは C++のキーポイント main関数 cout(シーアウト) コメントアウト 全角文字 #include <bits/stdc++.h> using namespace std; プログラムの書き方とエラー 3種類のエラーの具体例 コンパイルエラー 実行時エラー 論理エラ</bits/stdc++.h>…