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

tiling

문제

세로 길이 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 
------------
*/

Advanced

• 타일링 문제를 해결하는 효율적인 알고리즘(O(N))이 존재합니다. 반드시 직접 문제를 해결하시면서 입력의 크기에 따라 어떻게 달라지는지 혹은 어떻게 반복되는지 관찰하시기 바랍니다.

문제풀이

문제 자체가 무슨말인지 이해가 안되서 일단 찾아보고 시작했다. 사용한 언어는 다르지만 개념은 같아서 이해하는 용도로. (백준 11726번)

 

점화식을 사용해서 푼다고 하기에 점화식이 무슨말인가 간단히 알아봤다. 

점화식은 수열에서 이웃하는 항 사이의 관계를 나타내는 식으로, 이전 항들의 값들을 이용하여 다음 항의 값을 구할 수 있습니다.

이 문제에서도 피보나치 수열과 유사한 형태를 가지고 있으므로 점화식을 사용하여 값을 구할 수 있으니 살펴보자면, 여기서 n은 가로 크기를 의미하며 세로 크기가 2로 고정되어 있으므로 가로 크기 n인 공간에 박스를 넣는 경우의 수를 f(n)이라고 할 때, 다음과 같은 점화식이 성립한다.

• f(1) = 1
• f(2) = 2
• f(n) = f(n-1) + f(n-2) (n >= 3)  // n이 3 이상인 경우에만 f(n)을 구하기 위한 점화식을 제시, 3미만이면 f(1)과 f(2) 값으로 계산

이 점화식은, 가로 크기가 n인 공간에 박스를 넣는 경우의 수는 (n-1)번째 공간에 박스를 넣은 경우의 수와 (n-2)번째 공간에 박스를 넣은 경우의 수를 합한 것과 같다는 식이다.

점화식인 아래코드에서 사용되었으며 초기값으로 f(1)과 f(2)를 각각 1과 2로 설정하고, 반복문을 사용하여 f(3)부터 f(n) 값을 계산했다. 이때, f(i) = f(i-1) + f(i-2) 점화식을 이용하여 계산하고 f(n) 값을 반환하여 가로 크기가 n인 공간에 박스를 넣는 경우의 수를 구할 수 있다.

let a = 1; // 초기값 f(1)
let b = 2; // 초기값 f(2)
for (let i = 3; i <= n; i++) {
  let c = a + b; // f(i) = f(i-1) + f(i-2)
  a = b;
  b = c;
}
return b; // f(n) 반환

- for문을 사용한 방법

let tiling = function (n) {
  // 세로 2 가로길이가 n인 박스
  // 타일은 2x1 or 1x2

  // 가로 크기가 1인 경우, 1개의 상자만 넣을 수 있으므로 1을 반환
  if (n === 1) {
    return 1;
  }
  // 가로 크기가 2인 경우, 2개의 상자를 넣을 수 있는 경우의 수는 2이므로 2를 반환
  if (n === 2) {
    return 2;
  }
  // 가로 크기가 3 이상인 경우, f(n) = f(n-1) + f(n-2) 점화식을 이용하여 경우의 수를 계산
  // a와 b는 초기값으로 f(1)과 f(2)를 각각 1과 2로 설정
  let a = 1;
  let b = 2;
  // n이 3부터 n까지 반복문을 실행하면서, a와 b를 이용하여 f(n) 값을 계산
  for (let i = 3; i <= n; i++) {
    let c = a + b;
    a = b;
    b = c;
  }
  // f(n) 값을 반환
  return b;
}

// 가로 크기가 5일 때 박스를 넣을 수 있는 경우의 수를 출력
console.log(tiling(5)); // 8

 

이 코드의 시간 복잡도는 O(n)이다.  for문 안에서 n번의 반복을 하기 때문에, 시간 복잡도는 입력 크기 n에 비례하게 된다. 즉, n이 증가할수록 계산 시간도 증가한다. 따라서 이 코드는 입력 크기 n에 대해 선형 시간이 걸리는 알고리즘이라고 할 수 있다. 

선형 시간 알고리즘(Linear Time Algorithm)은 입력 크기에 비례하여 처리 시간이 증가하는 알고리즘.

예를 들어, 입력 크기가 n인 배열의 모든 요소를 한 번씩만 순회하는 알고리즘의 경우, 배열의 크기 n에 비례하여 처리 시간이 증가한다. 따라서 이러한 알고리즘을 선형 시간 알고리즘이라고 부른다.
선형 시간 알고리즘은 입력이 커질수록 처리 시간이 증가하지만, 입력 크기에 비례하는 계산 복잡도를 가지므로 일반적으로 효율적인 알고리즘이라고 할 수 있다.

- 재귀함수 사용한 방법

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

console.log(tiling(5)); // 8

하지만 문제의 크기가 n이라서, 재귀함수를 이용하여 문제를 해결할 경우 시간복잡도는 O(2^n)가 나오고 테스트를 통과하지 못했다.

