NinaLabo

個人ゲーム開発者の技術メモ

【StudyReport】 2021年7月

自分がどこに向かうべきか定まらないのですが、とりあえず興味のあるものから少しずつインプットを増やすようにしています。

 

書籍

Pythonでのアルゴリズムの解き方サンプルとしてざっと目を通しました。コード1行1行に解説があってわかりやすいものの、個人的にはちょっと説明が冗長な感じもしました。

 

大量の問題は後回しにしてとりあえず文章だけざっと読みました。ビックオー記法の説明が詳しくて良かったです。他の本だとなかなかきちんと説明している箇所がなかったので理解が深まりました。例題を解いてみると意外と簡単なようで難しい...対数がどうも苦手です... 

 

 Pythonを勉強しはじめたので、せっかくだしと思って機械学習の入門書っぽいものも買ってみました。2章のscikit-learnまで読みましたが、主にライブラリの使い方という感じでざっと目を通す程度で良さそうです。

LeetCode

Easyを10問ちょっとぐらい解きました。もっとがっつりやろうと思っていたのですが、1問1問結構時間も頭も使うので疲れちゃって大量にできなかったです...

https://leetcode.com/problemset/all/

# タイトル   備考
1 1. Two Sum Easy

二重ループだと\displaystyle O(n^2)だがHashを使えば\displaystyle O(n)で解ける。事前にHashを作らず、ループ内で値が見つからなければHashに追加していく。Premiumだが動画がわかりやすい

2

121. Best Time to Buy and Sell Stock

Easy \displaystyle O(n^2)ではなく2つの変数を使って\displaystyle O(n)で解く
3 953. Verifying an Alien Dictionary  Easy 単純な文字列比較問題
4 20. Valid Parentheses Easy 括弧の対応関係が正しいかをスタックで解く
5 53. Maximum Subarray Easy

全パターン検索だと\displaystyle O(n^2)だが、動的計画法(DP)のKadane's Algorithm (カデインと読むらしい)を使えば\displaystyle O(n)で解ける。下記の動画がわかりやすい。

https://www.youtube.com/watch?v=86CQq3pKSUw

また、少し遅くなるが分割統治法(divide-and-conquer)を使えば\displaystyle O(nlogn)で解ける

6 415. Add Strings  Easy 桁をそれぞれUnicode差分で数字にして足していくだけ。ただそれでも初見だと一瞬戸惑う
7 7. Reverse Integer Easy 10の余りで桁を取り出すのと前の数字にx10して桁を足すのを同じループ内でやると\displaystyle O(logn)で解ける
8 176. Second Highest Salary Easy 急にSQLの問題でびっくりした。こんなのもあるのか...Maxより小さいものの中でMaxを取れば2番目の値が取れる
9 125. Valid Palindrome Easy 回文か判定する問題。外側から内側に向かって比較していけばいいだけ
10 680. Valid Palindrome II Easy 回答がない問題でどこまでやればいいのかちょっと微妙
11 696. Count Binary Substrings Easy

英語の読解力のなさも相まって問題がわかりにくい。動画を見てようやく理解できた

https://www.youtube.com/watch?v=MGPHPadxhtQ

       
       

 

 

【StudyReport】 2021年6月

毎日学習時間を計って1週間ごとに記事を上げようと思っていましたが早々に挫折しました。時間をはかるのがまず面倒で... ふとした時に本を手にとって読んだり、お風呂で読んだりするともう時間がわからなくなり、計画的に何かをやるのは向いてないと痛感しました....とりあえずその月にやったことだけ書くようにしてみようと思います。

 

書籍

 (P160まで読んだところで中断)

練習問題が豊富にあるので手を動かしながら読めそうということで買ったのですが、結論から言えば初心者が最初に読む本ではなかったです。サンプルコードが載っているのでまったく理解できないということはないのですが、概要を読んで、まずは自分で考えてコードを書いてみて、その後解説を読んで、わからないところはネットで調べて、さらにコードを直して....みたいなことをやってると全然進まなくて....全部で450ページぐらいあるのに1日数ページしか進まないので焦ってきて挫折しそうだったので一旦この本は中断することにしました。とは言え、内容は面白かったですし問題も豊富にあるので、ある程度全体を広く理解できた段階で戻ってこようと思います。

 

最初にこれを読んでおけばよかったと思いました。図入りで解説が丁寧ですし、いくつか知らなかったことも出てきたので面白かったです。挫折せずに最後まで読めました。

 

アルゴリズムの勉強をC++でやろうとしてたのですが一応大学でやってはいたもののやっぱり業務で使わないとどうにも手に馴染まないし、だったらもっと簡単な言語のほうがやりやすいかなと思いPythonの入門書を読みました。シンプルな上に便利な言語仕様が多くてC++よりこっちのほうが好きになれそうな気がしてます。機械学習関連の本を読むときにもPython知ってたほうが便利ですしね。

 

 

【StudyReport】 2021/5/29〜6/5

