997. Find the Town Judgeを解いた

997. Find the Town Judge

leetcode.com

町にN人住んでおり、彼らは1からNの数字でラベリングされている。 この中に一人だけ裁判官がいるという噂があるので、それを特定する。

裁判官が存在する場合の条件は以下のとおり。

  1. 裁判官は誰も信じない
  2. (裁判官を除く)全員が裁判官を信じる
  3. この1.と2.を満たす人が1人だけいる

trustという配列が与えられ、trust[i] = [a, b]aはbを信じるということを意味する。上記条件が満たされる場合はそのラベルを返し、それ以外の場合は-1を返す。

Example 5:

Input: N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]

Output: 3

My Answer

以下のようなコードになり、2回目の提出でAC(Accepted)が出た。時間計算量はO(n+t)、空間計算量はO(n)となる。

class Solution:
    def findJudge(self, N: int, trust: List[List[int]]) -> int:
        ppl = set()
        score = [0 for i in range(N)]
        for i in range(len(trust)):
            ppl.add(trust[i][0])
            ind = trust[i][1]
            score[ind-1] += 1 
        if len(ppl) == N:
            return -1
        maxNum = max(score)
        if score.count(maxNum) == 1:
            return score.index(maxNum) + 1
        return -1

実行速度は780 msとなり、全体の85.63 %の参加者より速い結果となった。単純な英語力不足から、問題の意味を正しく理解するのに時間がかかってしまった。最終的に、問題を翻訳していて上記コードはたまたまACしているだけと気付いた。

Best Answer

この問題の解答はプレミアム会員でないと閲覧することができなかった。こういう時は大抵問題についてのディスカッションフォーラムを参照するかYouTubeにある解説動画を探すようにしている。

www.youtube.com

動画内の説明はJavaで記述されていたので、Pythonで書き直した。

class Solution:
    def findJudge(self, N: int, trust: List[List[int]]) -> int:
        count = [0] * (N+1)
        for t in trust:
            count[t[0]] -= 1
            count[t[1]] += 1
        for i in range(1, N+1):
            if count[i] == N-1:
                return i
        return -1

裁判官は誰も信じないので、信用する側を-1で調整するというアプローチ。そして、2回目の線形探索でN-1と一致するのであればそいつが裁判官だ。実行速度結果は812 ms(42.32%)になってしまったが、コードはかなりすっきりしたこともあり、こちらの方が解答としては望ましいだろう。

338. Counting Bitsを解いた

338. Counting Bits

leetcode.com

非負整数numが与えられるので、0からnumまでのiについて、2進数に変換したiに含まれる1の数を数えていき、それらを配列にしたものを返すことが求められる。

Example 1:

Input: 2

Output: [0,1,1]

注意点としてはFollow upとして時間計算量をO(n)で解くことを、ベストソリューションとして求められている点である。

Brute Force

初回の提出は、以下のようなコードになった。これは上記のFollow upを無視した解答であり、計算量はO(n*sizeof(integer))となる。

class Solution:
    def countBits(self, num: int) -> List[int]:
        res = []
        for i in range(num+1):
            res.append(str(bin(i)).count("1"))
        return res

実行速度の結果は92 msとなり、これは全体の45.81 %の参加者より速い結果となった。

ボトルネックとなっているのはcount()を使用している部分であると推察した。文字列に特定の文字がいくつ含まれるかという操作は、線形探索O(n)であるので、iの数が大きくなるにつれ計算量は増加してしまう。これをどうにかしたい。

Optimize

最終的に以下のようなコードとなった。任意の数字までを2進数表記したものを紙面上に書き出して眺めていると、bitの桁数が増加することで1の数は1つ増加することに加え、その桁数で表現できる数値範囲は、1つ前の桁数の数値範囲に依存することがわかった。直前の結果を再利用することができるので、DP(Dynamic Programming)の適用が考えられる。

class Solution:
    def countBits(self, num: int) -> List[int]:
        res = [0, 1]
        if num == 0:
            return [0]
        if num == 1:
            return res
        count = 2
        lim = 2
        ind = 0
        
        while count != num + 1:
            if lim == ind:
                lim *= 2
                ind = 0
            res.append(res[ind] + 1) 
            count += 1
            ind += 1
        return res

実行速度の結果は80 msとなり、これは全体の84.49 %の参加者より速い結果となった。劇的な実行速度の変化は生じていないが、他との比較値を見てみると十分に改善が行われたのではないだろうか。

デューク大学の「Java Programming: Solving Problems with Software」を修了しました

オブジェクト指向について本格的に学ぶために、以下のコースを受講しました。

 

