皆さんご存知の二分探索。この応用について今回は書いていきたいと思う。
二分探索の一般化
二分探索とはつまり、範囲を特定することである。
例億マス計算
そこで今回は二分探索を使う下記問題を解いていく
C - 億マス計算AtCoder is a programming contest site for anyone from beginners to
experts. We hold weekly programming contests online.AtCoderAtCoder Inc.
[https://atcoder.jp/contests/arc037/tasks/arc037_c]
愚直に2重ループで解くと
O(N²)になるため、時間が足りなくなる
blog-binary_search_2blog-binary_search_2. GitHub Gist: instantly share code,
notes, and snippets.Gist262588213843476
[https://gist.github.com/kooooohe/8cc33e0f1e目次
* きっかけ
* Two’s complement(2の補数)
* 累積和
* BIT(binary indexed tree)
* 転倒数
きっかけ
先日友人から下記の結果についての質問がきた。
package main
import (
"fmt"
)
func main() {
const a = ^0
fmt.Println(a)
}
皆さんも予想してみてほしい。
実行は↓から
The Go Playground [https://play.golang.org/p/qpWRExXsJ8E]
^0 はNOTでbit反転なのだが、値はintegerのmax値になることなく
`-1` となる。
これは、ご存知Signed Integer で全bitが1の場合はTwo’s complement(2の補数)となり `-1`が出力される。
そして、Goのconstは数値が右辺に来た場合はSigned Integer Typeとデフォルトで解釈する。
では uintのmaxの値をbit反転で取りたい場合はというと
package
nuxt.jsAmplifyを使わずに、認証の部分のみをCognitoに任せてNuxt.jsで使いたい
今回はこの中のAuth.tsのみを使用する。
amplify-js/Auth.ts at master · aws-amplify/amplify-jsA declarative JavaScript
library for application development using cloud services. - amplify-js/Auth.ts
at master · aws-amplify/amplify-jsGitHubaws-amplify
[https://github.com/aws-amplify/amplify-js/blob/master/packages/auth/src/Auth.ts]
Amplifyを使用して、認証画面の自動生成等を行っている記事は多く見かけた。
認証にのみCognitoを使うケース&認証画面はすでにあるものを使いたい場合の記事が少なかったので、こちらに書き記す。
* 下準備
* login処理
* Middlewa
前回
DP(Dynamic Programming)をVue3.0 With TS & PrimeVUEで視覚化するやることMediumkooooohe
[https://medium.com/@1211lta/dp-dynamic-programming-%E3%82%92vue3-0-with-ts-primevue%E3%81%A7%E8%A6%96%E8%A6%9A%E5%8C%96%E3%81%99%E3%82%8B-2c84c749f340]
区間DP
DP(動的計画法)の中で区間を状態として表すものをいう。
[a,b,c,d]とあった際に、
* a→b cost 3
* a→c cost 10
* b→d cost 2 etc
といったような条件が有り、適切に区切ったさいの 最小、最大のコストを取るか見積もる際などに使われる
※なので今回の区切る個数は 添字0~4の5つとなる
dp[i][j] = (i,j] の最適解 となるように計算していく
イメージ図参考問題(応用)
https://judge.u-aizu.ac.jp/onlinejudge/d
やること
典型的な動的計画法（Dynamic Programming)を使うナップサック問題をVue3.0の学習がてら視覚化していく
技術
* Vue3.0
* TypeScript
* PrimeVUE
PrimeVUE [https://primefaces.org/primevue/showcase/#/]
PrimeVUEはVue3.0に対応しており、良さげだったので使用。
あとせっかくなのでVueのCompositon APIで書いてみた。
余談：
Vue3.0のビルドが早くて驚いた。
また、Compositon APIを使うことにより型が厳密に定義できとても良いなと感じた。
ナップサック問題
ナップサック問題 - Wikipediaウィキメディア財団Contributors to Wikimedia projects
[https://ja.wikipedia.org/wiki/%E3%83%8A%E3%83%83%E3%83%97%E3%82%B5%E3%83%83%E3%82%AF%E5%95%8F%E9%A1%8C#:~:text=%E3%83%共通鍵暗号の1つであるS-DES(Simplified DES)をGoで実装してみたその１~key generate編~
前回は公開鍵暗号の1つであるRSA暗号を実装してみたが、今回は共通鍵暗号の1つであるS-DESを実装していく。
公開鍵暗号の1つを実装してみたのであれば、共通鍵暗号の1つも実装しないわけには行かないだろう
公開鍵暗号の1つであるRSA暗号をGolangで実装してみる注意: ところどころ簡素化してあるところはありますMediumkooooohe
[https://medium.com/@1211lta/%E5%85%AC%E9%96%8B%E9%8D%B5%E6%9A%97%E5%8F%B7%E3%81%AE1%E3%81%A4%E3%81%A7%E3%81%82%E3%82%8Brsa%E6%9A%97%E5%8F%B7%E3%82%92golang%E3%81%A7%E5%AE%9F%E8%A3%85%E3%81%97%E3%81%A6%E3%81%BF%E3%82%8B-a8d8ad01b903]
GitHub - kooooohe/SimplifiedDE
結論
O(log (n))となり
1000項目めを求めるには0.000199s
10000項目めは0.000405sで求められました。
完成品
https://github.com/kooooohe/fibonacci/blob/master/main.g
[https://github.com/kooooohe/fibonacci/blob/master/main.go]o
通常の再帰を使った簡単な解き方
fib_blog_1.goGitHub Gist: instantly share code, notes, and snippets.Gist
262588213843476
[https://gist.github.com/kooooohe/17818f61bcfe287eb2709466eaccbf7f]func fib(num int) int {
if num <= 1 {
return num
}
return fib(num-2) + fib(num-1)
}
これだとO(2^n)となるためかなり遅い。
※メモ化については今回は割愛 注意: ところどころ簡素化してあるところはあります
公開鍵暗号とは
> 公開鍵暗号Public-key cryptography
[https://en.wikipedia.org/wiki/Public-key_cryptography]暗号化
[https://ja.wikipedia.org/wiki/%E6%9A%97%E5%8F%B7%E5%8C%96]復号
[https://ja.wikipedia.org/wiki/%E5%BE%A9%E5%8F%B7]暗号方式
[https://ja.wikipedia.org/wiki/%E6%9A%97%E5%8F%B7%E6%96%B9%E5%BC%8F]
公開鍵暗号 - Wikipediaウィキメディア財団Contributors to Wikimedia projects
[https://ja.wikipedia.org/wiki/%E5%85%AC%E9%96%8B%E9%8D%B5%E6%9A%97%E5%8F%B7]流れ
* 2種類の素数p,qを準備する(p != q)
* 各素数の積 Nを計算 (p * q)
ざっくりしたいこと
Vue.js でできたStatic websiteを独自ドメイン with SSLで公開する
SSL証明書の発行、サブドメイン作成などもすべて、できる限りTerraformで作成する
使用技術:
・Vue.js
・Terraform(v0.12.26)
・GitHub Actions
その他実行環境:
* aws-cli/2.0.19
* Python/3.8.3
* Linux/5.4.0–37-generic botocore/2.0.0dev23
Vue.js
Static websiteの作成
Terraform
前提: State用のS3は作成済み。ドメインはRoute53で取得済み。
Deployで作ったものはすべて壊せるようにしたい
S3,Cloud Front,ACM,Route53あたりをTerraformで触っていく。
以下のことをすべてTerraformで自動化する
S3:Privateで作成＆Force Deleteの有効化
blog-terraform-aws-static-site-s3.tfGitHub G
クリーンアーキテクチャをTypeScriptで実装する際のDIをInversifyJSを使ってみた
* Firebase & Firestore & Hosting
* Nuxt.js & TypeScript
を使い、サービスを実装する際にクリーンアーキテクチャを採用した。
その際のDIライブラリとしてInverstifyJSを選定
InversifyJSInversifyJS is a lightweight inversion of control (IoC) container
for
TypeScript and JavaScript apps.http://inversify.io/Remo H. Jansen
[https://inversify.io/]
想定サービス
レストランの一覧を取得するもの
Firestore
とりあえず今回はPublicなRestaurantデータを取得するものを作成、
データモデルはこんな感じ
Clean Architecture
有名な図
これをもとにフロント側を実装
Inverstify JS
GitHub -
構成
全体のソースコードはこちら
GitHub - kooooohe/notify-github-todoContribute to kooooohe/notify-github-todo
development by creating an account on GitHub.GitHubkooooohe
[https://github.com/kooooohe/notify-github-todo/tree/master]まずは開発環境で試してみる
docker-compose.yaml
medium-blog-cloud-run-docker-compose.jsmedium-blog-cloud-run-docker-compose.js.
GitHub Gist: instantly share code, notes, and snippets.Gist262588213843476
[https://gist.github.com/kooooohe/03d99ac8d08c7ee46dd894c122fd1d41]version: "3"
services:
n望月教授のIUT理論を使用した、ABC予想の証明査定が終わったというニュースが流れてきた。
もともと、証明が終わったというニュース自体は数年前から知っていた。
エンジニアリングも数学も何でもこういった、新しい概念やモノが生まれてくるのはワクワクする。
それの影響を受けて、一般向けにその内容を噛み砕いてくださっている下記の本を購入し読んでいる。
宇宙と宇宙をつなぐ数学 IUT理論の衝撃 | 加藤 文元 |本 | 通販 | AmazonAmazonで加藤 文元の宇宙と宇宙をつなぐ数学
IUT理論の衝撃。アマゾンならポイント還元本が多数。加藤 文元作品ほか、お急ぎ便対象商品は当日お届けも可能。また宇宙と宇宙をつなぐ数学
IUT理論の衝撃もアマゾン配送商品なら通常配送無料。Amazon加藤 文元
[https://www.amazon.co.jp/%E5%AE%87%E5%AE%99%E3%81%A8%E5%AE%87%E5%AE%99%E3%82%92%E3%81%A4%E3%81%AA%E3%81%90%E6%95%B0%E5%AD%A6-IUT%E7%90%86%E8%AB%96 
