피보나치 수열(배열 vs 재귀 비교)

피보나치 수열은 알고리즘 및 자료구조를 공부하는데 있어서 여러 유형에서 기본으로 나오게된다.

아래 두가지 예시를 가지고 비교해보며 설명하고자 한다.

물론 기억력의 한계가 있다보니 기록해두려는 목적 또한 있다는 점도 포함!

---

먼저 배열을 이용한 피보나치 예시이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

// 피보나치 수열
public class infArray4 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        for(int x : Solution(N)){
            System.out.print(x + " ");
        }
    }
    public static int[] Solution(int N){
        int [] answer = new int[N];
        answer[0] = 1;
        answer[1] = 1;
        for(int i=2; i<N; i++){
            answer[i] = answer[i-2] + answer[i-1];
        }
        return answer;
    }
}

 

다음은 재귀를 이용한 피보나치 함수 구하기 예시이다.

// 재귀로 피보나치 수열 풀기
public class infRecursive4 {
    static int[] fibo;
    /*
        결과적으로 피보나치 수열을 돌면서
        값을 구하는 과정에서 반복되는 연산이 수행되는데
        결과적으로 내가 구하고자 하는 리턴값인 DFS(10)만 구하면 된다.
        그래서 반복되는 연산을 기억해놓기 위해서 배열에다가 담아두고 다시 수행되지 않게 기억해놓는다.
     */
    public static void main(String[] args) {
        int n = 45;
        fibo = new int[n+1]; // 0번 인덱스가 필요없고 1~10번 인덱스로 사용하기위해
        DFS(n);
        for(int i=1; i<=n; i++) System.out.print(fibo[i] + " ");
    }
    public static int DFS(int n){
        /*
            메모이제이션을 활용해서 시간복잡도를 확 줄여버린다!!
            배열을 선언하면 기본적으로 0으로 초기화 되는데
            아래와 같이 피보나치를 돌면서 이미 연산한 값이 배열안에 있는지 확인해서 있다면 그값을 리턴해줌으로써 시간을 확 줄인다.
            이게 바로 메모이제이션!
         */
        if(fibo[n] > 0) return fibo[n];
        if(n == 1) return fibo[n] = 1;
        else if(n == 2) return fibo[n] = 1;
        else return fibo[n] = DFS(n-2) + DFS(n-1);
    }
}

---

위의 두개의 예시를 보고 피보나치를 어느 것으로 푸는 것이 더 효율적인지 여부를 판단해보면 (배열 vs 재귀)

• 결과로 우선 얘기하자면 배열을 이용하여 for문을 통해 푸는 것이 성능적인 면에서 압도적으로 좋다.
• 위의 재귀방식에서는 스택프레임이 계속 돌아가기 때문에 메모리적으로나 성능적으로나 안 좋다.
• 하지만 위 두가지 방식에 대해서 다 알아두면 좋다. (코딩 인터뷰에서 자주 물어보는 질문이다)