<2.4> 피보나치 수열

문제
: 사용자로부터 N값을 입력받아 , 1번째 항부터 N번째 항까지의 피보나치 수열값을 모두 출력
(단 1번째 항은 1이라고 가정, 이때 N 은 3이상 45이하의 자연수)
EX) 3을 입력받으면 -> 1 1 2 를 출력해야 함
EX) 5를 입력받으면 -> 1 1 2 3 5 를 출력해야 함
EX) 10을 입력받으면 -> 1 1 2 3 5 8 13 21 34 55

이 문제의 요구사항은 곧 N번째 항까자의 피보나치 수열 값을 출력하는 것이다.
따라서 우리가 알고있는 "이전항 + 이전이전항" = "다음항" 이 되는 피보나치 수열의 논리를 코드로 풀어내면 문제를 쉽게 해결할 수 있다.

[해결책]
1. Array섹션인 만큼 배열을 사용
: arr[0] 에 0 을 , arr[1]에 1을 미리 대입해둔 뒤, 반복문을 돌면서
arr[i]=arr[i-2]+arr[i-1] 연산을 하여 피보나치 수열 값을 구할 수 있다.

2. 배열을 사용하지 않고
   : 3개의 변수 a1, a2, a3를 선언한 후, a1=0, a2=1을 대입한 후, 반복문을 돌면서 <a3=a1+a2; (a3출력) a1=a2; a2=a3;> 의 과정을 반복하면 된다.

위 두 해결책을 각각 solution(), solution2() 메서드로 구현한 코드를 아래에서 확인할 수 있다.

import java.util.Scanner;

public class Main {

    public static void solution(int N){
        int[] fibo = new int[N+1];

        fibo[0] = 0;
        fibo[1] = 1;

        for(int i=2; i<=N; i++){
            fibo[i] = fibo[i-1] + fibo[i-2];
        }

        for(int i=1; i<=N; i++){
            System.out.print(fibo[i] + " ");
        }

    }

    public static void solution2(int N){
        int a1 = 0;
        int a2 = 1;
        int a3 = a1+a2;

        System.out.print(a2 + " ");
        for(int i=2; i<=N; i++){
            System.out.print(a3 + " ");
            a1 = a2;
            a2 = a3;
            a3 = a1 + a2;
        }
    }


    public static void main(String[] args) {

        //0. Scanner 준비
        Scanner sc = new Scanner(System.in);

        //1. n번째 항인지, n을 입력
        int N = sc.nextInt();

        //2. 그 n을 인자로 넘기면서 solution()을 호출하여 , 결과 피보나치 수열을 출력
        solution2(N);
    }
}

참고로 피보나치 수열은 재귀함수를 통해서도 해결할 수 있는걸로 기억하지만 ,
이는 이미 계산한 값임에도 불구하고 함수를 다시 호출해서 계산해야 하는 비효율적인 측면이 있기 때문에 , 재귀함수를 이용해서 문제를 해결하지는 않았다.