트리보나치 수열이란?
트리보나치(Tribonacci) 수열은 피보나치 수열을 일반화한 개념입니다. 피보나치 수열에서는 각 항이 앞의 두 항의 합으로 결정되지만, 트리보나치 수열에서는 각 항이 바로 앞의 세 항의 합으로 결정됩니다.
예를 들어 트리보나치 수열의 첫 몇 개 항은 다음과 같습니다.
0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149
각 숫자가 이전 세 개의 숫자를 더한 값임을 확인할 수 있습니다. 예를 들어 7은 2 + 4 + 1의 결과이며, 13은 4 + 7 + 2의 결과입니다.
문제 정의
숫자 하나, 예를 들어 num을 인수로 받는 자바스크립트 함수를 작성해야 합니다.
이 함수는 트리보나치 수열의 첫 num개 항을 담고 있는 배열을 반환해야 합니다.
재귀를 활용한 구현
가장 직관적인 방법은 재귀(recursion)를 사용하는 것입니다. 기저 조건(base case)을 먼저 처리한 뒤, 그 외의 경우에는 세 번의 재귀 호출 결과를 더해 반환합니다.
const tribonacci = (num = 1) => {
if (num === 0 || num === 1 || num === 2) {
return 0;
}
if (num === 3) {
return 1;
} else {
return tribonacci(num - 1) +
tribonacci(num - 2) +
tribonacci(num - 3);
}
};
const trib = num => {
const res = [];
for (let i = 1; i <= num; i++) {
res.push(tribonacci(i));
}
return res;
};
console.log(trib(15));코드 동작 방식
- tribonacci(n): n번째 트리보나치 항을 재귀적으로 계산합니다. n이 1 또는 2이면 0을, n이 3이면 1을 반환하는 것이 기저 조건입니다.
- trib(num): 1부터 num까지 반복하면서 각 항을 배열에 차례대로 저장한 뒤 완성된 배열을 반환합니다.
출력 결과
위 코드를 실행하면 콘솔에 다음과 같은 배열이 출력됩니다.
[ 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927 ]
참고: 성능 개선 팁
위 재귀 구현은 같은 값을 여러 번 계산하기 때문에 n이 커지면 실행 시간이 지수적으로 증가합니다. 실제 프로젝트에서는 메모이제이션(memoization)을 적용하거나, 반복문으로 세 변수만 유지하며 계산하는 방식(O(n))을 사용하는 것이 좋습니다.