[Algorithm] 피보나치 수열 (반복문, DFS)

피보나치 수열을 구현하는데 두가지정도의 알고리즘이 대표적으로 존재한다.

반복문 + 배열로 구현

먼저, 대표적으로 배열 + 반복문으로 구현하는 방법은 아래와 같다.

package Array;

import java.util.*;

public class Fibonacci {

    public static int[] fib(int n) {
        int[] arr = new int[n];

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[] answer = fib(n);

        for (int i : answer) {
            System.out.print(i + " ");
        }
    }

}

배열의 인덱스가 0이나 1일 때는 원소의 값을 1로 집어 넣는 복잡도가 O(1)이고, 인덱스가 0 또는 1이 아닐 때 원소값을 삽입하는 복잡도는 대략 O(n) 정도이다. 즉 배열과 반복문으로 풀면 복잡도는 O(n) 정도이다.

 

---

DFS 로 구현

기본적으로 DFS는 메서드를 재귀적으로 호출한다. 구현은 아래와 같다.(편의상 마지막 값만 출력)

import java.util.*;

public class DFSFibonacci {

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        System.out.println(fib(n));
    }
}

로직은 배열로 작성했을때와 같다. 다만 값이 0또는 1이 아닐때는 메서드를 재귀적으로 호출하여 값을 구하는 점에서 차이점이 존재한다.

시간복잡도를 계산해보자.

fib(n) 메서드는 반복적으로 fib(n-1) 와 fib(n-2)를 호출한다. -> 즉 메서드를 호출할수록 호출이 분기를 생성해낸다.

이를 재귀적으로 분기한다고 하는데, 위 예제에서는 대략 2^n에 비례한다. -> 즉 복잡도는 O(2^n) 에 비례한다.

 

현재처럼 간단한 코드에서는 일단 배열 + 반복문 조합으로 푼 방식이 더 효율적이다.

다만 DFS을 최적화 하는 방법중에 메모이제이션이라는 방법이 있는데, 이는 추후에 써보겠다!

 

오늘은 그냥 간단한 구현이 목적이었다.