計算量を最適化して問題を解く必要がありますか?

Written by Recursion
11月 7, 2021

中級者向け:

※以下の内容は、中級コースが修了済みのユーザーが対象となります。

1回目の提出の際は、時間計算量、空間計算量を考慮せず、Brute-force(総当たり)で解いてみることをおすすめします。それはBrute-forceで解く場合と最適化して解く場合で難易度が全く異なるからです。

まずは自分のチカラだけで解いてみよう

Recursionでは「Think For YourSelf」という方針を大切にしています。自分で考えて独自のソリューションが開発できるようになるためにも、まずは頑張って自分のチカラで解いてみましょう。

それでは有名なTwo Sumという問題をBrute-forceで解いた場合と、最適化して解く場合を例として考えてみましょう。

ID258 足して合計値
整数で構成される配列intArrとターゲットsumが与えられるので、配列内の2つの数字を足し合わせてtargetに一致するペアのインデックスを出力してください。

この問題をBrute-forceで解くことはとても簡単です。以下のように2つのfor文を入れ子で使い、それぞれの要素と残りの要素の合計がtargetに一致するかどうか全通りチェックすれば問題ありません。


function twoSum(intArr,sumInt){
    for (let i = 0; i < intArr.length; i++) {
        for (let j = i+1; j < intArr.length; j++) {
            if (intArr[i] + intArr[j] == sumInt) return [i,j];
        }
    }
    return [];
}

しかし、この問題を計算量を意識して解くとなれば、難易度はかなり上がります。配列の検索はO(n)なので、ルックアップの計算量が少ないハッシュマップを使って、インデックスと値の情報を保存します。その後、for文を使ってペアがハッシュマップ内に存在するかチェックしていきます。


function twoSum(intArr,sumInt){
    let hashmap = [];

    for (let i = 0; i < intArr.length; i++) {
        const curr = intArr[i];
        if(!(curr in hashmap)) hashmap[curr] = i;
    }

    for (let i = 0; i < intArr.length; i++) {
        const diff = sumInt - intArr[i];
        if (diff in hashmap && hashmap[diff] != i) {
            const j = hashmap[diff];
            return j > i ? [i, j] : [j, i];
        }
    }

    return [];
}

このようにコードは少し煩雑になり、問題としての難易度は上がりますが、計算量は大幅に削減することができます。コードの計算量を削減するにはアルゴリズムやデータ構造の知識が必要になります。

高い目標を持つ方にはおすすめ

Brute-Forceで解く場合と最適化して解く場合は難易度が大幅に異なるため、コーディング面接ではアルゴリズムやデータ構造の知識が必要になることがあります。特に将来レベルの高い開発者や、有名企業でソフトウェアエンジニアとして勤務したい場合は計算量を意識して問題を解いてみましょう。Recursionの模範解答を上手く活用して学習を進めても良いかもしれません。

Note:
何気なく使っているメソッドの計算量を調べてみるのもおすすめです。例えば、文字列から特定の文字のインデックスを検索するindexOf()メソッドの時間計算量はO(n)で、配列をソートするsort()メソッドの時間計算量はO(nlogn)です。これらの計算量をリサーチし、計算量を意識して問題を解くことで新たに発見があるはずです。
関連記事
  • 問題をスキップしても進捗に影響は与えますか?
  • 問題に合格した後、どうすれば良いですか?
  • 問題がどうしても解けないです。どうすれば良いですか?
  • メソッドや関数は暗記する必要はありますか?
Leave A Comment コメントをキャンセル

CAPTCHA


email confirm*

post date*

日本語が含まれない投稿は無視されますのでご注意ください。(スパム対策)

カテゴリー
  • コンテンツ 0
    • 一般 7
    • 機能 7
    • 学習方法 4
  • コーディング問題 0
    • 一般 5
    • 問題を解く 5
    • エディタ 8
    • テストケース 5
    • テスト & 提出 4
    • 解説 3
  • コミュニティ 0
    • 一般 2
    • 機能 1
  • アカウント設定 0
    • 一般 5
    • カスタマイズ 3
    • 退会 2
  • 請求書 0
    • 一般 2
    • お支払い 6
  • その他 3
よく読まれている記事
  • 学習ロードマップの使い方
  • 学習期間はどれくらいですか?
  • 初級の2周目をJavaでするべきか、中級に進むべきでしょうか?
  • コミュニティはどうやって入ることができますか?
  • 問題の解答解説はどうやって見ることができますか?
  • プロモコードの使い方を教えてください
  • コース内のエディタはどうやって学習するのがおすすめですか?
  • 中学校の数学の知識しかありませんが、ついていけると思いますか?
  • 解答解説はどのように勉強するべきですか?
  • コードの貼り付け方がわかりません
問題を解く
  • 計算量を最適化して問題を解く必要がありますか?
  • 問題をスキップしても進捗に影響は与えますか?
  • 問題に合格した後、どうすれば良いですか?
  • 問題がどうしても解けないです。どうすれば良いですか?
  • メソッドや関数は暗記する必要はありますか?
  • Recursion
  • 公式ブログ
  • © 2022 Recursion, Inc All Rights Reserved.

よく検索されるワード:コミュニティ, 解答, プロジェクト