한동안 알고리즘을 안풀다가 다시 풀어본다.
https://leetcode.com/problems/n-th-tribonacci-number/description/
1. 문제
2. 내 풀이
3. 다른 풀이
4. memoization
5. 관련된 다른 알고리즘 문제들
6. 피보나치 공식 (binet's formula)
1. 문제
The Tribonacci sequence Tn is defined as follows:
T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.
Given n, return the value of Tn.(해석 - 의역)트리보나치 숫자를 다음과 같이 정의한다.
(T0) 0번째 숫자: 0
(T1) 1번째 숫자: 1
(T2) 2번째 숫자: 1
임의의 0이상의 정수에 대하여 다음을 만족한다.
Tn+3 = Tn + Tn+1 + Tn+2
n번째 트리보나치 숫자를 구하시오.2. 내 풀이
const tribonacci = (n) => {
if(n === 0) return 0
if(n === 1) return 1
if(n === 2) return 1
let a = 0
let b = 1
let c = 1
for(let i = 3; i <= n; i++){
let d = a + b + c
a = b
b = c
c = d
}
return c
}재귀함수를 이용하여 풀 수도 있다.
const tribonacci = (n) => {
if(n === 0) return 0
if(n === 1) return 1
if(n === 2) return 1
return tribonacci(n-1) + tribonacci(n-2) + tribonacci(n-3)
}3. 다른 사람의 풀이
ahmedengu의 풀이
var tribonacci = function(n) {
if (mem[n] !== undefined) return mem[n];
return mem[n] = tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3);
};
const mem = {
0: 0,
1: 1,
2: 1
};그 전의 결과값을 저장하는게 신기했는데 이에 관련해서 찾아보다가
memoization에 관련하여 찾아보게 되었다.
4. memoization
- 프로그래머스 - 피보나치 수
https://school.programmers.co.kr/learn/courses/30/lessons/12945
프로그래머스에서 피보나치 문제를 풀 당시 재귀함수로 풀었었다.
그 당시에는 그 전의 결과값을 알아서 가지고 있겠거니 했었는데
그렇지 않았다.
5번째 피보나치 숫자를 구하기 위해 함수가 15번 작동한다.
- 왜 15번(여러번) 작동하는가?
5번째를 구하기 위해서는 4번째와 3번째가 필요하다
4번째를 구하기 위해서는 3번째와 2번째가 필요하다
...
문제는 그림과 같이 동일한 수를 위해 여러번 동작한다
예) 2번째 수를 구하는것을 3번한다.
그래서 전에 한번 계산한 값은 다른 곳에 잠시 저장해두어 효율을 더 높이는 것이 필요하다.
- memoization
이전의 계산한 결과를 임시의 공간에 저장해두고
그 결과값이 필요하면 불러오는 것이다.
(caching하는 것이다.)
=> 5번째 피보나치 수를 구하기 위해 3번째 피보나치가 2번 필요하다.
=> 3번째를 한번 계산하고 임시공간에 저장해둔다.
=> 그 다음에 사용할때는 그 임시공간에서 바로 가져온다.
=> 3번째를 구하기위해 중복적인 작업이 없어진다.
그림과 같이 횟수가 줄어든다.
- 언제 memoization을 사용하나요?
문제를 반복적인 작은 문제들로 쪼갤수 있으면 사용해보는 것이 좋을 것 같다.
5. 관련된 다른 알고리즘 문제들
- Fibonacci Number
- Climbing Stairs
6. 피보나치 공식 (binet's formula)
위의 문제들중 509. Fibonacci Number에서 다른 사람들의 풀이를 보면 n번째 숫자를 바로 구해주는 공식이 있다. 신기해서 적어본다.
(이상하게 생각할 수도 있지만 저렇게 분자가 저런 형태면(괄호안의 숫자를 더하면 정수가 되는 형태) 신기하다 생각해왔고 저것이 내 눈길을 끌었다.)
고민을 해보았지만 저게 왜 맞는지 이해가 안됐었다.
밑의 사이트에 들어가 풀이를 보면 바로 이해가 된다.
https://artofproblemsolving.com/wiki/index.php/Binet%27s_Formula