www.coursera.org

  

ちなみに、全4コース構成となるため、今回のコースはオブジェクト指向についてはあまり触れられておらず、現在受講している第2コースの「Java Programming: Arrays, Lists, and Structured Data」でようやく話が出た程度です。

 

コース難易度は初心者向けと設定されていますが、全くの未経験者がこの講座から学習をスタートするのはおすすめしません。現にレビュー欄でも、初学者には難しすぎるといった意見も見受けられました。


各セクションの課題では、0からクラスファイルを作成する必要があります。大まかな全体設計の指示は入りますが、それでも大半のコードを自分で記述しなければならず、試験パートでは、課題で作成したプログラムを実際に実行させて回答をする必要があるため、きちんと動作しなければ次の週へ進むことができません。

自分がこれまで受けてきた講座では、あらかじめスクリプトが与えられておりその中の一部のコードを書き換えるものや、作成した一つの関数のみを提出するといった比較的ライトな課題が多く、受講当初は非常に負荷が大きかったことを覚えています。良い感じに補助輪が外せてきたということでしょうか。


自分はこのコースを受講するにあたって、以下のコースとオンラインクイズが前提知識として役立ちました。


・少なくとも1つのプログラミング言語について学ぶ

www.coursera.org

 

参考:Pythonを0から学びたいなら、ミシガン大学のPython for Everybodyという講座がおすすめ

 

Javaの肩慣らし

codingbat.com

 

参考:CodingBatに取り組んでいます

 

 

内容

- 1週目:イントロダクション&Javaの構文とセマンティクス

おなじみのHello World!からになります。この週のみでJavaの基礎の殆どをカバーするという中々のスピードっぷりです。Pythonでこうした基礎はある程度理解していたものの、そもそもクラス、インスタンス化とは何ぞや?という状態だったので、イントロダクションにも関わらず全週のなかで一番時間がかかりました。

 

- 2週目:Javaの文字列

おなじみ文字列操作です。Javaの実行においては環境構築をする必要はなく、BlueJという統合開発環境を用います。ただこのBlueJ、あまり評判がよろしくなく、自分の場合は主にVS Codeで課題を進めることが多かったです。


- 3週目:JavaCSVファイルと基本統計

以下のパッケージを使用して、CSVファイルを呼び出し、そこから任意の情報を取り出すプログラムを作成します。

 

www.dukelearntoprogram.com

 

- 4週目:ミニプロジェクト:赤ちゃんの名前

いわゆるキャップストーンプロジェクトになります。

 

雑感

このコースを受講してよかったと思えるのが、これまではやや座学中心でパッシブな講座が多かったのに対して、完全に課題が中心となってカリキュラムが進むので、各週に乗り越えるべき壁がきちんと設けられていたことです。自分で考えなければいけない部分がこれまでのコースに比べて格段に増え、最初は時間はかかりましたが良い感じにステップアップをすることができました。

 

ではでは。

Neural Networks and Deep Learningの講座に挑戦するも尾羽打ち枯らした話

ようやくこのブログでも、AIについて触れることが出来ました。自分がプログラミングの学習をスタートしようとしたのは、昨今のAIブームによるものが大きく、当初の自分の計画ではゼロベースからAIエンジニアを目指すという無謀極まりないものでしたが、紆余曲折を経て、現在はあくまでAIトレンドに関してはアンテナを張るだけに留まっています。

 

さて、本記事では、Deep Learning Specializationのプロジェクトの最初の講座であるNeural Networks and Deep Learningについて、振り返りをしたいと思います。

 

www.coursera.org

 

前置きとして、自分はブログタイトルにもあるように、この領域に関しては一切のアカデミックバックグラウンドを持ち合わせておらず、全くの素人であり、あくまで本記事は、素人目線による経験談にしか過ぎないことをご了承下さい。加えて、講座の具体的な内容については、既にQiitaの方でまとめられている方がいるので、興味のある方はこちらを参考にすることを推奨します。

 

qiita.com

 

この講座の魅力としては、講座の提供元が本場のdeeplearning.aiであることと、現代の人工知能界隈の最大の牽引者であるとも言えるAndrew Ngが講師を務められていることにあります。Andrew Ngについては、Courseraで非常に高い評価を得ている以下の機械学習の講座が有名で、こちらの講座をきっかけとして名前を知った人も多いのではないでしょうか。

 

ja.coursera.org

 

自分は深層学習を学ぶにあたって必要となる機械学習の知識に関しては、以下のUdacityの講座を履修することでカバーしたのですが、既に内容がうろ覚えになってしまっていることから、いずれ本領域への学習再開の目処が立った際には、まずは改めて上記講座からスタートを切りたいと考えています。

 

