Java 피보나치(Fibonacci) 수열 제대로 풀기

오늘은 알고리즘 단골 문제인 피보나치 수열 풀이법에 대해 알아보려고 합니다. 피보나치 수열은 면접 현장에서 손 코딩으로 배열 또는 재귀 함수로 풀어보고 성능을 물어보기도 하기 때문에, 이번 포스팅을 통해 정확히 알고 가시면 좋을 것 같습니다😄

 

피보나치

 

피보나치(Fibonacci)📘

수학에서 피보나치 수는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열을 일컫습니다. 예시로 5는 1 1 2 3 5로 표현이 되겠네요. 이런 피보나치 수열을 푸는 방법은 앞서 말씀드린 것처럼 배열로 푸는 방식과 재귀 함수로 푸는 방식으로 나뉩니다.

 

사실 배열로 푸는 방식이 성능면에서도 좋고 풀이 방법도 간단하지만, 재귀함수로 풀어보라는 회사도 많기 때문에 두 가지 풀이 방법을 모두 숙지하시는 게 좋습니다.

 

성능면에서 재귀 함수는 스택 프레임을 사용하기 때문에 상당히 메모리 비용이 큽니다. 혹여나 스택 프레임(Stack Frame)을 모르신다면 링크를 클릭하셔서 꼭 숙지하시길 바랍니다😄

 

📌 간단 설명 : 스택 프레임은 값을 계속 저장하고 체크하는 방식입니다.

 

그럼 먼저 간단한 배열 방식부터 풀어볼까요?

 

배열(Array) 방식📒

public class FibonacciArray {
    public static void main(String[] args) {
        int n = 10;
        int[] result = new int[n];

        result[0] = 1;
        result[1] = 1;

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

        for(int x : result) {
            System.out.print(x + " ");
        }
    }
}
// 출력 값 : 1 1 2 3 5 8 13 21 34 55

간단하죠? 배열 0번째 인덱스와 1번째 인덱스에 1로 값을 세팅하고, 입력받은 n의 길이만큼 반복문을 돌면서 해당 인덱스에 이전 값과 2번째 이전 값을 더해서 세팅해주면 끝이 납니다.

 

여기서 한 가지 주의할 점은 피보나치 수는 첫 번째와 두 번째의 수가 1로 고정되기 때문에 반복문을 배열의 2번 인덱스부터 시작해야 하는 점입니다. 

 

📌 배열은 0부터 시작하는 점 잊지 않으셨죠!?

 

재귀(Recursive) 방식📗

재귀란 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻합니다. 코드상에서는 사실 반복문과 큰 차이는 없습니다. 차이점으로는 재귀 함수는 함수를 반복적으로 호출하기 때문에 스택 메모리를 사용하고 반복문은 메모리 힙을 사용합니다.

public class Fibonacci {
    public int DFS(int n) {
        if(n==1) {
            return 1;
        } else if (n ==2) {
            return 1;
        } else {
            return DFS(n-2) + DFS(n-1);
        }
    }
    public static void main(String[] args) {
        Fibonacci T = new Fibonacci();
        int n = 40;
        for(int i = 1; i <= n; ++i) {
            System.out.print(T.DFS(i) + " ");
        }
    }
}

사실 이전 포스팅 재귀 함수를 보셨다면 코드에서 이해하기 힘든 부분은 크게 없으실 것 같아요. DFS 함수는 해당 숫자가 인자 값으로 들어왔을 때, 즉 3이 들어왔다고 가정하면 이전 값 1과 두 번째 이전 값 1이 더해져서 2를 return 하게 됩니다.

 

📌 앞에서 언급한 바와 같이 1(인덱스 자리)과 2(인덱스 자리)는 1로 고정시키는 것이 피보나치 수열입니다😊

 

결국엔 반복문이 1부터 시작해서 리턴 받은 값들을 출력하면 아래 사진과 같이 출력이 되겠네요!

하지만 이렇게만 답을 제출하면 백 점짜리 정답은 아닙니다. 결과값은 기대한 대로 피보나치 수열로 나왔지만, 실제로 실행을 시켰을 때 굉장히 느린 것을 확인하실 수 있으실 거예요. 그 이유는 바로 스택 프레임을 사용했기 때문입니다. 사실 글로만 보면 이해하기 힘들 것 같아서 아래 이미지를 통해 다시 한번 쉽게 설명해 볼게요😀

 

다이어그램

 

만약 5라는 인자 값이 들어왔다고 가정하고 반복문이 돌아가게 됩니다. 1과 2는 코드 상 1로 return 하기 때문에 System.out.print()를 통해 출력하고 넘어가게 되고, 3부터 재귀가 시작됩니다.

 

DFS(3)은 DFS(3-2 = 1) + DFS(3-1 = 2)로 진행됩니다. 즉, 1+1 = 2가 된다는 뜻이죠. 그 이후로, 반복문을 통해 4라는 숫자가 들어옵니다. 

 

DFS(4)은 DFS(4-2 = 2) + DFS(4-1 = 3)로 진행됩니다. 여기서 DFS(4-1 = 3)은 방금 위에서 구한 DFS(3) 방식으로 똑같이 구하게 됩니다. 즉 위 다이어그램처럼 빨간색 부분들이 중복적으로 계산이 이루어지고 있다는 뜻입니다.

 

