[JS]_daily coding #26

seul_·2022년 6월 29일
0

Algorithm

목록 보기
25/31

코플릿 데일리 코딩 05_tiling

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

입력: number 타입의 1 이상의 자연수
출력: number 타입을 리턴해야 합니다.


문제 파악하기

일단 문제를 이해하는데도 한참 걸렸다. 문제에 있는 입출력 예시는 입력으로 4가 주어지면,
2 X 4 보드에 타일을 놓는 방법이 아래의 5가지이므로 5가 출력된다.

패턴을 살펴보면 1,2,3의 경우는 맨 앞에 세로로 놓인 타일 1개를 제외하면 2 X 3보드에 타일을 놓는 패턴과 일치하고,

4,5의 경우는 맨 앞에 가로로 놓인 타일 2개를 제외하면 2 X 2보드에 타일을 놓는 패턴과 같다.

즉, 2 x 4 보드에 타일을 놓는 방법은 2 x 3 보드에 타일을 놓는 방법과 2 x 2 보드에 타일을 놓는 방법을 더한 결과와 같다는 것을 알 수 있다.

마찬가지로, 2 x 5 보드에 타일을 놓는 패턴도 살펴보면 2 x 4 보드에 타일을 놓는 방법과 2 x 3 보드에 타일을 놓는 방법을 더한 결과와 같다.

첫번째 접근

따라서, 피보나치 수열 문제와 같아서 재귀함수로 구할 수 있다. 이렇게 하면 예시처럼 작은 수의 입력은 정상적으로 출력할 수 있다.

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

다만 피보나치 수열 문제를 풀 때처럼 동일한 연산이 중복해서 실행되는 경우를 고려해서 풀어야지 크기가 큰 입력이 주어졌을때 효율적으로 해결할 수 있다.

두번째 접근

연산 결과를 배열에 기록하고 이미 해결한 문제는 풀지 않는 보조 함수를 만들어서 해결하는 방법을 사용해서 해결할 수 있다. (재귀 + 메모지에이션)

let tiling = function (n) {
  
  const memo = [0,1,2]; 
  const aux = (size) =>{
    // 이미 해결한 적이 있으면, 메모해둔 정답을 리턴한다.
    if (memo[size] !== undefined) return memo[size];
    // 새롭게 풀어야하는 경우, 문제를 풀고 메모해둔다.
    memo[size] = aux(size -1) + aux(size -2);
    return memo[size];
  }
  return aux(n)
};

세번째 접근

재귀 함수를 따로 만들어주는 것이 아니라 결과를 저장해두고 결과를 리턴하는 방식으로 해결할 수도 있다.

let tiling = function (n) {
  if (n <= 1) return n
  return tiling(n-1) + tiling(n-2)
  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 방식도 나와있었는데 이해하지 못했다. 주말에 더 공부해보기!
profile
Connecting dots

0개의 댓글