[C, Java, Python] 피보나치 수열(Fibonacci numbers) 코드로 이해하기

 

 

 

 

피보나치 수열을 C 언어로 구현하는 방법에는 여러 가지가 있지만, 가장 기본적인 방법은 재귀와 반복문을 사용하는 것입니다. 아래에는 두 가지 방법을 소개하겠습니다.

1. 반복문을 이용한 피보나치 수열 구현

이 방법은 효율적이며, 메모리 사용량이 적습니다.

#include <stdio.h>

// 피보나치 수열을 반복문으로 계산
void fibonacci(int n) {
    int a = 0, b = 1, next;

    printf("Fibonacci series up to %d terms:\n", n);

    for (int i = 0; i < n; i++) {
        if (i <= 1) {
            next = i;
        } else {
            next = a + b;
            a = b;
            b = next;
        }
        printf("%d ", next);
    }
    printf("\n");
}

int main() {
    int n;

    printf("Enter the number of terms: ");
    scanf("%d", &n);

    if (n <= 0) {
        printf("Please enter a positive integer.\n");
    } else {
        fibonacci(n);
    }

    return 0;
}

설명:

1. fibonacci 함수는 피보나치 수열의 처음 n개의 항을 출력합니다.
2. a와 b는 피보나치 수열의 첫 두 항(0과 1)을 저장합니다.
3. 반복문을 통해 피보나치 수열을 계산합니다. next는 현재 항을 저장합니다.
4. 반복문 내에서 next를 업데이트하고, a와 b를 이동시킵니다.
5. 메인 함수에서 사용자가 입력한 항의 수를 읽고 fibonacci 함수를 호출합니다.

2. 재귀를 이용한 피보나치 수열 구현

이 방법은 코드가 간단하지만, 큰 n에 대해서는 비효율적일 수 있습니다.

#include <stdio.h>

// 재귀를 이용한 피보나치 수 계산
int fibonacci(int n) {
    if (n <= 1)
        return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int n;

    printf("Enter the number of terms: ");
    scanf("%d", &n);

    printf("Fibonacci series up to %d terms:\n", n);
    for (int i = 0; i < n; i++) {
        printf("%d ", fibonacci(i));
    }
    printf("\n");

    return 0;
}

설명:

1. fibonacci 함수는 재귀적으로 피보나치 수를 계산합니다.
2. 기본 조건으로 n이 0 또는 1일 때 n을 반환합니다.
3. 그 외의 경우에는 fibonacci(n - 1) + fibonacci(n - 2)를 반환합니다.
4. 메인 함수에서 사용자가 입력한 항의 수에 대해 피보나치 수열을 출력합니다.

성능 비교

• 반복문: O(n) 시간 복잡도를 가지며, 메모리 사용이 적고 큰 n에 대해서도 효율적입니다.
• 재귀: 시간 복잡도가 O(2^n)으로 매우 비효율적이며, 큰 n에 대해서는 성능이 급격히 떨어집니다. 메모리 사용량도 많을 수 있습니다.

실제 구현에서는 반복문을 사용하는 방법이 더 일반적입니다.

피보나치 수열을 자바로 구현하는 방법도 여러 가지가 있지만, 가장 기본적인 방법은 반복문과 재귀를 사용하는 것입니다. 각각의 방법을 소개하겠습니다.

1. 반복문을 이용한 피보나치 수열 구현

이 방법은 효율적이며, 메모리 사용량이 적습니다.

import java.util.Scanner;

public class Fibonacci {

