[JavaScript] Tiling문제와 재귀, 그리고 최적화(?) 기법(memoization, tabulation, slicing window)

문제

세로 길이 2, 가로 길이 n인 2 x n 보드가 있을 때, 2 x 1 크기의 타일을 가지고 이 보드를 채우는 모든 경우의 수를 리턴하는 함수를 작성하시오. 단, 인자는 n 하나이다. 그리고 타일을 채우는 방향은 상관이 없다(가로, 세로 상관없음).

로직

이 문제는 발표 순서와 마찬가지로 경우의 수 문제이다.
경우의 수 문제를 풀 때 좋은 방법은 일단 직접 손으로 경우의 수를 계산하면서 규칙성을 찾아나가는 것이다. 따라서 가로길이가 4까지의 경우를 정리해보았다.
n이 1일 때, 오직 하나의 경우의 수만 가능하다.(|)
n이 2일 때, 두가지 경우의 수가 가능하다.(| | , 二)
n이 3일 때, 세 가지 경우의 수가 가능하다.(| | | , | 二 , 二 |)
n이 4일 때, 다섯 가지 경우의 수가 가능하다. (| | | | , | | 二 , | 二 | , 二 二, | | 二)

여기서 주목해야 될 것은 n이 3일 때부터이다.
n = 3인 경우 안에 n=2인 경우의 모양이 분리해보면 포함되어있다는 것을 알 수 있다.
(n=3인 경우의 첫 번째와 두 번째 경우에서 맨 왼쪽의 |를 빼고 생각하면 된다) 그리고 동시에 n=1인 경우 |가 포함되어있다.
이것은 n = 4인 경우도 모양의 규칙성을 보면 n = 2인 경우와 n = 3인 경우가 포함되어있다는 것을 알 수 있다.
이렇게 되는 이유는 세로의 길이는 고정된 상태로 가로의 길이가 늘어났기 때문에 쪼개면 결국 닮음 형태의 직사각형이 되기 때문이다.
닮은 꼴의 경우에는 재귀를 쓰면 문제 해결이 간단해진다.
특히 재귀 중에서 피보나치 수열과 매우 유사하다.

Naive Solution: O(2^N)

가장 만만하게 짤 수 있는 코드는 다음과 같다.
재귀를 한 함수식에 두 번 쓰는 것이다.

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

하지만 이렇게 코드를 짜게 되면 시간복잡도가 지수함수꼴이 되기 때문에 N이 커지면 실행 시간이 기하급수적으로 늘어날 것이다.
따라서 최적화 기법을 쓰면 시간복잡도를 비약적으로 줄일 수 있다.

Memoiztion: O(N)

최적화 기법 중에서 가장 먼저 알아볼 것은 Memoization(메모이제이션)이다. 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);
  };

최적화 기법의 가장 큰 특징은 자기 자신의 함수를 리턴하는데, 리턴하는 함수는 오직 하나라는 점이다.
위에도 리턴하는 보조함수 aux 하나만 리턴하는 것을 알 수 있다.
보조함수 aux를 살펴보면, memo라는 함수블록 스코프 내의 변수를 이용하는 것이 특징이다.
우선 memo에는 인덱스별로 base case에 해당되는 값을 적는다.
n = 0이면 아예 경우의 수가 없기 때문에 0을 적어준다.
그 다음에 원래 있던 Naive Solution과 비슷하게 적기는 하는데, memo[size]를 보조함수의 더한 값으로 지정을 해주고, memo[size]를 리턴한다.
이 함수의 특징은 memo가 변수로 저장되어있기 때문에 한번 저장된 값은 다시 계산하지 않는다는 것이다.
위의 Naive Solution에서는 함수의 값을 일일이 불러와야 되는 것과는 대조적이다.(과정을 자세히 보고싶으면 Debugger;를 이용하면 됨)

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

태뷸레이션 방법의 특징은 반복문이다.
즉, 재귀를 사용하지 않는 것이다!
base case를 메모에 저장하는 것까지는 같다.
그 다음에는 재귀가 아니라 for문을 써서 recursive case를 해결하는 것이다.
어쩌면 재귀를 배우기 전에 문제를 해결한다면 이 방법이 가장 직관적일 것이다.
그리고 반복문을 한 번만 사용하기 때문에 시간복잡도가 O(2^N)에서 O(N)으로 비약적으로 줄어든 것을 볼 수 있다.

Slicing window: O(N)

slicing window란 필요한 최소한의 데이터만을 활용하는 것이다.
사실 이 방법은 앞서 재귀를 이용한 피보나치수열에서 꼬리재귀와 아주 유사하다.
코드를 보고 꼬리재귀와 비교해보길 바란다.

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