アルゴリズム、学んでる①
概要
"問題解決のための「アルゴリズム × 数学」が基礎からしっかり身につく本"という本を読んだ際の記録です。
本の概要、自分が学んだことを記載させていただきます。
以下、amazonの商品リンクになります。
動機と簡単な自己紹介
paizaのプログラミングスキルチェックの問題を解いた際に、数が少ないテストケースに関しては、自分が書いたコードで回答することができたのですが、提出するとタイムアウトなってしまい、テストに失敗しました。
原因として、for文のなかでfor文を回しているなど実行に時間がかかるような処理になってしまっていることだと考え、なんとなく聞いたことのあったアルゴリズムの考え方を学んでみようと考えました。
▼paiza プログラミングスキルチェック
また、この本を学習するにあたって、基準となりそうな私の情報を記載します。
- 数学は何年か前に数Ⅲまで学習済み
- 高校までの教科で好きなのは数学
- paizaのプログラミングスキルチェックはBランクは解ける、Aランクはたまに解ける
第2章 数学の基礎知識
2.2 基本的な演算と記号
【pythonでの計算方法】
あまり → 8 % 5
絶対値 → abs(-3)
累乗 → 10 ** 2
ルート → math.squt(9)
【計算回数】
ざっくり何回の計算が必要かを考えることによって、実行時間を予測する
ランダウのO記法を利用すると、「ざっくりN回」は「O(N)」と表せる
典型的なアルゴリズムは計算量ごとに分類できる
【その他の基本的な数学の知識】
必要条件と十分条件 → 範囲の広い方が必要条件
【コラム】
以下の例題など、組み合わせの全探索を行うとき、次の手順で検索できる。
N枚のカードがあり、それぞれに整数が書かれている。選んだカードに書かれている整数の総和をSにするような選び方が存在するか判定せよ。
N枚のカードがあるとき、選び方は2のN乗通りとなる。
それぞれの選び方に、0から2**N-1の番号を割り当てる。
※その番号を2進数で表したとき桁数がN桁
「番号が3の時、番号を2進数で表すと011なので、3枚のうち、2枚目と1枚目のカードを選ぶ」というように番号と選ぶカードを対応させる。
これをforループで回して総和がSになるか判定する。
0から2**N-1までの番号をforループで回す際、N枚のカードを選ぶか選ばないかは以下の方法で判定できる。
3番目の組み合わせのの場合、 i (1<=i<=N) 枚目は、
- 「3 & 2 ** (i-1) == 0」の時選ばない。
- 「3 & 2 ** (i-1) != 0」の時を選ぶ。
この判定方法に関しては、仕組みを理解できていない状況ですので、仕組みが分かる方いらっしゃいましたら、教えていただけますと幸いです。
これまでの知識で知っていることは記載を省いております。ご了承ください。
勉強の仕方や、ブログの書き方など、アドバイス等ございましたらコメント等よろしくお願いいたします。次は3章から勉強していきます。