🖍 문제 1
문제 설명
세로 길이 2, 가로 길이 n인 2 x n 보드가 있습니다. 2 x 1 크기의 타일을 가지고 이 보드를 채우는 모든 경우의 수를 리턴해야 합니다.
입출력 예시
let output = tiling(2);
console.log(output); // --> 2문제해결
1. 팩토리얼 재귀함수
let tiling = function (n) {
let twoMax = Math.floor(n / 2);
let sum = 0;
let result = 0;
function repeat(n, i) {
if (i >= 1) {
sum = n * repeat(n - 1, i - 1);
} else if (i === 0) {
return 1;
}
return sum;
}
for (let i = 1; i <= twoMax; i++) {
result += repeat(n - i, i) / repeat(i, i);
}
// 모든 세로로 배치한 경우가 하나 있기 때문에 1을 더해줌
return result + 1;
};처음 풀었던 방식은 팩토리얼로 해결하였다.
타일이 2행으로 구성되어있기 때문에, 1행에서 세로로 놓을지, 가로로 놓을지를 결정하면 2행은 고려할 필요가 없다.
때문에, 1행에 가로로 놓을 타일의 개수를 계산하여 가로로 놓을 타일이 몇개인지에 따라 모든 경우에 수를 구해주면 된다.
이때 팩토리얼로 경우의 수를 더해주고, 가장 마지막에 모두 세로로 놓는 경우 1을 더해주면 답이 나오게 된다.
시간을 측정해보니 대략 0.09~0.15ms의 시간이 걸린다.
2. 피보나치 수열 적용
let tiling = function (n) {
let arr = [0, 1];
for (let i = 2; i <= n + 1; i++) {
arr.push(arr[i - 2] + arr[i - 1]);
}
return arr[arr.length - 1];
};이 풀이는 대략 0.035~0.0.073ms의 시간이 걸린다.
1번 풀이보다 훨씬 빠르다.
프로그래머스 문제2 멀리뛰기 문제를 풀었을 때, 피보나치의 규칙이 보였다. 문제 2 멀리뛰기는 손으로 계산하며 풀었는데, 그때 규칙을 알아차리고 피보나치 수열로 간단하게 문제를 풀 수 있었다.
프로그래머스 멀리뛰기 문제를 푸니, 문제1번이 다시 떠올랐다.
어?? 이거 이전에 타일문제랑 비슷한데???
다시 문제를 보니 풀이2와 같이 간단한 코드가 만들어졌다.
피보나치 수열을 적용할 수 있는 문제가 존재하는 것 같다.
다양한 문제를 풀어보고 정리해 두어야겠다.
🖍 문제 2 멀리뛰기
문제 설명
효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는
(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)
의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.
제한 사항
n은 1 이상, 2000 이하인 정수입니다.
프로그래머스 멀리뛰기 문제는 위의 문제와 동일하다.
배열의 길이에 1과 2가 배치되는 경우의 수를 구하면 된다.
이때 피보나치 수열을 적용하면 간단하게 풀리는 문제였다.
하지만, 멀리뛰기문제의 경우 n의 길이가 2000개 이하이기 때문에, js 정수 오버플로우가 발생한다.
때문에 문제에서 1234657을 나눈 나머지를 리턴하라는 조건이 있는 것 같다.
자바스크립트에서 산술 연산의 결과가 표현할 수 있는 가장 큰 수 보다 더 크다면 오버플로우(Overflow)가 발생하며 무한대를 의미하는 Infinity 값을 출력합니다. 언더플로우의 경우 자바스크립트가 표현할 수 있는 가장 작은 수보다 더 작을 때 발생하며, -Infinity 값을 출력합니다.
자바스크립트의 산술 연산에서 0으로 나누는 행위는 에러를 발생시키지 않습니다. 양의 정수 혹은 음의 정수를 0으로 나눌 때 Infinity 혹은 –Infinity 값을 반환합니다. 한 가지 예외가 있다면 0을 0으로 나눌 때 발생합니다. 이 경우에 반환되는 값은 정의 되지 않은 값을 가지며 그 결과로 NaN(Nat a Number) 값을 출력합니다.
자바스크립트에서 숫자는 모두 '64 비트 IEEE 754 형식'으로 다뤄진다. 우리가 콘솔에 0.1을 입력하면, 자바스크립트는 이를 '64 비트 IEEE 754 형식'에 따라 2진법으로 바꾸고 그 결과를 다시 10진법으로 바꿔 화면에 표시한다.
'64 비트 IEEE 754 형식'에서는 -(2^53 - 1)부터 2^53 - 1 사이의 수가 안전하다(여기서 안전함이란 정수를 정확하고 올바르게 비교할 수 있음을 의미한다). 즉 안전한 가장 큰 정수는 9007199254740991, 가장 작은 정수는 -9007199254740991이다.
