0. はじめに 気軽な気持ちでプログラムを書いたら計算量オーダーが $O(n^2)$ になってしまって処理がメチャクチャ遅い、というのは大変あるあるです (この記事など)。そういった状況を打破するために、古来から $O(n^2)$ なアルゴリズムを $O(n)$ や $O(n\log{n})$ に改良するテクニックは無数に考案されて来ました。逆に本来なら $O(n)$ で終わるはずの処理を雑に実装したために $O(n^2)$ になってしまうトラップも無数に知られています。その辺りの話は以下に特集してみました: 特集！知らないと損をする計算量の話 今回は $O(n^2)$ を $O(n)$ にするテクニックの 1 つであるしゃくとり法について、個人的に思うことを書いて行きます。またしゃくとり法を用いる以下の問題たちを紹介します: AOJ Course The Number of Window
2014年12月3日より2015年1月7日まで開催した、paizaオンラインハッカソンVol.4Lite「エンジニアでも恋したい」は、トータルで3問有りましたが全て解けましたでしょうか？ 各問題の成否によりストーリーが変わるのであえて間違えて解いた方もいらっしゃると思いますがｗ (プレゼント対象期間は終了しましたが、問題チャレンジは可能なので、未チャレンジの方は是非チャレンジください！) 問題１、問題２は解説するほどのむずかしさでもないので省きますが、問題３は多少工夫が必要なので、問題３について今回もPOH恒例の「図解解説」をしてみたいと思います。既に解けた方もそうでない方も、今回の解説を読んで、それぞれの方法すべてを実装してみると勉強になると思いますので、是非試してみてください。 ■どのような高速化ステップがあるのか？ 今回の問題ですが、解法の大きなパターンとしては、１．全てのパターンを
「効率的なアルゴリズムを実装しよう」第2弾は、配列や文字列を効率的に走査するテクニックです。 今回も、2重ループO(n^2)をなくす方法です。 配列内や文字列の、組み合わせを比較する時に威力を発揮します。 早速ですが、問題を見てみましょう。 配列の要素数の組み合わせが「0」となる関数を作成せよ。なお、要素数はinteger型でありソートされたものとする。//実行結果 sumZero([-3,-2,-1,0,1,2,3]) //[-3,3] sumZero([-2,0,1,3]) //undefined sumZero([1,2,3]) //undefinedつまり、配列内の要素数に「0」になる組み合わせがあるか、探せばいいわけです。 ナイーブな解法 O(n^2)function sumZero(array) { for (let i = 0; i < array.length; i++)
PythonでGoogleスプレッドシートを編集してみました。 #環境 Python 3.5.2 pip 10.0.1 gspread 3.0.0 → https://github.com/burnash/gspread oauth2client 4.1.2 #サービスアカウントキー取得 Googleスプレッドシートにアクセスするためのサービスアカウントキー(JSONファイル)を取得します。 ##プロジェクト作成 こちらからプロジェクトを作成します。 https://console.developers.google.com/cloud-resource-manager プロジェクト名を適当に入力します。今回は「gspread-sample」としました。 ##Google Drive APIを有効 ライブラリからAPIを検索します。 「drive」と入力すると「Google Drive A
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