頭痛と吐き気と不眠と動悸であんまり進まないですが、まったくやらないよりはマシと思って少しずつ進めようと思います。

 

週間サマリー

アルゴリズムとデータ構造:P33(P53〜P59, P117〜P142):(week 6:18 / total 12:17)

日別内訳

2021/5/29(土)

体調不良でおやすみ

2021/5/30(日) 

C言語によるはじめてのアルゴリズム入門:P7(P53〜P59):(day 1:54 / week 1:54)

正規分布ガウス分布)】

\displaystyle N(m, σ^2)=\dfrac{1}{\sqrt{2πσ^2}}e - \dfrac{(x-m)^2}{2σ^2}

*標準偏差σ(シグマ)、平均m, 分散σ^2

【Unity道場スペシャル 2017札幌】乱数完全マスター

正規分布の密度関数を意味的に理解する | AVILEN AI Trend

【ボックスミュラー法】

一様分布に従う確率変数から標準正規分布に従う確率変数を生成させる手法

 \displaystyle x=σ\sqrt{-2logX}cos2πY + m

 \displaystyle y=σ\sqrt{-2logX}sin2πY + m

【台形則の定積分

\displaystyle \int_{a}^{b}f(x)dx=h*(\dfrac{1}{2}(f(a)+(b))+f(a + h)+ .. + f(a + (n - 1)h))

【シンプソン則の定積分/テイラー展開

だんだん頭が追いつかなくなってきた。入門書を買ったつもりだったけど...

初心者用 テイラー展開解説

2章の数値計算は一旦後回しにして3章のソートとサーチをやってみることにする 

2021/5/31(月) 

C言語によるはじめてのアルゴリズム入門:P10(P117〜P126):(day 1:17 / week 3:11)

 直接選択ソート、バブルソート、シェイカーソート

2021/6/1(火) 

C言語によるはじめてのアルゴリズム入門:P7(P127〜P133):(day 1:54 / week 5:05)

 基本挿入法シェルソート

2021/6/2(水) 

C言語によるはじめてのアルゴリズム入門:P9(P134〜P142):(day 0:25 / week 5:30)

 逐次探索と番兵、二分探索

2021/6/3(木) 

おやすみ

2021/6/4(金) 

おやすみ

2021/6/5(土) 

C言語によるはじめてのアルゴリズム入門:P7(P143〜P149):(day 0:48 / week 6:18)

マージ、文字列の照合

【StudyReport】2021/5/22〜5/28

次に会社で嫌なことがあった時にすぐに転職できるように準備することにしました。実際に転職するかどうかはわかりません。一部の同僚には恵まれているのでずっといる可能性もあります。

実際に応募したわけではないので認識が甘い可能性もありますが、今と同じような仕事をする前提で会社を選り好みしなければそれほど大掛かりな準備は必要ないのかもしれません。 ただ、現状にはうんざりしているところもあるので、どうせ転職するなら今までとはちょっと違ったことをやってみたくなりました。明確にはまだ決めてはいないものの、準備なしではいざとなった時にどこにも入れる気がしないので、もう一回勉強し直すことも含めてやってみようかと思います。

 

週間サマリー

アルゴリズムとデータ構造:P53(開始〜P53):(week 6:09 / total 6:09)

日別内訳

2021/5/22(土)

・何をやるかに想いを馳せる

amazonアルゴリズムとデータ構造の入門書を買う

2021/5/23(日) 

C言語によるはじめてのアルゴリズム入門:P15(開始〜P15):(day 2:30 / week 2:30)

*漸化式(ぜんかしき)

n!=n*(n-1)*(n-2)...2*1

nPr=\dfrac{n!}{(n-r)!}

nCr=\dfrac{n!}{r!*(n-r)!}

nCr=\dfrac{(n-r+1)}{r} * nC_{r-1}(n!でオーバーフローしないために漸化式)

*Horner法

多項式f(x)=a_nx^n+a_{n-1}x^{n-1}...a_1x...a_0

Horner法: f_i=f_{i-1}x+a_{n-i}f_0=a_n

2021/5/24(月) 

C言語によるはじめてのアルゴリズム入門:P14(P15〜P28):(day 1:40 / week 4:10)

_{n}C_{r}=_{n-1}C_{r-1} + _{n-1}C_{r}

ヒストグラム、順位付け

2021/5/25(火) 

C言語によるはじめてのアルゴリズム入門:P8(P29〜P36):(day 0:43 / week 4:53)

ランダムな順列、モンテカルロ法

