[22.11.02] Daily Coding 25

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

내가 쓴 답

let tiling = function (n) {
  // 2 x 4 보드에 타일을 놓는 경우 
  // 1) 처음에 세로로 하나 놓는 경우 : 2 x 1 + 2 x 3
  // 2) 가로로 놓는 경우 (밑에도 가로로 놓게 됨) : 2 x 2 + 2 x 2
  // => 즉 n=4 일 때 경우의 수 : n = 2, 3 일 때를 더한 것 (재귀)
  
  let arr = [0,1,2];

  const boxTiling = (n) => {
    if(arr[n]) return arr[n];
    return arr[n] = boxTiling(n-1) + boxTiling(n-2);
  } 

  return boxTiling(n);
};

레퍼런스 📌

DP(Dynamic Programming)

💫 memoization

• 주어진 입력값에 대한 결과를 저장함으로써 같은 입력값에 대해 함수가 한 번만 실행되는 것을 보장한다(보통 딕셔너리에 저장한다). 즉 주어진 값이 있다면 그걸 꺼내 쓰지 다시 반복해서 실행하지 않는 방법!
• top-down approach (하향식)
• memoization을 이용한 재귀함수 방법은 O(N)의 시간복잡도를 나타낸다.

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);
};

💫 tabulation

• 어떤 값을 구하기 위해 순서대로값을 구해 나감으로써 중복된 계산을 하지 않고 다음값을 빠르게 구해나가는 방법
• 테이블을 그려놓고 하나씩 진행하며 저장하는 방식이다. 제일 최소의 단위부터 문제의 값을 테이블에 저장해 나가며, 제시된 문제를 해결할 수 있으면 거기서 해당 값을 리턴
• bottom-up approach (상향식)

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];
};

💫 slicing window

• 필요한 최소한의 데이터만을 활용하는 것을 말합니다.
• 이 문제에서는 , 크기 n에 대한 문제를 해결하기 위해서 최소 필요한 데이터가 2개 라는 것을 기억한다.
• 같이 일정한 범위를 가지는 것을 유지한 채 이동하며 계산되는 방법, 최소한의 데이터만을 활용하는 방법 (가장 작은 경우의 수부터 하나씩 이동하는 느낌으로 계산된 값을 누적해나가는 방법?)
• fst,snd 두 개의 변수를 정해줌으로써 한 칸씩 이동해나가며 fst에 snd를 할당, 두 변수의 합을 snd에 할당함으로써 n까지 합을 누적해가며 값을 구하는 방법이다.

  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;
     fst = snd;
     snd = next;
  }
   return snd;
 };