문제 : tiling

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

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))이 존재합니다. 반드시 직접 문제를 해결하시면서 입력의 크기에 따라 어떻게 달라지는지 혹은 어떻게 반복되는지 관찰하시기 바랍니다.

문제의 접근

처음 이 문제를 보는 순간 든 생각은 '흥미롭다' 였다. 과연 어떤 방법으로 풀 수 있을까? 물론 경우의 수를 찾는 거니깐 DP(Dynamic Programming : 동적할당) 하지만 이렇게 생각한다면 그냥 단순하게 수학 공식을 외우는 것과 다름 없다. +솔직히 DP로 코드를 짤 자신이 없다...

그렇기 때문에 일단 천 리 길도 한 걸음부터 손으로 직접 하나하나 씩 끄적여 보았다. 생각보다 만만치 않았다... 그래도 6번째 까지 해보니 어떠한 규칙을 찾을 수 있었다.

3번 째 이후 부터는 피보나치 수열을 이룬다.

물론 6번까지만 해봐서 확신은 할 수 없었지만 그래도 이 규칙이 만약 맞다면 코드는 정상적으로 작동 할 것이라 생각되어 일단 코드를 작성 해보았다.

let tiling = function (n, m=[]) {
  // TODO: 여기에 코드를 작성합니다.
  let result = 0;
  if(m[n] !== undefined){
    return m[n] 
  }
  if(n<=3){
    return n
  }
  result = tiling(n-1,m) + tiling(n-2,m)
  m[n] = result;
  
  return result;
};

결과는 예상치 못하게 통과 했다... 뭔가 찝찝하다. 과연 이렇게 푸는게 맞나 싶다...😭

Advanced

처음에 그냥 피보나치를 실행했지만, 역시나 실행시간 초과로 나왔다. 그래서 다시 하향식의 방식을 이용해서 구현하니 효율적인 알고리즘이 되었다.

문제를 통해 생각해 볼 것

모로 가도 서울만 가면 된다

이 말을 한번 곱씹게 된다. 물론 테스트는 모두 통과했지만 과연 이 접근 방법이 맞는가 생각이 든다. 물론 나름 열심히 생각해서 도출한 결과이기에 풀었을 때, 기분은 좋았다. 하지만 그래도 이게 맞는 걸까 하는 불안감이 엄습해온다...😭