피보나치 수열

문제 : 2 이상의 n이 입력되었을 때, fibonacci 함수를 제작하여 n번째 피보나치 수를 반환해 주세요. 

ex) n = 3이라면 3 번째 피보나치 수인 2를 반환

---

[정리]

이탈리아의 상인이며 수학자인 피보나치(Fibonacci ; 1170 ~ 1250)는 중세 유럽의 대수학자이다. 

1170년 이탈리아 피사(Pisa)의 상업 중심지에서 태어나 '피사의 레오나르도(Leonardo)'라고 불리었다.

피보나치 수열 : 처음 두 항을 1과 1로 한 후, 그 다음 항부터는 바로 앞의 두 개의 항을 더해 만드는 수열을 말한다.

만일 을 정의한다면, 위의 관계식과 마찬가지로 , 즉 이 되어야 하므로 이 된다. 따라서 수열의 초깃값을 종종 과 로 정의하기도 한다.

#참조 - 네이버 수학백과

[예]

# 1과 1로 시작할 경우 : 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

# 0과 1로 시작할 경우 : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

※ Environment : Java

---

#피보나치 수열 알고리즘 - Programmers 참조

#myself

public long fibonacci(int num) {
    long answer = 0;
 
    if(num == 0) return 0;
    if(num == 1) return 1;
 
    if(num > 1) {
        long a = 0;
        long b = 1;
 
        for(int i = 1; i < num; i++) {
            answer = a + b;
            a = b;
            b = answer;
        }
    }
    
    return answer;
}

+ 0 ~ 1 번째까지는 바로 0 또는 1을 리턴

+ 2 번째부터 num - 1 만큼 반복

+ 피보나치 수열을 유지하기 위해 answer = a + b,  a = b, b = answer 대입

# fibonacci(4)

# 3번 반복

1. i = 1, answer = 0 + 1; a = 1; b = 1;

2. i = 2, answer = 1 + 1; a = 1; b = 2;

3. i = 3, answer = 1 + 2; a = 2; b = 3;

4. Result

# answer = 3;

# 0, 1, 1, 2, "3"

#1 (재귀함수로 구현을 해보고 싶었으나, 한계로 다른 사람의 풀이를 참조)

public long fibonacci(int num) {
    long answer = 0;
    if(num < 2){
        answer = num;
    } else {
        answer = fibonacci(num - 1) + fibonacci(num - 2);
    }
    return answer;
}

+ 재귀함수를 이용한 피보나치 수열 구현

+ 4 번째에 대한 피보나치 수를 구하는 재귀함수 동작 방식

#2

public long fibonacci(int num) {
    long answer = 0;
    long[] dp = new long[num + 1];
    dp[0] = 0;
    dp[1] = 1;
 
    for(int i = 2 ; i <= num; i++){
        dp[i] = dp[i - 1] + dp[i - 2];
    }
 
    return dp[num];
}

+ 배열을 이용한 피보나치 수열 구현

# fibonacci(3)

# 2번 반복

1. i = 2, dp[2] = dp[1] + dp[0]; >> dp[2] = 1 + 0;

2. i = 3, dp[3] = dp[2] + dp[1]; >> dp[3] = 1 + 1;

3. Result

# dp[3] = 2

# 0, 1, 1, "2"