LearnApplyShare

[알고리즘] 피보나치 수

May 04, 2018 - [피보나치수열, fibonacci]

Problem

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2칸) 의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 출력하는 jumpCase 함수를 완성하세요. 예를 들어 4가 입력된다면, 5를 반환해 주면 됩니다.


Solution

칸의 수가 n 개 주어졌을 때 총 멀리뛰기 방법의 수를 j(n)이라 하자. n칸을 멀리뛰기 하는 전체 방법의 수는 최초 1칸을 뛰었을 경우와 최초 2칸을 뛰었을 경우 2가지로 나누어 볼 수 있다. 첫번째 경우의 방법의 수는 남아있는 칸의 수가 n-1 개 이므로 j(n-1)이 되고 두번째 경우의 방법의 수는 남아있는 칸의 수가 n-2개 이므로 j(n-2)가 된다. 그러므로 j(n) = j(n-1) + j(n-2) 와 같이 표현될 수 있다.


JS Code

// 1. 반복문
function jumpCase(num) {
var arr = [1,2];
for(var i=0; arr.length<num; i++){
arr.push(arr[i]+arr[i+1]);
}
return arr[num-1];
}
// 2. 재귀함수 & memoization
const jumpCase = (function(){
let arr = [1,2];
return function(num){
return arr[num-1] ? arr[num-1] : arr[num-1] = jumpCase(num-2) + jumpCase(num-1);
}
})();
// 3. 꼬리재귀
function jumpCase(num, a = 0, b = 1){
return num==0 ? b : jumpCase(num-1, b, a+b);
}
// 4. 꼬리재귀 & memoization
const jumpCase = (function(){
let = [];
return function(num, a = 0, b = 1){
// 첫번째 함수 호출시 이미 계산된 값이 있으면 그 값을 리턴
if(a==0 && arr[num]) return arr[num];
// 이미 앞서 계산한 값들을 이용
if(a==0 && arr.length>2 && num>arr.length-1){
num -= arr.length-1;
a = arr[arr.length-2];
b = arr[arr.length-1];
}else{
// 새로 계산된 결과는 저장
arr.push(b);
}
return num==0 ? b : jumpCase(num-1, b, a+b);
}
})();
view raw fibonacci.js hosted with ❤ by GitHub

Ref.