코플릿 데일리 코딩 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 방식도 나와있었는데 이해하지 못했다. 주말에 더 공부해보기!
