TOY05.tiling

質問する
2 x n板、長さ2、長さn.2 x 1サイズのタイルを使用してこの板を充填する場合は、数を返さなければなりません.
入力
パラメータ1:n

型1以上の自然水

しゅつりょく
は、

の番号タイプ

を返します.
注意事項

タイルは、横方向および縦方向に配置することができる.(I/O例参照)

I/O例

let output = tiling(2);
console.log(output); // --> 2

output = tiling(4);
console.log(output); // --> 5
/* 
2 x 4 보드에 타일을 놓는 방법은 5가지
각 타일을 a, b, c, d로 구분

2 | a b c d
1 | a b c d 
------------

2 | a a c c
1 | b b d d 
------------

2 | a b c c
1 | a b d d 
------------

2 | a a c d
1 | b b c d 
------------

2 | a b b d
1 | a c c d 
------------
*/

私が解読したコード

let tiling = function (n) {
  // TODO: 여기에 코드를 작성합니다.
  /**
   * n개 있다고 생각하자.
   * n 을 1 과 2 를 빼면서 0으로 만들 수 있는 경우의 수를 생각하면 된다.
   * 만약 n 이 1 => 1
   * n 이 2 라면 (1, 1)
   * n 이 3 이라면 (1, 2), 
   *             (2, 1)
   * n 이 4 라면 (1, 1, 1, 1), (1, 1, 2), (1, 2, 1),
   *            (2, 1, 1), (2, 2)
   * 규칙을 생각해본다.
   * 재귀를 이용하면 될 듯 하다.
   * 처음 숫자가 1인 경우와 2인 경우로 나눠서 재귀 호출 
   * 탈출 조건은 n === 0
   * 
   */
  let count = 0;
  
  function recursion(n) {
    if (n === 0) {
      count++;
      return; //탈출 조건 
    }
    for (let i = 1; i <= 2; i++) {
      if (n - i >= 0) {
        recursion(n - i);
      }

    }
    return;
  }
  recursion(n);
  return count;
};

問題を見て考えたのは,1と2を用いて与えられたnを0にするたびにcountという変数が1を増やし,再帰呼び出しが可能になるということである.実際に実行しましたが、時間的複雑度がO(2^n)のため、テストには合格しませんでした.(時間の複雑さの概念はまだ…)
リファレンスコード

let tiling = function (n) {
  const memo = [0, 1, 2];
  
  const aux = (size) => {
    if (memo[size] !== undefined) return memo[size];
    if (size <= 2) return memo[n];
    memo[size] = aux(size - 1) + aux(size - 2);
    return memo[size];
  };
  return aux(n);
}

参考コードの解釈を見て感嘆した.

2 x 4タイル仮定

タイルを配置する方法は、左から右または水平に配置します.
1)縦置き
2 | a - - -
1 | a - - -
2)横置き
タイルは横に、真下のタイルは横に
2 | a a - -
1 | b b - -

から2×4タイルを充填する方法は2×3タイル+2×2タイルであることがわかる.

すなわち,復元を利用して問題を解決することができる.思いついた方法も繰り返すことができましたが、こんなに近いとは思いませんでした.
また,memorizationを用いて計算した値は再計算されないため,より効率的なコードとなる.
学識
符号化テストではmemoizationを利用するという問題がよくあるそうです.まず,memoizationを用いてより効率的なコードを記述する.