재귀함수에서 가로 크기가 n인 경우를 계산할 때, 이전 단계에서 가로 크기가 n-1인 경우와 n-2인 경우를 모두 계산해야 하므로, 하나의 문제를 해결하기 위해 최대 2개의 하위 문제를 해결하는 방식으로 동작했다. 이 때문에 재귀 호출의 깊이는 최대 n까지 증가하며, 각 호출에서 2개의 하위 호출을 수행하므로 시간복잡도는 O(2^n)이 됐다.

반면에, for 루프를 이용한 방식은 문제를 한 번에 해결할 수 있기 때문에, 시간복잡도는 O(n)이고 따라서 대규모의 문제를 다루는 경우, 재귀함수를 이용하는 것보다 for 루프를 이용하는 것이 더욱 효율적인것 같다.

- 메모제이션을 사용한 방법

let tiling = function(n) {
  let memo = [0, 1, 2]; // 초기값으로 memo 배열을 선언하고, n = 1일 때와 n = 2일 때의 값을 미리 저장
  let aux = function(n) {
    if (memo[n] === undefined) { // memo[n] 값이 정의되어 있지 않으면, 계산을 실행
      memo[n] = aux(n-1) + aux(n-2); // memo[n] 값을 구하기 위해서 이전 두 값을 더하기
    }
    return memo[n]; // memo[n] 값을 반환
  };
  return aux(n); // aux 함수를 호출하고, 결과값 반환
};

// 가로 크기가 5일 때의 경우의 수 구하기
console.log(tiling(5)); // 8

메모이제이션은 계산된 값을 저장해두었다가 나중에 다시 사용하는 방법이니 동일한 입력값에 대한 함수 호출을 반복할 경우 중복된 계산을 피할 수 있다. 이를 이용하여 tiling 문제를 해결하기 위해서 이전에 계산한 값을 저장해두고 다시 사용하면 된다.

위 코드에서는 memo 배열을 생성하여, 이전에 계산한 값을 저장해둔다. aux 함수는 n에 대한 값을 구하는 함수이며, 만약 memo[n] 값이 undefined이면 aux(n-1)과 aux(n-2)의 값을 더한 후 memo[n]에 저장한다. 이렇게 저장한 값을 이후에 다시 사용할 수 있고 이전에 계산된 값은 다시 계산하지 않아도 되므로, 중복된 계산을 피할 수 있다.

메모이제이션을 이용한 풀이의 시간복잡도는 O(n)이다. memo 배열에 이미 계산된 값을 저장해둠으로써, 같은 문제를 한 번만 계산하면 되기 때문이다. 따라서 재귀함수를 이용한 방법보다 훨씬 효율적이고 이 코드도 테스르를 통과한다.

메모이제이션을 사용한 코드와 위에 있던 for문을 사용한 코드 모두 선형 시간 알고리즘이다.
하지만 메모이제이션을 사용한 코드의 경우, 이전에 계산된 값을 저장해두고 재활용함으로써 중복 계산을 방지하고 처리 시간을 절약할 수 있다. 따라서, 메모이제이션을 사용한 코드가 같은 입력에 대해 더 빠른 처리 시간을 보인다.
즉, 입력 크기가 커지면 커질수록 메모이제이션을 사용한 코드가 더 효율적인 알고리즘이라고 할 수 있을것 같다.

레퍼런스코드

// naive solution: O(2^N)
// 2 x 4 보드에 타일을 놓는 방법은 5가지다.
// 각 타일을 a, b, c, d로 구분한다.
// 아직 타일이 놓이지 않는 부분은 -로 표기한다.
// 타일을 놓는 방법은 가장 왼쪽부터 세로로 놓거나 가로로 놓는 것으로 시작한다.
// 1) 세로로 놓는 법
//   2 | a - - -
//   1 | a - - -
//   ------------
// 2) 가로로 놓는 법
// 타일을 가로로 놓게 되면, 그 바로 아래에는 가로로 놓을 수 밖에 없다.
//   2 | a a - -
//   1 | b b - -
//   ------------
// 이때, 타일이 아직 놓이지 않은 부분은 사실 크기만 다를뿐 같은 종류의 문제라는 것을 알 수 있다.
// 즉, 2 x 4 보드에 타일을 놓는 방법은 아래 두 가지 방법을 더한 결과와 같다.
//  1) 2 x 3 보드에 타일을 놓는 방법
//  2) 2 x 2 보드에 타일을 놓는 방법
// 따라서 2 x n 타일 문제는 아래와 같이 재귀적으로 정의할 수 있다.
// 주의: 재귀적 정의에는 항상 기초(base), 즉 더 이상 재귀적으로 정의할 수 없는(쪼갤 수 없는) 문제를 별도로 정의해야 한다.
// let tiling = function (n) {
//   if (n <= 2) return n;
//   return tiling(n - 1) + tiling(n - 2);
// };

// dynamic with 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);
};

// dynamic with tabulation: O(N)
// 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: O(N)
// 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;
// };