지금은 5라는 작은 숫자지만 만약 40이라는 숫자가 들어왔다면 빨간색 원이 얼마나 많아질까요? 

 

이런 부분이 스택 프레임을 사용해서 성능적으로 안 좋은 이유입니다. 또한, 40이라는 수를 피보나치 수열로 했을 때 15초라는 시간이 걸리도록 말이죠😅 (배열은 1초도 안 걸립니다) 

 

그렇다면 재귀 함수를 사용하는 피보나치 수열을 더 개선시킬 방법은 없을까요? 정답은 아닙니다! 메모이제이션을 사용하면 문제를 해결할 수 있습니다. 아래서 확인해볼게요 :)

 

메모이제이션📙

메모이제이션은 계산하면서 이미 계산한 값은 메모해 둔 곳에서 가져와서 계산하자는 방식입니다. 즉 이미 구해둔 값은 구해둔 값으로 사용하자라는 얘기입니다. 코드를 살펴볼까요?

public class Fibonacci {
    static int[] fibo;
    public int DFS(int n) {
        if(fibo[n] > 0) {
            return fibo[n];
        } //line 6
       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);
        }
    }
    public static void main(String[] args) {
        Fibonacci T = new Fibonacci();
        int n = 40;
        fibo = new int[n+1];
        T.DFS(n);
        for(int i = 1; i <= n; ++i) {
            System.out.print(fibo[i] + " ");
        }
    }
}

이전과 달리 static으로 메모해 둘 배열을 fibo로 지정하였습니다. 이후에, main에서 fibo를 int형 배열로 n+1 만큼 선언합니다. 재귀 함수의 경우 배열의 순서와 입력값의 숫자를 동일하게 넣기 때문입니다.

 

그리고 T.DFS() 함수에 인자 값 40을 넣고 실행시킵니다. DFS() 함수에 40이 들어왔습니다. 아직 fibo 배열에는 아무 값도 없기 때문에 line 6번째 줄은 넘어가겠네요. 이후로 40은 1,2가 아니기 때문에 else문을 타게 됩니다.

 

else 문은 fibo[40] = DFS(40 - 2 = 38) + DFS(40 - 1 = 39)의 값이 들어갑니다. 그러면 fibo[40]의 값은 아직 모른 채 스택에 쌓이게 됩니다. 이후에 DFS(38)과 DFS(39) 함수가 실행됩니다. 

 

DFS(39) 또한 fibo에 아직 값이 없고 1,2가 아니기 때문에 else문을 타게 됩니다. fibo[39] = DFS(39 - 2 =37) + DFS(39 - 1 =38)의 형식이 될 것입니다.

 

이렇게 반복적으로 계속해서 내려갈 것입니다. 다이어그램 꼭대기에서 DFS(1)까지 쭉 트리 형식으로 구성이 되겠네요. 그리고 마침내 1,2에 도달했을 때 fibo[1] = 1, fibo[2] = 2가 return 되면서 이후로 잠시 홀딩되었던 fibo[3]의 결과값부터 fibo[40]까지의 결과값이 순차적으로 계산이 됩니다. 아래 그림처럼 말이죠!

 

stack

 

결과값은 동일하게 나오지만 시간 차이는 분명하게 납니다. 이전에는 피보나치 수열 전체가 print 되기까지 15초라는 시간이 걸렸지만, 메모이제이션을 사용해서 1초 만에 결과값을 도출할 수 있었습니다.

 

---

👨‍👩‍👦‍👦 오픈채팅방 운영

취업을 준비하는 예비 개발자분들을 위한 질문&답변할 수 있는 공간을 만들었습니다. 취업과 이직을 하기 위해서 어떤 걸 중점적으로 준비해야 하는지부터 포트폴리오&이력서 작성법 등 다양한 질문들을 받고 답변을 드립니다. 참여하셔서 다양한 정보 얻고 가시면 좋을 것 같네요😁

 

참여코드 : 456456

https://open.kakao.com/o/gVHZP8dg

비전공 개발자 취업 준비방(질문&답변)

 

---

👨‍💻 전자책 출간

아울러 제가  🌟비전공자에서 2년만에 보안 전문 중견기업으로 이직 한 방법들을 정리한 전자책을 출간 하게 되었습니다. 어떤 걸 공부해야 하는지, 이직을 위해서 무엇을 준비해야 하는지, 제가 받았던 기술 면접 리스트 등 다양한 목차로 구성되어 있습니다. 또한, 구매 시 1:1 채팅을 이용하여 포트폴리오 첨삭을 도와드리고 있습니다. 🐕전자책으로 얻은 모든 수익은 유기견 센터 '팅*벨 입양센터'에 후원될 예정입니다. 관심 있으신 분들은 아래 링크를 참고해주세요😁

https://kmong.com/gig/480954

비전공개발자 2년만에 중견기업 들어간 방법 | 14000원부터 시작 가능한 총 평점 0점의 전자책, 취

---

 

마치며

사실 재귀 함수와 스택 프레임을 구조를 잘 모른다면 한 번에 이해하기는 어려울 수도 있을 것 같아요. 혹여나 궁금한 점이 있으시거나 잘못된 점이 있으시면 댓글 남겨주시면 감사하겠습니다😄