www.udacity.com

 

講座では2層NNとL層NNの構築を行い、猫の画像識別モデルを作成することが最終的な目標となっています。上記NNの実装に必要な各数理モデルの理論の説明→numpyを用いた実装、という流れを何度も繰り返しながら、ジュピターノートブック上で段階的な構築を少しずつ行っていく感じです。自分は数2Bの知識も怪しいレベルでしたので、微積やベクトル・行列を復習する必要がありましたが、そうした受講者に対しての補足回も含まれているという超絶親切っぷり設計です。しどろもどろになりながらも、一応の実装を終えることができ、猫の画像識別は成功しましたが、間違いなくこれまで受講した講座の中で、一番ハードな内容でした。

 

講座のねらいとしては、初めにニューラルネットワークディープラーニングの理論を受講者にしっかりと理解させることで、後々の講座で扱うことになる、TensorFlowに代表されるような主流AIフレームワーク群を極力ブラックボックスとして運用させないようにすることにあります。

 

また、それぞれのセクション末にはコラムとして、業界の著名人に対してNg先生がインタビューを行うパートがあります。そこでは「これから人工知能を学びたいと思っている人はどのようなキャリアを歩めばよいか」といった、我々が最も気になるであろう点についてクリティカルに触れられており、これを視聴するだけでも、何となくAIに興味を持たれている方にとっては、一見の価値があるのではないかと思います。

CourseraのUsing Python to Access Web Dataの講座でWebスクレイピングを学ぶ

前回では「ひとつのプログラミング言語」「データベース言語」について学ぶ事が出来るオンラインコース、「Python for Everybody Specialization」を取り上げました。

 

www.coursera.org

 

本記事では、さらにそのプロジェクトの中の一つの講座「Using Python to Access Web Data」について取り上げたいと思います。 お伝えした通り、自分はこの講座を受講したことでプログラミングの実用性を正しく理解することが出来ました。講座では、BeautifulSoup4というライブラリを用いて、Webスクレイピングを行います。このライブラリによって、HTMLを取得、解析することで、Web上の任意のソースを取得することができます。加えて、正規表現を活用することで、取得対象をより特定させることも学びます。

 

www.coursera.org

 

幸運だったのが、丁度この時期に実生活において初めて野良のエンジニアと交友を持つことができ、彼がこの講座のサポーターとしての役目を果たしてくれた事です。とりわけ、正規表現の利便性を説いていたのが印象的でした。

 

さて、現在は上記の2つの手法に加えて、Seleniumというツールをブラウザのオートメーションのために扱うようになりました(Webアプリケーションのテストツールなので、本来的な使い方ではないかもしれません)。Seleniumは上記講座では触れらていませんが、BeautifulSoup4、正規表現と組み合わせる事で、PythonによるWeb上での処理はかなり自由度が高まったのではないかと思います。

 

qiita.com

 

これまで取り組んでいた課題では、Webのインタプリタ上やCLI上で指定された結果を出す、といったものが殆どだったので、実際のプログラムの処理動作を(初心者にもわかりやすいように)視覚認識する機会にはあまり恵まれていませんでした。その点、Seleniumにおいては、ブラウザがその役目を疑似的に果たしてくれるので、「自分の書いたプログラムが視覚的に動いてくれている」ということを実感できる。 この体験は、自身のモチベーションを跳ね上げることに一役買ってくれました。

 

自身の最初のSeleniumの用途としては、明らかに手動でやる分には非効率的だろう、と考えられるタスクの自動化でした。これからもルーティンタスクについて存分に活用していきたいなと思っています。現在、思いつく限りでも日常生活においてWeb上の2、3つほどの単調なタスクを抱えているので、自身のスキルの拡張性が高まる機会だと思って貪欲に取り組んでいきたいと考えています。

Pythonを0から学びたいなら、ミシガン大学のPython for Everybodyという講座がおすすめ

前回書いた記事で取り上げたエンジニアに求められるスキルセットから、「ひとつのプログラミング言語」と「データベースの基本知識」について自身のこれまでの経験と照らし合わせていきたいと思います。

 

現在、自分が最も使用頻度が高い言語はPythonであり、Pythonからスタートした理由としては、そもそもプログラミングをスタートしたのがAIのブームに乗っかかろうとしたミーハーな気持ちからであり、加えて最初に受講したCS101でPythonが用いられていたためです。

 

www.udacity.com

 

