前提知識の要らない、純粋なひらめきで解くアルゴリズム問題
それをコードで実装してみたり...
algorithmic-creativity/
├── README.md <- ⭐️
├── algorithms/ <- その他の問題
│ ├── README.md
│ └── ...
│
└── 12coins/ <- 12コイン問題を解く・プログラムに解かせる・解説
│ └── ...
│
└── DP/ <- 動的計画法
│ └── ...
│
└── search algorithm/ <- グラフアルゴリズム
└── waterjug.py <- ex. "8Lと3Lの容器で5Lを作れ"といった問題をBFSで解く
以下、個人的なお気に入り順 My favorites:)
Find the 1 fake coin out of 12 using a scale just 3 times. Is it heavier or lighter?
12枚のコインのうち一枚のみ重さが異なる。天秤を3回のみ使用して重さの異なるコインはどれか・他より重いのか軽いのかも特定するアルゴリズム
-
偽物のコインが他より重いのか軽いのかわかっていないところが面白い 単純に1/2ずつ絞っていくのではいけない
-
考えられる状況は、偽物コインの番号12通り ｘ 重い軽いの2通り = 24通り < 天秤3回で表せる状況は 3^3 = 27通り なので理論的には解けるはず
ただしこの条件で考えるにはほぼ毎回の天秤で3分岐を有効に使う必要がある -> どんな工夫ができるか
└── 12coins/
├── README.md
├── 12coins_explanation.md <- 解説
├── play_12coins.py <- 実際に遊んでみる
└── solve12coins.py <- プログラムに解かせる
Find the majority element in O(1) space.
数字（自然数）がN個、どんどん流れてくる。全ての数字が流れ終わった時点で、過半数登場した数字があることは保証されている。この時どの数字が過半数現れたかを、以下の計算量で特定する。
- 時間計算量(Time) O(N)
- 空間計算量(Space) O(1) 🤯
つまり過去に登場した数字と登場回数のmappingは作れないということ!
Find all elements that appear more than ⌊N/3⌋ times in a stream.
過半数判定アルゴリズムの進化版
「N/3回より多く」 登場したすべての数字を特定するアルゴリズム。
Ex: 3 -> 2 -> 3 -> 1 -> 2 -> end => [3, 2] (※N=5なので、5/3=1.66... より多く登場した3と2が答え)
- 時間計算量(Time) O(N)
- 空間計算量(Space) O(1) 🤯
N個の異なるデータが流れてくる。Nがいくつかはデータを全て読み終わった後に初めてわかる。データは巨大なため、どこかに全て保存しておくことはできない。
この時、これらのデータから 完全にランダムなデータ を選ぶ(つまりNがいくつであっても、N個のデータのうち一つを1/Nの確率で選ぶ)にはどんなアルゴリズムを使用すればいい？?
例：
nab;eotrfa
eorif
gavoeru
anbero
noevar
end
"noevar" is selected with 1 / 5 probability
等確率保証アルゴリズムの拡張。1つではなく3つのデータを等確率で選びたい時どうする？
python3 reservoir_3sampling.py
neaor
dnvaorb
wefn
ds
nvrp
espdi
e
vnoe
d
vrnk
nwefo
end
"vrnk", "nwefo", "espdi" are selected by 3 / 11 probability.
- 1から5までの整数を等確率で出力する関数（乱数生成器）がある
- これを使って、1から7までの整数を等確率で出力する関数を作るアルゴリズムは？
Maximize profit by choosing a single day to buy and a single day to sell.
- ある銘柄の日々の価格（自然数）が、1日目から順に流れてくる。
- 「一度だけ株を買い、その後（未来）の日に一度だけ株を売る」ことができる。
- この時、得られる 最大の利益 を計算するアルゴリズム（利益が出ない場合は0とする）。
Ex: 7 -> 1 -> 5 -> 3 -> 6 -> 4 -> end => 5 (価格1で買い、価格6で売るため)
- 時間計算量(Time) O(N)
- 空間計算量(Space) O(1) 🤯
過去の価格履歴を全てリストに保存しておくことはできない。
- 不均一なコイン（表が出る確率が例えば70%など、不明かつ偏りがあるコイン）が1枚ある
- このコインを使って、正確に50%の確率で「勝ち」か「負け」を決めるゲームを作るアルゴリズムは？
Sort 2 types of items in-place.
A,BがランダムにN個混ざった文字列の各文字を、A -> B または B -> Aに変換できるとき、AA...AB...BBのようにA,Bを分断させるのに必要な最短変換回数を
- 時間計算量(Time) O(N)
- 空間計算量(Space) O(1) 🤯 で計算する
- 二つの卵と100階建てのビルがある。ある階から下の階では卵は割れず、ある階より上の階からは卵が割れる。
- この境目が何階なのかを特定したい時、最悪試行回数をなるべく少なくしたい時どのような戦略を立てればいい？？
⭐︎ 最悪試行回数が最小になる時 ＝ どのような条件に対しても同一の最悪試行回数で特定できる時