[Java] 피보나치 수열 출력하기 | 인프런 | 단순 재귀 와 메모이제이션 방식

문제

숫자 N을 입력하면 원소의 갯수가 N개인 피보나치 수열을 출력하는 프로그램을 작성하세요

 

풀이1 - 재귀함수 이용하기

피보나치는 바로 앞 두 원소를 더해서 새로운 원소값을 설정합니다. 식으로 표현하면 다음과 같습니다.

f(n) = f(n-2) + f(n-1) (단, n>=2, f(1)=1, f(2)=1)

따라서 첫 번째 원소나 두 번째 원소라면 재귀를 탈출하고 그게 아니라면 앞 두 원소를 더하는 과정으로 문제를 풀면 됩니다.

재귀함수는 보통 if-else구문으로 푸나 여기서는 if-elseif-else 구조로 문제를 풀겠습니다. 두 조건을 합춰 if-else로 만들어도 상관은 없습니다.

 

import java.util.Scanner;

public class Main {
    public static int recursion(int n) {
        if (n == 1) return 1;   // 첫 번째 원소라면
        else if (n==2) return 1;    //두 번째 원소라면
        else {  
            return recursion(n-2) + recursion(n-1);
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        for (int i=1; i<=n; i++) {
            System.out.print(recursion(i) + " ");
        }
    }
}

 

재귀함수를 통해서도 피보나치 수열을 출력할 수 있지만 구한 값을 다시 구한다는 단점이 있습니다.그렇기 때문에 입력 값이 커지면 걸리는 시간이 오래 걸립니다.

풀이2- static 배열을 선언하여 구한 값을 기록하기(메모이제이션)

이번에는 메모이제이션 방식으로 피보나치 수열을 출력해보겠습니다. 메모이제이션은 말 그대로 구한 값을 배열에 기록하는 방법입니다. 그렇기 때문에 구한 값을 다시 구하려고 연산을 낭비하지 않아도 됩니다. 재귀함수의 정의 맨 처음에 값을 구한적이 있는지 검사합니다.

만약 dp[n]이 0이면 값을 구한적이 없는 것이고, 0이 아니면 값을 구한 적이 있으므로 dp[n]을 리턴하면 됩니다. 이와같이 배열을 사용하면 구한 값을 다시 계산할 필요가 없어지므로 연산이 적어지고 빠르게 값을 구할 수 있습니다.

 

package 인프런.재귀와트리와그래프.피보나치수열.배열로풀기;

import java.util.Scanner;

public class Main {
    static int[] dp;    // 메모이제이션 역할을 할 배열 선언. 인덱스는 항 순서

    public static int recursion(int n) {
        if (dp[n] != 0) return dp[n];   // 앞에서 값을 구한적이 있는지 검사

        if (n == 1) return dp[0] = 1;
        else if(n == 2) return dp[1] = 1;
        else return dp[n] = recursion(n-2) + recursion(n-1);
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        dp = new int[n+1];

        for (int i=1; i<=n; i++) {
            System.out.print(recursion(i) + " ");
        }
    }
}