[JavaScript,JS]二分検索,決定アルゴリズム解題,概念整理

📋 背景を書く

最近JavaScriptでコーディングテストを勉強しています.アルゴリズムといっても、気まずい問題も解決していて、今は少し神秘的な問題を解決し理解しようと努力しているようです.問題は二分探索による決定アルゴリズムである.質問の名前は「MV」ですが、グーグルゲームをしているときは有名な質問のようです.この問題を基礎教程から抜粋し、学習の目的でブログに整理するつもりです.

📝 質問の概要

決定アルゴリズムを紹介し,まず問題を確認し,アルゴリズムで解決策を紹介する.
問題は以下の通りです.
質問する
DVDにはN曲があり、DVDに収録する際は現場の順番を維持します.つまり、1番と5番の曲を同じDVDに録画するためには、1番と5番の曲の間のすべての曲を同じDVDに録画しなければならない.また、1曲を割って2枚のDVDに録画することはできません.このときDVDの大きさ(録画可能な長さ)は最小にします.また、M個のDVDはいずれも同じ大きさでなければならず、製造コストが低いため、必ず同じ大きさでなければならない.
入力例
3, [1, 2, 3, 4, 5, 6, 7, 8, 9]
出力例
17
簡単にまとめると、共有するDVDの個数はMで、1曲あたりの長さは順番です.例えば、1分から9分まで、9曲の順に3枚のDVDで録音する.このDVDの長さは最小容量に指定した方が良いので、クリップではなく3枚のDVDに効率よく9曲を入れます.

📝 どうやって解読しますか?

まず問題を解決するために、私たちが得たい値の範囲を指定する必要があります.決定アルゴリズムはこうです.DVDの最小長さは9、最大長さは45です.(1つの場合とすべての場合のみを含む.値の範囲は9<=X<=45である.ここでは、2分探索により、所望の条件に対応する値の中で最小値を探す.)
この探索には中間値を定め,引き続き割る場合を創造する必要がある.したがって、値の範囲を変数として指定し、範囲を縮小するアクティビティを行うために適切な変数を作成する必要があります.次に、中間の対応する値を使用して有効かどうかをテストします.

📝 ソリューションコード

概念の理解と整理を目的とした位置づけなので、コードや説明が友好的でなくても理解してほしい.問題解決コードを紹介します.

const count = (arr, capacity) => { // DVD개수를 세어주는 함수
  let cnt = 1; // dvd 한장 있음
  let hap = 0;

  for (let x of arr) {
    if (hap + x > capacity) {
      cnt++;
      hap = x;
    } else hap += x;
  }

  return cnt;
};

const solution = (m, arr) => {
  let answer = 0;

  let lt = Math.max(...arr);
  let rt = arr.reduce((a, b) => a + b);

  while (lt <= rt) {
    let mid = parseInt((lt + rt) / 2);
    if (count(arr, mid) <= m) {
      answer = mid;
      rt = mid - 1;
    } else lt = mid + 1;
  }

  return answer;
};

console.log(solution(3, [1, 2, 3, 4, 5, 6, 7, 8, 9])); // output: 17

コードを簡単に説明しながらまとめを終了します.
まず、テスト変数をsolution関数に渡し、resultは正しい答えを返す値です.まず値の範囲を指定しなければならないのでltとrtの変数値を指定します.
次にwhileゲートを回し、rt比ltが前またはlt比rtより後ろの瞬間を条件とする.これですべての探索が終わったことを意味するからだ.
次に、その範囲の中間値midを設定します.これは,この探索が中間点から切り込んで探索されるため,非常に効率的である.次にarrとmidをcount関数に送信します.count関数は,中間の値をDVD長がどれだけarrを切断できるかを検証する関数と見なすことができる.arr配列の歌をhapという変数に追加し、長さを真ん中に埋め、midより大きい値でcntを増加させ、hapを瞬間xの値に初期化します.if,elseでこの方式を表現した.1曲からDVDの数がカウントされているので、cntを1にします.count関数から得られた戻り値が所定のmの値(ビューでは3)以下である場合、この値は有効です.この言葉はとても重要です.有効以下3つ切らせてもらいますが、1つか2つ切ることができます.これは長さが十分であることを示しています.DVDの長さは十分な長さなので、無条件で有効です.では,より効率的な長さを探すために,最大値rtをmid−1に減らし,再検査を行うことができる.
そうでなければ,与えられたmid長で有効性検査を行った場合,割れが多すぎると,長さが短く,増やせばよいことを示す.mid+1でlt値を変更すればよい.このプロセスを続けると、17の値が得られます.
解決が複雑で何度も実行されているように見えますが、二等方式で探索するので、すべての状況を確認するよりも効率的です.

📝 整理...

コーディングテストの準備をするために、レッスンを受けながら一日にいくつかの問題を決めて、ずっと努力して解答して、やっと少し分かりにくい内容が出てきて、整理しています.後の問題は厩舎も片付けようとしたが、眠くて大変だった.