피보나치 수열 효율적으로 풀어보기 (Java 알고리즘)

피보나치 수열

피보나치 수열을 이전 항 2개를 더한값이 현재 항이 되는 수열이다.

• 예를들어, A(n) = A(n-1) + A(n-2) (단, A(1) = 1, A(2) = 1 이다) 를 만족하는 수열

2 3 5 8 13 21 34 55 89 144 233 ...

 

프로그래밍

피보나치 수열을 풀어보는 방법은 여러방법이 있다.

그 중 아래 3가지 방법으로 풀어본다.

1. 배열로 풀어보는 방법
2. 배열없이 풀어보는 방법
3. 재귀함수를 이용하는 방법

 

1. 배열로 풀어보는 방법

• STEP 1. int 배열을 선언한다.
• STEP 2. A(1) = 1, A(2) = 1을 미리 초기화한다.
• STEP 3. 반복문을 이용하여 A(n) = A(n-1) + A(n-2)를 이용하여 계속해서 더한다.

public static void main(String[] args) {
        // STEP 1. 결과값을 담을 배열 선언
        final int[] arr = new int[100];

        // STEP 2. 첫번째 항과 두번쨰 항 미리 선언
        arr[1] = 1;
        arr[2] = 1;
        
        // STEP 3. 반복문을 이용하여, 계속해서 더해 나간다.
        for (int i = 3; i < 100; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
            System.out.print(arr[i] + " ");
        }
}

 

2. 배열없이 풀어보는 방법

변수 2개를 이용하여 문제를 푼다.

• STEP 1. '전 전 항'과 '이전 항'을 담을 변수 2개를 선언한다. (초기값은 A(1)=1, A(2)=1에 따라 1로 초기화 함)
• STEP 2. 반복문을 이용하여 계속 더해 나간다.
• STEP 3. 더한 뒤에 '전 전 항'과 '이전 항'을 갱신해준다.

public static void main(String[] args) {
        int prevPrevNum = 1; // 전 전 항 (n-2)
        int prevNum = 1; // 이전 항 (n-1)

        for (int i = 3; i < 100; i++) {
            int curNum = prevPrevNum + prevNum; // 현재 항 (n)
            System.out.print(curNum + " ");

            prevPrevNum = prevNum;
            prevNum = curNum;
        }
}

 

3. 재귀적으로 반복하여 푸는 방법

재귀(Recursive)적으로 풀어본다. (효율적으로 풀기 위해 Memoization을 사용)

• STEP 1. 계산된 결과값을 담을 'memo' 배열을 생성한다.
• STEP 2. 재귀적으로 수행할 fibo()메소드를 생성한다.
• STEP 3. 처음 계산하는 경우와 이미 계산한 경우로 나눠진다.
  
  • 이미 계산한적이 있어서 memo 배열에 값이 있는 경우, 그대로 반환한다. 
  • 처음 계산하는 경우, 계산한 뒤 memo 배열에 저장하고 반환한다.

public class Fibonacci {

    // 계산된 결과 값을 담을 배열
    private static int[] memo = new int[100];

    public static void main(String[] args) {
        fibo(99);

        for (int n : memo) {
            System.out.print(n + " ");
        }
    }

    private static int fibo(int k) {
        if (memo[k] != 0) {
            // 이미 계산한 값
        } else {
            // 처음 계산되는 값
            if (k <= 2) {
                // 1번 항과 2번 항은 1로 초기화
                memo[k] = 1;
            } else {
                // 3번째 항 부터는 계산
                memo[k] = fibo(k - 1) + fibo(k - 2);
            }
        }
        return memo[k];
    }

}