[알고리즘] 07.Recursive, Tree, Graph (DFS, BFS) / 04. 피보나치 재귀(메모이제이션)

피보나치

설명

피보나치를 재귀 용법으로 풀어보기

입력

출력

예시 입력 1

예시 출력 1

느낀점

피보나치 수열을 배열, for문, 재귀, 다양하게 풀어 볼 수 있다.
어떤 식으로 문제가 출제도 풀 수 있도록!

코드

import java.util.Scanner;

//방법1
public class Main {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int n = 10;
		for(int i=1; i<n; i++) {
			System.out.print(T.recursive(i) + " ");
		}
	}

	public int recursive(int n) {
		if(n == 1){
			return 1;
		}else if(n == 2) {
			return 2;
		}else {
			return recursive(n-2) + recursive(n-1);
		}
	}
}

//방법2 .. static을 이용해서 방법1보다 조금 속도 개선
import java.util.Scanner;

public class Main {
	static int[] fibo;

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int n = 10;
		fibo = new int[n+1];
		T.recursive(n);
		for(int i=1; i<n; i++) {
			System.out.print(fibo[i] + " ");
		}
	}

	public int recursive(int n) {
		if(n == 1){
			return fibo[n] = 1;
		}else if(n == 2) {
			return fibo[n] = 2;
		}else {
			return fibo[n] = recursive(n-2) + recursive(n-1);
		}
	}
}

//방법3 : 메모이제이션
import java.util.Scanner;
public class Main {
	static int[] fibo;
...

	public int recursive(int n) {
		if(fibo[n] > 0) return fibo[n];
		if(n == 1){
			return fibo[n] = 1;
		}else if(n == 2) {
			return fibo[n] = 2;
		}else {
			return fibo[n] = recursive(n-2) + recursive(n-1);
		}
	}
}