피보나치 수열 출력. 알고리즘, 자바

 

문제

 

n을 입력 했을 때 피보나치 수열을 출력하기

피보나치 수열이란, 이전의 두 숫자를 더해서 나온 결과 값을 모두 모아놓은 수열이다.

예를 들어서 7을 입력하면 

1 1 2 3 5 8 13

위와 같은 결과를 출력한다. 그리고 n은 아래와 같은 값을 만족한다.

3 <= n <= 45

 

난이도

 

하

 

 

설명

 

이 문제를 푸는데에는 아래와 같은 두가지 방법이 있다.

• n크기의 배열을 만들어서 푸는 방법
• 3개의 인덱스(변수)를 만들어서 푸는 방법

 

n크기의 배열을 만들어 푸는 방법

 

n은 2보다 크기 때문에 0번 인덱스와 1번 인덱스는 확정적으로 1값이 들어간다. 

그리고 다음 인덱스의 번호를 i라고 할 때 i에 해당하는 값은 i-1과 i-2번의 합이다.

따라서 아래와 같이 풀이할 수 있다.

/**
 * 배열을 사용한 방법
 * */
public int solution_1(int n) {
    int answer = 0;

    int[] nums = new int[n];

    // 첫 두 수는 값을 채워 넣는다. ( n > 2)
    nums[0] = 1;
    nums[1] = 1;

    // 피보나치 수열을 만든다.
    for (int i=2; i<n; i++) {
        nums[i] = nums[i-1] + nums[i-2];
    }

    // 피보나치 수열을 출력한다.
    for (int i=0; i<n; i++) {
        if (i < n-1) {
            System.out.print(nums[i] + " ");
        } else {
            System.out.print(nums[i]);
        }
    }

    return answer;
}

깃허브 : github.com/donghyeon0725/algorithm_java/blob/master/src/com/inflearn/two/Four.java

 

 

3개의 인덱스(변수)를 만들어서 푸는 방법

 

푸는 원리는 위와 동일 하다.

지금 계산하려고 하는 수열의 인덱스 값을 i라고 할 때 (예를 들어서 2번 인덱스 값은 1+1=2)

i에 해당 하는 값을 출력 한 뒤라면, 다음 값인 i+1번을 계산하기 위해 필요한 인덱스 번호는 i-1과 i번이다.

따라서 i-2번은 필요 없으므로

i-1, i-2 번에 해당할 변수 2개와 해당 값을 임시로 저장해놓을() 공간 하나까지 3개의 변수가 필요하다.

/**
 * 바로 출력하는 방법
 * */
public void solution(int n) {
    int answer = 0;

    int b1 = 1;
    int b2 = 1;

    // 첫 두개의 숫자를 먼저 출력한다.
    System.out.print(1 + " " + 1 + " ");

    // n보다 2 작은 값(기본값 제외)까지 반복
    for (int i=0; i<n-2; i++) {
        int temp = b2;
        b2 += b1;
        b1 = temp;

        // 마지막 출력의 경우 공백 없이 출력이 되어야 함
        if (i < n-3) {
            System.out.print(b2 + " ");
        } else {
            System.out.print(b2);
        }
    }
}

깃허브 : github.com/donghyeon0725/algorithm_java/blob/master/src/com/inflearn/two/Four.java