Algorithmlevel1

Algorithm Dynamic Fibonacci

,

Fibonacci

Fibonacci를 구현하다보면 재귀를 사용하는 경우가 흔한 경우이다 하지만 재귀를 사용하면 중복되는 코드가 많이 발생하다보니 코드 수행시간이 길어진다.
이를 해결하기 위한 방법이 Dynamic Fibonacci이다.

재귀 Fibonacci

1
2
3
4
5
6
7
8
9
10
11
12
13

public int fibonacci(int num) {
	int first = 0;
	int second = 1;
	int sum = 0;
	
	if(num <=2) {
		sum = first + second;
	}else {
		sum = fibonacci(num-1) + fibo(num-2);
	}
	return sum;
}

Dynamic Fibonacci

Dynamic Fibonacci는 값을 지속적으로 저장하면서 코드를 실행한다 그러기 때문에 속도가 재귀보다 우수하다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class intfibonacci {
	
	// long type을 사용하는 것이 중요하다.
	public long fibonacci(int num) {
		int answer = 0;
		int[] arr = new int[num + 1];

		arr[0] = 0;
		arr[1] = 1;
		if (num <= 2) {
			answer = 1;
		} else {
			for (int i = 2; i <= num; i++) {
				arr[i] = arr[i-1] + arr[i-2];
			}
		}
		answer = arr[num];
		return answer;
	}

	public static void main(String[] args) {
		intfibonacci c = new intfibonacci();
		for (int i = 2; i <= 70; i++) {
			System.out.println(i + " " + c.fibonacci(i));
		}

	}
}

하지만 여기서 또다른 issue사항이 발생한다 바로 int로 값을 표현하였기 때문에 표현할 수 있는 문자열의 한계가 존재한다 그래서 47번째 fibonacci부터 -값이 저장이된다.

fibo

값을 해결하기위하여 long type을 사용합니다.

  • int 표현범위 -2147483648 ~ 2147483647
  • long 표현범위 -9223372036854775808 ~ 9223372036854775807
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class fiboexample {
	
	// long type을 사용하는 것이 중요하다.
	public long fibonacci(int num) {
		long answer = 0;
		long[] arr = new long[num + 1];

		arr[0] = 0;
		arr[1] = 1;
		if (num <= 2) {
			answer = 1;
		} else {
			for (int i = 2; i <= num; i++) {
				arr[i] = arr[i-1] + arr[i-2];
			}
		}
		answer = arr[num];
		return answer;
	}

	public static void main(String[] args) {
		fiboexample c = new fiboexample();
		for (int i = 2; i <= 65; i++) {
			System.out.println(i + " " + c.fibonacci(i));
		}

	}
}
Share