データ構造配列, Trie木, 文字列, prefix

Trie木は、効率的な検索(retrieval)のために使われるデータ構造です。文字列などの先頭部分(接頭辞: prefix)の共通部分を共有して保存することで、\(O(M)\) での検索を可能にします。(文字列の長さを\(M\) と ...

2020年3月21日数学最大公約数, 配列, 結合則

配列 A が与えられて、その全ての要素の最大公約数(GCD)を求めることを考えます。2つの最大公約数だけではなく、N個の要素の最大公約数を求めます。

例:

Input: A = {36, 12, 48}

2020年3月20日数学最小公倍数, 配列, 結合則

配列 a の全ての要素の最小公倍数(LCM: least common multiple) を求めるアルゴリズムについてです。2つの最小公倍数だけではなく、N個の要素の最小公倍数を求めます。

Input: a = {1, ...

2020年3月20日その他区間和, 区間, 累積和, 配列

要素数 N の数列 \(\{a_0, a_1, a_2, \cdots, a_{N-1}\}\) が与えられた時に、区間

累積和の気持ち累積和とは

累積和は、「始めから i 番目までの和を前処理で計算したもの」です

2019年11月25日データ構造入門, データ構造, 配列

配列とは

配列は、連続したメモリ領域にデータを格納するシンプルなデータ構造です。データにアクセスしたい時は、配列の先頭から見て何番目のデータを取り出したいか(index)を指定します。

プログラミングを学ぶときに、必ずと学ぶ ...