[알고리즘] 2 x n 보드 타일링과 피보나치 수열

문제:
세로 길이 2, 가로 길이 n인 2 x n 보드가 있다. 2 x 1 크기의 타일을 가지고 이 보드를 채우는 모든 경우의 수를 리턴하시오.

입력: number 타입의 1 이상의 자연수
출력: number 타입

주의사항: 타일을 가로, 세로 어느 방향으로 놓아도 상관없다.

---

위의 타일링 문제를 작게 쪼개 보면 다음 그림과 같이 왼쪽 첫 시작을 세로로 타일 한 장을 놓을지, 가로로 타일 두 장을 놓을지에 따라 두 가지의 경우 밖에 나오지 않는다. 전자의 경우 그 다음은 가로가 n-1인 보드를 채우는 경우의 수가 되고, 후자의 경우 그 다음은 가로가 n-2인 보드를 채우는 경우의 수가 된다. 따라서 가로 길이가 n인 보드를 채우는 모든 경우의 수는 가로 길이가 n-1인 경우의 수와 가로 길이가 n-2인 경우의 수를 더한 경우의 수가 된다.

💡 F(n) = F(n-1) + F(n-2)

어디서 많이 본 식이지 않은가?
그렇다, tiling 문제는 피보나치 수열과 동일한 문제이다. 따라서 똑같은 재귀 함수로 문제를 풀 수 있다. 타일링 문제와 피보나치 수열 문제의 단 하나의 차이점이 있다면 초기값 세팅을 어디까지 해주느냐이다.

먼저 타일링 문제의 재귀 함수 솔루션은 다음과 같다.
가로 길이가 1일 때는 한 가지 경우의 수 밖에 없고, 가로 길이가 2일 때는 타일 2개를 둘 다 가로로 놓든지, 세로로 놓든지 하는 두 가지 경우의 수가 있기 때문에 인자로 1이나 2이 들어올 때는 그 자신을 리턴해 주면 된다.

const tiling = function(n) {
  // base case
  if (n <= 2) return n;
  
  return tiling(n - 1) + tiling(n - 2);
}

피보나치 수열의 재귀 함수 코드는 다음과 같다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 2이기 때문에 base case에서 위와 차이가 있다.

const fibonacci = function(n) {
	// base case
	if (n <= 1) return n
    
    return fibonacci(n - 1) + fibonacci(n - 2)
}

여기까지만 해도 문제는 풀리지만 시간 복잡도를 생각하면 위의 재귀함수 코드는 O(2^N)이기 때문에 최적화를 해주는 몇 가지 방법을 더 생각해 볼 수 있다. 피보나치 수열을 예로 들어보겠다.


1. Memoization - O(N)
- 초반 탈출 코드를 memo에 저장하거나 return 값을 직접 지정해준다.
- 보조함수(helper 함수)를 선언해서 재귀를 호출하고,
- 이미 해결한 문제는 풀지 않는다.
+) 이 방식은 잘 살펴보면 클로저(Closure) 패턴이다.

const fibonacci = function (n) {
  // 이미 해결한 문제의 정답을 따로 기록해 둘 배열을 선언한다.
  const memo = [];

  const helper = (n) => {
    // base case
    if (n <= 1) return n;

    // 이미 해결한 적이 있는 문제면 메모해둔 정답을 리턴한다.
    if (memo[n] !== undefined) return memo[n];

    // 새롭게 풀어야 하는 경우, 문제를 풀고 메모해둔다.
    memo[n] = helper(n - 1) + helper(n - 2);
    return memo[n];
  };

  return helper(n);
};

다음의 두 가지 풀이 방식은 재귀 함수를 쓰지 않고 for loop를 돌려서 해결한다.

2. Slicing window - O(N)
- 필요한 최소한의 데이터만을 활용한다.
- 피보나치 수를 구하기 위해 필요한 데이터는 그 앞의 수(n-1)와 그 앞의 앞의 수(n-2) 2개 뿐이라는 사실을 이용한다.

const fibonacci = function (n) {
  let first = 0,
    second = 1;

  if (n <= 1) return n;

  for (let i = 2; i <= n; i++) {
    // 앞의 두 수를 더해 그 다음 수를 구할 수 있다.
    const next = first + second;

    // 다음 문제로 넘어가기 위해 필요한 2개의 데이터의 순서를 정리한다.
    first = second;
    second = next;
  }

  return second;
};

3. tabulation - O(N)
- 데이터를 테이블(여기서는 배열)에 정리하면서 bottom-up 방식으로 해결한다.

const fibonacci = function (num) {
  let memo = [0, 1];
  if (num <= 1) return memo[num];

  // memo 배열에 memo[n] = memo[n-1] + memo [n-2] 를 넣어준다.
  for (let n = 2; n <= num; n++) {
    memo[n] = memo[n - 1] + memo[n - 2];
  }

  return memo[num];
};