[JS] tiling

문제

세로 길이 2, 가로 길이 n인 2 x n 보드가 있습니다. 2 x 1 크기의 타일을 가지고 이 보드를 채우는 모든 경우의 수를 리턴해야 합니다.

입력

인자1: n

• Number타입의 1 이상의 자연수

출력

• number 타입을 리턴해야 합니다.

주의사항

• 타일을 가로, 세로 어느 방향으로 놓아도 상관없습니다. (입출력 예시 참고)

수도코드

타일을 놓는 법은 세로와 가로가 있다.
2 x n 보드에서 타일은 n개가 들어간다.
타일을 왼쪽부터 놓는 다 하에 타일을 가로로 놓게 되면 바로 아래는 가로로 놓을 수 밖에 없다.
타일이 아직 놓이지 않은 부분은 크기만 다를뿐 같은 종류의 문제이다.
즉, 타일 놓는 법 2 x 4의 경우의 수는 2 x 2와 2 x 3의 경우의 수의 합이다.

재귀적으로 구현해 보면 다음과 같다.

let tiling = function (n) {
  if (n <= 2) return n;
  return tiling(n - 2) + tiling(n - 1);
};

하지만 테스트 실행 시간을 초과했다.

시간복잡도를 효율적으로 관리할수있는 알고리즘들이 있다.

'0(N)' 알고리즘 (시간복잡도)

dynamic with memoization

let tiling = function (n) {
  // 인덱스를 직관적으로 관리하기 위해
  // 앞 부분을 의미없는 데이터(dummy)로 채운다.
  const memo = [0, 1, 2];

  // 재귀를 위한 보조 함수(auxiliary function)을 선언)
  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);
};

dynamic with tabulation

tabulation은 데이터를 테이블에 정리하면서 bottom-up 방식으로 해결하는 기법을 말한다.

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

dynamic with slicing window

slicing window은 필요한 최소한의 데이터만을 활용하는 것을 말한다.
크기 n의 문제에 대한 해결을 위해 필요한 데이터는 오직 2개뿐이라는 사실을 이용한다.

 let tiling = function (n) {
   let fst = 1,
     snd = 2;
   if (n <= 2) return n;
   for (let size = 3; size <= n; size++) {
     // 앞의 두 수를 더해 다음 수를 구할 수 있다.
     const next = fst + snd;
     // 다음 문제로 넘어가기 위해 필요한 2개의 데이터의 순서를 정리한다.
     fst = snd;
     snd = next;
   }
   return snd;
};