競技プログラミングで度々必要になるヒープをまとめてみる。 ヒープとは ヒープは木構造の1つで、二分木として表現される。 各ノードがその子ノードより小さい（or 大きい）か等しくなるように配置される。 そのため根ノードが最小（or 最大）になる。 この…

競プロでは最大公約数や最小公倍数が度々出題される。 今回は最大公約数や最小公倍数についてまとめてみる。 最大公約数はGreatest Common Divisorを略してgcdやgと表記されることがある。 最小公倍数はLeast Common Multipleを略してlcmやlと表記されること…

1次元の累積和 以下の問題を考える。 atcoder.jp 連続するk個の総和の最大値を求める問題。 シンプルに考えると、連続するk個の値はn-k個のパターンがあり、それぞれを求めて最大値を求めていく。 これだと、連続するk個の総和を求める処理が計算量にするとO…

競技プログラミングで度々出題される素数判定についてまとめる。 単純な素因数分解問題 以下のような単純に素因数分解する問題を考える。 https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_A&lang=ja 2から√nまでの整数で割っていき、割り…

競技プログラミングで有名なアルゴリズムに動的計画法（DP）がある。 無駄に同じ計算をしないように、ある条件下での計算結果を配列などに保存しておき、計算を高速化するためのアルゴリズム。 言葉で言ってもぴんとこないので例題で考えてみる。 フェボナッ…

Linuxのプロセス周りについて自分なりにまとめてみる。 プロセス プロセスとはコンピューターシステムのプログラムの実行単位。 プロセスはOS上で実行中のプログラムを指し、プログラムの実行単位である。 OSがファイルを実行する際にメモリやCPUなどのリソ…

コンピューター上では全ての処理がメモリにロードして実行される。 メモリ管理の仕組みについて書いてみる。 物理メモリと仮想メモリ プログラムが実行されてプロセスが生成されると、カーネルは生成されたプロセスにメモリを割り当てる。カーネルによってプ…

Linux周りの概要について調べたことをだらだらと書いてみる。 コンピューターシステムの概要 まずコンピューターがプログラムを実行する流れ。 まず、プログラムを実行する。 プログラムのデータが格納されている補助記憶装置（ストレージデバイス）から主記…