[백준 10870] Java - 피보나치 수 5

https://www.acmicpc.net/problem/10870

 

피보나치 수 5

 

 

1)  문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다.
그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.
n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597
n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력: 첫째 줄에 n이 주어진다. n은 20보다 작거나 같은 자연수 또는 0이다.

출력: 첫째 줄에 n번째 피보나치 수를 출력한다.

 

 

2)  예시

예제입력 : 10

예제출력 : 55

 

 

 

3)  풀이

 

* 아이디어
1) 정수 n이 주어지고 n번째 피보나치수를 구하는 것 -> 수열의 특정항을 구하는 것

2) 점화식 (이전항을 이용해 다음항을 구하는) 문제 -> 반복과 재귀를 이용

3) base case는 f(0)=0, f(1)=1

 

 

 

 

4)  코드

//이 코드를 실제로 실행하면 함수 호출이 나무처럼 퍼졌다가, 리턴하면서 다시 값을 합쳐서 올라오는 구조입니다.

import java.util.Scanner;
// 유틸 패키지의 Scanner 클래스 사용목적


public class Main {
// 메인 클래스 정의

    public static int fibonacci(int n) {
// 정수값을 반환하는 피보나치 메소드를 정의
// static으로 객체 생성 없이 호출할 수 있게 해줌

        if (n == 0) return 0;
        // 첫번째 종료조건으로 n이 0이면 피보나치수열 0번째항은 0이므로 그대로 반환

        if (n == 1) return 1;
		// 두번째 종료조건으로 n이 1일 경우에는 1번째 피보나치 수는 1이므로 1을 반환
		// 이 두개의 종료조건이 없으면 무한재귀 발생으로 StackOverflow가 발생

        return fibonacci(n - 1) + fibonacci(n - 2); // recursive case
		// 재귀 호출 부분
    }

    public static void main(String[] args) {
		// 프로그램의 시작점
        Scanner sc = new Scanner(System.in);
		// 사용자로부터 입력을 받기 위해 스캐너 객체 생성
        int n = sc.nextInt();
        // 사용자로부터 입력을 받아 변수 n에 저장

        System.out.println(fibonacci(n));
		// n번째 피보나치 수를 계산하고 콘솔에 출력
    }
}

 

 

// 동작 흐름
fibonacci(5)
→ fibonacci(4) + fibonacci(3)
→ (fibonacci(3) + fibonacci(2)) + (fibonacci(2) + fibonacci(1))
→ ...
→ 최종값: 5

 

 

 

예제 문제 시각화 풀이

f(5)에서 시작하여, f(4)와 f(3)을 순차적으로 재귀 호출을 하고,
각 노드는 자기 자신을 두 번 더 호출하면서 점점 하위로 내려갑니다
리프 노드(f(0), f(1))는 종료 조건(base case)이 적용된 부분입니다

 

 

 

 

5)  리뷰

처음으로 피보나치 수열 문제를 풀어봤는데, 재귀 함수의 개념을 익히기에 딱 좋은 문제였습니다.
종료 조건을 설정하고 함수가 자기 자신을 호출하는 구조를 직접 짜보니, 재귀의 흐름에 대한 감이 잡히는 것 같습니다.
아직은 호출 흐름이 헷갈릴 때도 있지만, 계속 연습하면 익숙해질 것 같습니다.