    // 피보나치 수열을 반복문으로 계산
    public static void fibonacci(int n) {
        int a = 0, b = 1, next;

        System.out.println("Fibonacci series up to " + n + " terms:");

        for (int i = 0; i < n; i++) {
            if (i <= 1) {
                next = i;
            } else {
                next = a + b;
                a = b;
                b = next;
            }
            System.out.print(next + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("Enter the number of terms: ");
        int n = scanner.nextInt();

        if (n <= 0) {
            System.out.println("Please enter a positive integer.");
        } else {
            fibonacci(n);
        }

        scanner.close();
    }
}

설명:

1. fibonacci 메소드는 피보나치 수열의 처음 n개의 항을 출력합니다.
2. a와 b는 피보나치 수열의 첫 두 항(0과 1)을 저장합니다.
3. 반복문을 통해 피보나치 수열을 계산합니다. next는 현재 항을 저장합니다.
4. 반복문 내에서 next를 업데이트하고, a와 b를 이동시킵니다.
5. 메인 메소드에서 사용자로부터 입력받은 항의 수를 읽고 fibonacci 메소드를 호출합니다.

2. 재귀를 이용한 피보나치 수열 구현

이 방법은 코드가 간단하지만, 큰 n에 대해서는 비효율적일 수 있습니다.

import java.util.Scanner;

public class Fibonacci {

    // 재귀를 이용한 피보나치 수 계산
    public static int fibonacci(int n) {
        if (n <= 1)
            return n;
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("Enter the number of terms: ");
        int n = scanner.nextInt();

        System.out.println("Fibonacci series up to " + n + " terms:");
        for (int i = 0; i < n; i++) {
            System.out.print(fibonacci(i) + " ");
        }
        System.out.println();

        scanner.close();
    }
}

설명:

1. fibonacci 메소드는 재귀적으로 피보나치 수를 계산합니다.
2. 기본 조건으로 n이 0 또는 1일 때 n을 반환합니다.
3. 그 외의 경우에는 fibonacci(n - 1) + fibonacci(n - 2)를 반환합니다.
4. 메인 메소드에서 사용자로부터 입력받은 항의 수에 대해 피보나치 수열을 출력합니다.

성능 비교

• 반복문: O(n) 시간 복잡도를 가지며, 메모리 사용이 적고 큰 n에 대해서도 효율적입니다.
• 재귀: 시간 복잡도가 O(2^n)으로 매우 비효율적이며, 큰 n에 대해서는 성능이 급격히 떨어집니다. 또한, 메모리 사용량이 많을 수 있습니다.

실제 구현에서는 반복문을 사용하는 방법이 더 일반적이며, 재귀는 주로 알고리즘의 설명이나 작은 문제에 사용됩니다.

피보나치 수열을 Python으로 구현하는 방법도 여러 가지가 있지만, 가장 기본적인 방법은 반복문과 재귀를 사용하는 것입니다. 각각의 방법을 소개하겠습니다.

1. 반복문을 이용한 피보나치 수열 구현

이 방법은 효율적이며, 메모리 사용량이 적습니다.

def fibonacci(n):
    a, b = 0, 1
    result = []

    print(f"Fibonacci series up to {n} terms:")
    for _ in range(n):
        result.append(a)
        a, b = b, a + b

    print(" ".join(map(str, result)))

def main():
    n = int(input("Enter the number of terms: "))

    if n <= 0:
        print("Please enter a positive integer.")
    else:
        fibonacci(n)

if __name__ == "__main__":
    main()

설명:

1. fibonacci 함수는 피보나치 수열의 처음 n개의 항을 계산하여 리스트에 저장합니다.
2. a와 b는 피보나치 수열의 첫 두 항(0과 1)을 저장합니다.
3. 반복문을 통해 피보나치 수열을 계산합니다. result 리스트에 각 항을 추가합니다.
4. a와 b를 업데이트하여 다음 항을 계산합니다.
5. 메인 함수에서 사용자로부터 입력받은 항의 수를 읽고 fibonacci 함수를 호출합니다.

2. 재귀를 이용한 피보나치 수열 구현

이 방법은 코드가 간단하지만, 큰 n에 대해서는 비효율적일 수 있습니다.

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

def main():
    n = int(input("Enter the number of terms: "))

    print(f"Fibonacci series up to {n} terms:")
    for i in range(n):
        print(fibonacci(i), end=" ")
    print()

if __name__ == "__main__":
    main()

설명:

1. fibonacci 함수는 재귀적으로 피보나치 수를 계산합니다.
2. 기본 조건으로 n이 0 또는 1일 때 n을 반환합니다.
3. 그 외의 경우에는 fibonacci(n - 1) + fibonacci(n - 2)를 반환합니다.
4. 메인 함수에서 사용자로부터 입력받은 항의 수에 대해 피보나치 수열을 출력합니다.

성능 비교

• 반복문: O(n) 시간 복잡도를 가지며, 메모리 사용이 적고 큰 n에 대해서도 효율적입니다. 성능이 좋고 직관적입니다.
• 재귀: 시간 복잡도가 O(2^n)으로 매우 비효율적이며, 큰 n에 대해서는 성능이 급격히 떨어집니다. 메모리 사용량도 많을 수 있으며, 중복 계산이 많이 발생합니다.

실제 구현에서는 반복문을 사용하는 방법이 더 일반적입니다. 재귀 방법은 코드가 간단하지만, 성능 문제가 있을 수 있으므로 작은 문제나 학습용으로 주로 사용됩니다.