피보나치 수열

면접 중 손코딩 단골 피보나치 수열

피보나치 수열은 

a1=1,  a2=1,  an+2=an+1+an  (n=1, 2, 3, ⋯) 라는 규칙을 갖는다.

1 1 2 3 5 8 13 21 34 55 …

이 수열을 재귀, 메모이제이션, 반복문으로 나타내보자

피보나치 수열을 푸는 방법 1 - 재귀

public static void main(String[] args) {
		// TODO Auto-generated method stub
		int input = 8;
		for (int i = 1; i <= input; i++) {
			System.out.println(fibo(i));
		}
}
public static int fibo(int n) {
		if (n <=2) {
			return 1;
		}
		else
			return fibo(n - 1) + fibo(n - 2);
	}
}

근데 이건.. 시간 복잡도가 O(2^N) .. 느려 느려

피보나치 수열을 푸는 방법 2 - 메모이제이션 (memoization)

static int[] f;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int input = sc.nextInt();
		f = new int[input+1];
		
		Arrays.fill(f, 0);
		System.out.println(fibo(input));
	}
	public static int fibo(int n){
		if (n <= 2)
			return 1;
		else if (f[n] != 0) // 이미 계산이 되어 배열에 가지고 있음
			return f[n];
		else
			return f[n] = fibo(n - 1) + fibo(n - 2);
	}

이건 시간 복잡도가 O(N) 이라서 훨씬 빠르다.

피보나치 수열을 푸는 방법 3 - 반복문

	public static void main(String[] args) {
		int input = 8;
		f = new int[input + 1];
		f[0] = 0;
		f[1] = 1;
		for (int i = 2; i <= input; i++) {
			f[i] = f[i - 1] + f[i - 2];
		}
		
		System.out.println(f[input]);
	}

얘도 시간 복잡도가 O(N)  이다!

이제 이 기본 코드에서 조건을 더해서 응용으로 문제가 나오겠지?