알고리즘 - 피보나치 구현 방식

알고리즘 - 피보나치 구현 방식

---

피보나치란?

• 첫째항 및 둘째항은 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다.

• 0번째 항부터 시작할 경우 점화식으로 나타내면 다음과 같다
  • f(n) = f(n - 1) + f(n - 2) (이때, n > 1)

 

피보나치 - 재귀함수로 구현 with JAVA

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

• fibo(n - 1) + fibo(n - 2)를 진행할 때 같은 수를 중복적으로 호출하는 현상이 발생한다. 
• 시간복잡도는 O(2^N)이 된다.

재귀함수로 구현한 피보나치의 함수 호출

 

 

피보나치 - 반복문으로 구현 with JAVA (Dynamic Programming)

int[] fibo = new int[n + 1];

fibo[0] = 0;
fibo[1] = 1;
for(int i = 2; i <= n; i++) {
	fibo[i] = fibo[i - 1] + fibo[i - 2];
}
return fibo[n];

• 동적 계획법이라고도 하며, bottom-up 방식으로 n번만큼 반복하게 된다. 이전에 계산한 값을 가지고 계산을 축적해 나가므로 이미 계산한 값을 다시 계산하는 과정이 발생하지 않는다.
• 시간복잡도는 O(n)이 된다.

 

피보나치 - 재귀함수와 메모이제이션으로 구현 with JAVA

public static int fibo(int n, int[] memo) {
    if(memo[n] > 0) return memo[n];
    if(n <= 1) return n;
    
    return memo[n] = fibo(n - 1, memo) + fibo(n - 2, memo);
}

• 재귀함수 방법에서 중복된 함수가 여러번 호출되는 것을 막기 위해 이전에 계산한 값을 저장한다. 현재 구하려는 값이 이미 계산된 값이라면 그 값을 반환하여 중복 계산을 막는다.
• 메모이제이션은 동적 계획법의 일종으로 보기도 하며, top-down 방식으로 실제로 필요한 subproblem만을 풀 수 있다.
• 시간복잡도는 O(n)이다.

 

 

reference

ko.wikipedia.org/wiki/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98_%EC%88%98

velog.io/@minjae-mj/Memoization-%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98-feat.-%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98-%EC%88%98%EC%97%B4