[알고리즘] 피보나치 수
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
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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); | |
} | |
})(); |