その後、OO設計の理解やコーディングのクイズ集を解くために、Javaへと学習派生しましたが、最初のHello, World!出力だけでも、クラスや変数の型の宣言、コンパイルですら手間を感じずにはいられなかったということから、改めてPythonのシンプル且つ明瞭な設計思想の恩恵を実感しており、初学者に最も適した言語であると思います。

 

さて、自分がPythonについて、ようやくある程度の理解をする事が出来たなと自信を持つことが出来たのは、以下のCourseraの講座を修了した後になります。

 

www.coursera.org

 

最初に取り上げた、CS101はあくまでPythonを手段として用いることによって、計算機科学分野への案内をすることを目的としており、言語習得そのものにフォーカスをされた講座ではありません。(計算機科学を始点として学び始めるのはとても良いことだと思います)TechnicalDevGuideでも、CS101の後に薦められているのが、「少なくとも1つのオブジェクト指向プログラミング言語について学ぶ」であり、自分の場合はクラスセントラルでも評判の良かった上記のCourseraの講座を選択することにしました。*1

 

このスペシャライゼーションのプロジェクトは5つの講座を1つに統合したものであり、それぞれの講座の主題を簡単に説明すると以下のようになります。

 

1.Pythonの基礎について学ぶ

2.Pythonのデータ構造について

3.PythonでWebデータへアクセスする

4.データベース(!)について

5.以上の知識を用いて、Web上でデータを視覚化するアプリケーションを作る

 

このプロジェクトの良かった点としては、あくまで言語にフォーカスされているのは1,2番目の講座のみであり、その後は「Pythonが使って何が出来るのか?」というプログラミング初学者が最も気になるであろう点を、実戦形式でレクチャーしてくれることにあります。Python以外にもjavascript,json,SQLといった言語がカバーされておりPythonとこれら他言語や外部モジュールを組み合わせることによって、プログラミングが実用的なメリットを持ち合わせていることを正確に実感することが出来ました。この中でも、当時はjsonに対しては気味の悪い言語だなと思っていましたが、今では一番「知っててよかった」と思える言語の代表です。

 

次回は、3番目の講座で取り扱われているWebスクレイピングの技術について書く予定です。

*1:ちなみに、担当する講師はミシガン大学の教授でとてもユニークな方です。

エンジニアのためのキャリア形成指南書である、CAREER SKILLSを購入しました

CAREER SKILLSという書籍を買いました。 

CAREER SKILLS ソフトウェア開発者の完全キャリアガイド

CAREER SKILLS ソフトウェア開発者の完全キャリアガイド

 

 

まだ、エンジニアとしてキャリアを進めていくかは考え倦ねている状態なのですが、先日そのための取っ掛かりとなる機会を運良く得る事が出来たことから、エンジニアという特異なキャリアの中で、(日本と海外の市場は事情が異なる事を理解しつつも)本著をコンパスのように活用させていきたいと考えています。

 

もっとも最大の動機としては、前著であるSOFT SKILLSをよく図書館で何度も読み返しており、著者に非常に影響を受けたことが大きいです。この新書の存在については前から知っていたことから、翻訳が出ないものかと待ち望んでいたのですが、ふとしたきっかけで訳書が書店で並べられていたことを知り、久しぶりに衝動買いをしてしまったという経緯があります。

 

これからは、随時各章の内容について自身の現状と照らし合わせながら、考察をしていきたいと考えています。例えば、第3章「身につけないといけない技術スキル」では、エンジニアに求められる最低限のスキルセットが記述されています。

 

・金になるスキル

・ひとつのプログラミング言語

・コードの組み立て方

オブジェクト指向設計

アルゴリズムとデータ構造

・開発プラットフォームと関連テクノロジー

フレームワーク、またはスタック

・データベースの基本的な知識

・ソースコントロールシステム

・ビルドとデプロイ

・テスト

デバッグ

メソドロジー

 

これらについては、GoogleのTechnical Dev Guideで記載されていたエンジニアになるための必須スキル群とやはり共通するものが多く、本著で記載されていなかったのは「暗号化」「機械学習」「離散数学」などの知識でしょうか。これまでの経験で何とかカバー出来ているだろうと思えるのが、以下の3つぐらいしか思い当たらないため、ひどい焦燥感に駆られてしまいますが、愚直に一つずつ進めていくのが最善であると思います。

 

・ひとつのプログラミング言語

・開発プラットフォームと関連テクノロジー

・データベースの基本知識

 

加えて、現在絶賛格闘中であるのは以下の3つです。

 

オブジェクト指向設計

アルゴリズムとデータ構造

・コードの組み立て方

 

次回は、上記必要スキル群に対応するような学習計画、あるいは経験に基づくレビューを行う予定です。