[PS] 인프런 강의 - Recursive 4. 피보나치 수열

 

문제

1) 피보나키 수열을 출력한다. 피보나치 수열이란 앞의 2개의 수를 합하여 다음 숫자가 되는 수열이다.
2) 입력은 피보나치 수열의 총 항의 수 이다. 만약 7이 입력되면 1 1 2 3 5 8 13을 출력하면 된다.

 

▣ 입력설명
첫 줄에 총 항수 N(3<=N<=45)이 입력된다.

 

▣ 출력설명
첫 줄에 피보나치 수열을 출력합니다.

 

▣ 입력예제 1
10

 

▣ 출력예제 1
1 1 2 3 5 8 13 21 34 55

풀이

배열- for문, 재귀 등 다양한 방법으로 풀어보고 어떤게 성능이 좋냐고 많이 묻는다고 한다

당연히 for문이 성능이 좋다. 재귀는 스택 프레임(매개변수,지역변수, 복귀주소 등의 정보 저장)이 막 돌아가니까..

코드

재귀로 풀기

 

1. 제일 비효율적

import java.util.Scanner;

public class Main {

	public static int DFS(int n) {
		if(n==1) return 1;
		else if(n==2) return 1;
		else return DFS(n-2) + DFS(n-1);
	}
	
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(); // 3~45, 총 항의 수
        
        //피보나치 수열(앞의 2개의 수를 합하여 다음 숫자)
        for(int i=1; i<=n; i++) System.out.print(DFS(i) + " ");
    }
}

 

2. 1에서 조금 나아진것 -> 배열 사용해서 루트 한 번만 호출

import java.util.Scanner;

public class Main {

	static int[] fibo;
	
    //결과를 배열값에 넣어놓고 그 값을 반환
	public static int DFS(int n) {
		if(n==1) return fibo[n] = 1;
		else if(n==2) return fibo[n] = 1;
		else return fibo[n] = DFS(n-2) + DFS(n-1);
	}
	
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(); // 3~45, 총 항의 수
        
        //피보나치 수열(앞의 2개의 수를 합하여 다음 숫자)
        fibo = new int[n+1];
        DFS(n); //루트 한번만 호출
        for(int i=1; i<=n; i++) System.out.print(fibo[i] + " ");
    }
}

 

3. 2에서 발전 -> 이미 구한 값이 구해졌있으면 꺼내서 재사용(메모이제이션)

import java.util.Scanner;

public class Main {

	static int[] fibo;
	
	public static int DFS(int n) {
		//이미 값이 구해져있으면 사용(메모이제이션)
		if(fibo[n] > 0) return fibo[n];
		
		if(n==1) return fibo[n];
		else if(n==2) return fibo[n] = 1;
		else return fibo[n] = DFS(n-2) + DFS(n-1);
	}
	
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(); // 3~45, 총 항의 수
        
        //피보나치 수열(앞의 2개의 수를 합하여 다음 숫자)
        fibo = new int[n+1];
        DFS(n);
        for(int i=1; i<=n; i++) System.out.print(fibo[i] + " ");
    }
}

 

 

 for문 으로 풀기(가장 성능 좋음)

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(); // 3~45, 총 항의 수
        
        //피보나치 수열(앞의 2개의 수를 합하여 다음 숫자)
        int before = 1;
        int result = 1;
        System.out.print(before + " ");
        for(int i=1; i<n;i ++) {
        	System.out.print(result + " ");
        	int temp = result; //임시 저장
        	result = before + result;
        	before = temp;

        }
    }
}