TOY05.tiling

Judo·2020년 12월 17일

알고리즘

문제

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

입력

인자 1 : n

number 타입의 1 이상의 자연수

출력

number 타입을 리턴

주의사항

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

입출력 예시

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

문제를 보면서 든 생각은 주어진 n을 1 과 2를 이용해 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 x 4 타일을 채우는 방법은 2 x 3 타일 + 2 x 2 타일 인 걸 알아낼 수 있다.

즉, 재귀를 이용해 풀면 된다. 내가 생각한 방법도 재귀지만 이런 접근은 생각 못 했다.
또한 memoization을 이용해 계산한 값은 다시 계산하지 않게 해줌으로써 좀 더 효율적인 코드가 되었다.