[백준 알고리즘] 2747번 (피보나치 수)

[백준 알고리즘]

오늘 풀어본 문제는 피보나치 수열입니다.

피보나치 수열은 간단하게 

0 / 1 / 1 / 2 / 3 / 5 / 8 / 13 .... 이렇게 진행이됩니다.

식으로 나타내면 

F(n) = F(n-1) + F(n-2)  // (n >=2) 

이렇게 됩니다. 간단한 알고리즘입니다.

하지만 백준 알고리즘에서는 원하는게 재귀함수를 원하고 있습니다.

재귀 함수는 자기 자신을 재참조 하는 것입니다.

이 피보나치 수열이 재귀함수에서 가장 기본이 된다고 할 수 있습니다.

다음 문제를 보겠습니다.

간단한 문제입니다.

바로 코딩을 보겠습니다.

import java.util.Scanner;
 
public class Beak2747 {
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int result = fibonacci(n);
        
        System.out.println(result);
    }
 
    public static int fibonacci(int number) {
        if(number <= 1)
            return number;
        else
        return fibonacci(number - 2) + fibonacci(number - 1); // 1번
    }
}
 

fibonacci( ) 클래스를 만들었습니다.

그 fibonacci클래스는 다시 자기 자신을 불러옵니다.(1번)

이것이 바로 재귀함수입니다.

가장 기초적인 문제이기 때문에 이해하시는데 크게 어려움이 없을 것입니다.

그래도 한번 예제를 보여 드리도록 하겠습니다.

만약 입력 값이 5라면

여기서 fibonacci(1) / finbonacci(2) 에들어가는 값은 각각 1이 됩니다.

그래서 아래서 부터 더해서 올라가게 되면 최종 리턴 값은 5가 됩니다.

직접 손으로 그려서 해보시길 추천합니다.

직접 손으로 그려보면 금방 이해가 되실겁니다.