🌀 파보나치 수열이란?

• *파보나치 수열(Fibonacci Sequence)**은 다음과 같은 규칙으로 이루어진 숫자들의 나열이야:

처음 두 숫자는 0과 1이고,

그 다음 숫자는 바로 앞의 두 숫자를 더한 값이야.

🔢 예를 들면:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

문제

숫자 n이 주어졌을 때, n의

피보나치(Fibonacci) 수열을 출력하는 프로그램을 작성하시오.

(단, 피보나치 수를 구하는알고리즘의 시간 복잡도는 O(n)으로 구현해야 함)

(프로젝트 명은 Ex1C++로 작성하라.)

문제 설명

l  피보나치(Fibonacci) 수는 수학에서 다음과 같이 정의된다.

l  8의 피보나치 수열은 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21

0, 1, 1, 2, 3,
5, 8, 13, 21

l  n의 피보나치(Fibonacci) 수를 구하는 알고리즘은 반드시 다음

형식의 함수(메서드)로 작성할 것.

unsigned long fibo(int n)

l  피보나치(Fibonacci) 수를 구하는 알고리즘의 시간 복잡도는 O(n)으로

구현해야 함

입력

• n 값은 프로그램 실행 시 콘솔 키보드로부터 정수의 형태로 입력 받음
• 피보나치 수열을 구하기 위하여 입력 받는 n 값의 범위는 0 ~ 20으로 함

출력

• 입력 받은 n 값에 해당하는 피보나치 수열을 콘솔 터미널에 출력함

C++

/*숫자 n이 주어졌을 때, n의
피보나치(Fibonacci) 수열을 출력하는 프로그램을 작성하시오. */
#include <iostream>

using namespace std;

int cycle;

int main () {
    cout << "파보나치 연산 횟수 입력 : ";
    cin >> cycle;

    int* arr = new int[cycle + 2];

    arr[0] = 0;
    arr[1] = 1;

    for(int i = 0; i < cycle - 1; i++) {
        arr[i + 2] = arr[i] + arr[i + 1];
    }

    for(int i=0; i < cycle + 1; i++) {
        cout << arr[i];
        if(i != cycle)
            cout << ", ";
    }
    cout << endl;

    delete[] arr;
    return 0;
}

JS

const readline = require('readline');
const rl = readline.createInterface({
    input:process.stdin,
    output:process.stdout,    
})

let cycle;
let arr = [0, 1];

rl.question('파보나치 연산 수 입력: ', e => {
    cycle = Number(e);

    for(let i = 0; i < cycle - 1; i++) {
        arr.push(arr[i] + arr[i + 1]);
    }
    console.log(arr);

    rl.close();
})

PY

cycle = int(input("파보나치 연산 수 입력 : "))
arr = [0, 1]

for i in range(cycle - 1):
    arr.append(arr[i] + arr[i+1])
print(arr)