Leetcode - 509. Fibonacci Number (Easy) + Recursion Function (재귀함수)

오늘 문제는 바로 이전 글에서 다룬 Climb Stairs와 기본적으로 같은 문제 입니다.

피보나치 수 입니다.

https://ko.wikipedia.org/wiki/피보나치_수

피보나치 수 - 위키백과, 우리 모두의 백과사전

자바로 이것을 구현 하는 방법은 여러가지가 있습니다.

이전 글에서도 몇가지 살펴 보았고 이번 글에서도 몇가지 예를 배울 계획입니다.

이전 글 https://coronasdk.tistory.com/1185

Leetcode - 70. Climbing Stairs (Easy)

그 중에 하나가 Recursion Function 인데요. 오늘은 이 방법을 이해해 보고 그 다음 예들을 간단히 살펴 보겠습니다.

피보나치 수에 대한 정의는 아래와 같습니다.

피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다.

공식은 F(n) = F(n-1) + F(n-2) 입니다.

 

코드는 아래와 같습니다.

 

class Solution {
    public int fib(int n) {
        if(n<=1) return n;
        return fib(n-1) + fib(n-2);
    }
}

 

여기서 Recursion Function이 사용 됩니다.

 

return fib(n-1) + fib(n-2) 는 아래와 같이 작동합니다.

 

 

 

자 그럼 이 Recursion Function을 이용한 코드를 보겠습니다.

 

class Solution {
    public int fib(int n) {
        if(n<=1) return n;
        return fib(n-1) + fib(n-2);
    }
}

 

위 그림을 이해했다면 이 코드는 쉽게 이해 할 수 있을 겁니다.

 

이제 다른 방법을 알아 볼까요?

 

class Solution {
    public int fib(int N) {
        if (N <= 1) {
            return N;
        }
                  
        int[] cache = new int[N + 1];
        cache[1] = 1;
        for (int i = 2; i <= N; i++) {
            cache[i] = cache[i - 1] + cache[i - 2];
        }
    
        return cache[N];
    }
}

 

이것은 피보나치 식을 재귀 함수를 이용하지 않고 for 루프를 이용해서 코드를 작성한 겁니다.

방법은 같습니다.

 

Runtime은 for loop가 조금 더 빠른 것 같습니다.

 

그 이외에 아래와 같은 방법들이 있습니다.

 

class Solution {
    // Creating a hash map with 0 -> 0 and 1 -> 1 pairs
    private Map<Integer, Integer> cache = new HashMap<>(Map.of(0, 0, 1, 1));

    public int fib(int N) {
        if (cache.containsKey(N)) {
            return cache.get(N);
        }
        cache.put(N, fib(N - 1) + fib(N - 2));
        return cache.get(N);
    }
}

 

-----------

 

class Solution {
    public int fib(int N) {
        if (N <= 1) {
            return N;
        }

        int current = 0;
        int prev1 = 1;
        int prev2 = 0;

        for (int i = 2; i <= N; i++) {
            current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }
        return current;
    }
}

 

--------------------

 

class Solution {
    int fib(int N) {
        if (N <= 1) {
          return N;
        }
        int[][] A = new int[][]{{1, 1}, {1, 0}};
        matrixPower(A, N - 1);

        return A[0][0];
    }

    void matrixPower(int[][] A, int N) {
        if (N <= 1) {
          return;
        }
        matrixPower(A, N / 2);
        multiply(A, A);

        int[][] B = new int[][]{{1, 1}, {1, 0}};
        if (N % 2 != 0) {
            multiply(A, B);
        }
    }

    void multiply(int[][] A, int[][] B) {
        int x = A[0][0] * B[0][0] + A[0][1] * B[1][0];
        int y = A[0][0] * B[0][1] + A[0][1] * B[1][1];
        int z = A[1][0] * B[0][0] + A[1][1] * B[1][0];
        int w = A[1][0] * B[0][1] + A[1][1] * B[1][1];

        A[0][0] = x;
        A[0][1] = y;
        A[1][0] = z;
        A[1][1] = w;
    }
}

 

--------------

 

수학 공식을 이용하는 방법

 

class Solution {
    public int fib(int N) {
        double goldenRatio = (1 + Math.sqrt(5)) / 2;
        return (int) Math.round(Math.pow(goldenRatio, N) / Math.sqrt(5));
    }
}

 

실행결과 Runtime, Memory는 거의 모두 동일 합니다.