円の面積:r * r * π、半径1の円の内外判定(三角関数x^2 + y^2 \lt= 1

2021/5/26(水) 

履歴書を完成させる

C言語によるはじめてのアルゴリズム入門:P15(P37〜P51):(day 1:16 / week 6:09)

ユークリッド互除法、エラトステネスのふるい

一様乱数(線形合同法):\displaystyle X_{n} = (AX_{n-1} + B) mod M

2021/5/27(木) 

C言語によるはじめてのアルゴリズム入門:P3(P51〜P53)

カイ二乗検定\displaystyle \chi^2=\sum_{i=1}^{M}\dfrac{(f_i - F_i)^2}{F_i}

2021/5/28(金) 

体調不良でおやすみ

【Unity】UIElementsの導入

Unity2020になってEditor利用だけだったUIElementsがランタイムのゲームUIとして使えるようになったようです。

 

UIElements 開発者ガイド - Unity マニュアル

f:id:ninagreen:20201116023428p:plain

 

原始的なIMGUIに始まり、NGUIが席巻したと思ったら、UGUIがUnityから出て、落ち着いてきた頃にUIElementsに変わるとか、UI領域は技術の陳腐化が早すぎて本当に大変です。

最終的にUIElementsがUGUIに取って変わるのか、それとも結局UGUIが残り続けるのかはわかりませんが、ローグスフィア2の開発はUIElementsでやってみようかと思ってます。

 

まずはインストールして簡単なものを表示してみるところまでやってみます。

環境は Unity2020.1.13f1を使用しています(2020/11/16時点の最新)

 

UIElementsをインストール

Window > PackageManager を開く

まだpreviewの状態のため、左上の+ボタンから「Add package from git URL」を選択して 「com.unity.ui」を入力してインストールします

*昔はcom.unity.ui.runtimeだったようですがそちらは古いようで、com.unity.uiが新しいようです。

 

Runtime package 0.0.4 - Unity Forum

com.unity.ui.runtime is not supported, it's the old version and name of the pacakge.

You need to use the new package going forward "com.unity.ui" (no .runtime)

"com.unity.ui": "1.0.0-preview.3"

 

しばらくするとUI ToolKitのインストールが完了します

f:id:ninagreen:20201116032158p:plain

 

同じく「com.unity.ui.builder」を入力してUI Builderもインストールします。

f:id:ninagreen:20201117011750p:plain

 

レイアウトの生成(UXML作成)

Window > UI ToolKit > UIBuilderを開いてレイアウトを生成

f:id:ninagreen:20201117013011p:plain

UIBuilderの詳細な使い方は追々調べることにして、ひとまずは簡単なレイアウトを作成して

f:id:ninagreen:20201117013146p:plain

File > Save で適当な場所にuxmlファイルを保存

f:id:ninagreen:20201117013233p:plain

 

UIDocumentのアタッチ

シーン上に適当なオブジェクトを作成してUIDocumentをアタッチ

f:id:ninagreen:20201117025248p:plain

・PanelSettingsには

Projectウィンドウで右クリック > Create > UI ToolKit > Panel Settings Asset

で作成したPanelSettingsを設定する

・Source Assetには先ほど保存したuxmlファイルを設定する

 

再生

Unityを再生するとGameSceneにUIが表示されます。

再生したまま、UI Builderのレイアウトを編集できるのは便利で良いですね。

 

参考資料 

www.youtube.com

 

【LeetCode】20. Valid Parentheses(Easy)

【最初に】

LeetCode 8個目に挑戦です

leetcode.com


 

 

【問題】

次の '('')''{''}''['']' の文字だけを含んだ文字列の括弧対応が正しいか判定せよ。空文字列は正しいと判定すること。 

Example 1:

Input: "()"
Output: true

Example 2:

Input: "()[]{}"
Output: true

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true

 

【とりあえず】

思いつくのは左括弧の場合はStackに格納し、右括弧の場合はStackから取り出して括弧の対応が正しいか判定する、かな。

f:id:ninagreen:20191113020438p:plain

 

 できた!

f:id:ninagreen:20191113020503p:plain

【解答を見る】

だいたい↑と同じことやってた

 

【最後に】

最初に解いた内容と解答が同じだったのははじめてだな

 

【LeetCode】104. Maximum Depth of Binary Tree(Easy)

【最初に】

LeetCode 7個目に挑戦です

leetcode.com

 

 

【問題】

与えられたバイナリツリー(二分木)の最大深度を求めよ

Example:

Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its depth = 3.

 

【とりあえず】

再帰処理で全探索する。左と右で深度の大きいほうを返し続ければ最大深度になるはず。

f:id:ninagreen:20191112023129p:plain

 

できた!

f:id:ninagreen:20191112023152p:plain

 

【解答を見る】

と思ったらPremiumに加入してないと解答が見れないようになってる!仕方ないので、Discussionを見てみる。あ、そうか別にCheckChildとか別関数を作らなくても、もともとのmaxDepth関数を再帰させればいいのか。

 

f:id:ninagreen:20191112024114p:plain

引数が子要素を持たないノードの場合、maxDepth(root->left) も maxDepth(root->right) も0が帰ってくる。その状態から+1ずつしていけば深さを求めることができる。

 

できた!

f:id:ninagreen:20191112024439p:plain

余計なメソッド呼び出しがなくなったからか、実行速度も16msから8msにあがってる!

 

【最後に】

 Solutionは無料で全部見れると思ってたのに・・(TーT