19. [다이나믹]피보나치 수열

[문제]

아래와 같은 규칙성을 갖는 수열이 있을 때(피보나치 수열), 임의로 주어지는 n번째 수열 값을 구하시오. (위치 시작은 0)

0 1 1 2 3 5 8 13 ... (n-2) (n-1) n

n = (n-2) + (n-1)

입력: 5

출력: 5 

입력: 6

출력: 8

[풀이]

피보나치 수열의 규칙성은 다음과 같다.

  1) f0) = 0

  2) f(n) = f(n-2) + f(n-1)

재귀 호출로 코딩하면 다음과 같이 간단히 되겠다. 

그러나, 이렇게 하면 작은 수에 대해서는 괜찮으나, 큰 수에 대해서는 동작 안할수도 있고, 무엇보다 실행시간이 O(n²)으로, 굉장히 많이 걸린다.

         private long fibonacci_recursion(int n) {

                  if (n == 0)

                           return 0;

                  if (n <= 1)

                           return 1;

                  return fibonacci_recursion(n - 2) + fibonacci_recursion(n - 1);

         }

재귀호출보다는, n-2와 n-1번째 값들을 테이블로 저장해뒀다가 사용하는 것이 더 효율적일 것이다.

이렇게 짜면 아래와 같다.

          private long fibonacci_table(int n) {

                  if (n == 0)

                           return 0;

                  if (n <= 2)

                           return 1;

 

                  long[] table = new long[(int) n + 1];

                  table[0] = 0;

                  table[1] = 1;

                  table[2] = 1;

 

                  for (int i = 3; i <= n; i++) {

                           table[i] = table[i - 2] + table[i - 1];

                  }

 

                  return table[n];

         }

근데, 좀 더 생각해보면, 계산되는 모든 값을 테이블에 저장해두지 않아도 될 것이다. 즉, 바로전과 전전 값만 저장해두면 될것이다. 그렇게하면 메모리를 배열로 크게 잡을 필요가 없을 것임.

         private long fibonacci_variable(int n) {

                  if (n == 0)

                           return 0;

                  if (n <= 2)

                           return 1;

 

                  long a = 1, b = 1;

                  long c = 0;

                  for (int i = 3; i <= n; i++) {

                           c = a + b;

                           a = b;

                           b = c;

                  }

 

                  return c;

         }

* 정리

피보나치 수열에 대해 3가지 구현방법을 봤다. 

처음 fibonacci_recursion은, 수열의 원리 그대로 구현한 것인데, 실행속도가 너무 느리고, --> O(n²)

두번째 fibonacci_table은, 다이나믹 프로그래밍을 한 건데, 속도는 빠르나, 메모리 사용이 좀 많다. --> O(n)

세번째 fibonacci_variable은, 속도도 빠르고, 메모리 사용도 최소로 한 버전이다. --> O(n)

 ==> O(log n)에 Fibonacci값을 계산할 수도 있다. Divide And Conquer 방식을 사용하면.

이 세가지 코드가 다 들어 있는 코드는 아래 소스코드부분에 있고, 3가지 버전에 대해서 실행속도를 비교해보면,

다음과 같다.

 

fibonacci_recursion: 1095ms

fibonacci_table: 1ms

fibonacci_variable: 1ms

[소스코드]

package dynamic;

 

public class Fibonacci {

         public static void main(String[] args) {

                  Fibonacci fibo = new Fibonacci();

                  fibo.test();

         }

        

         public Fibonacci() {      

         }

 

         private void test() {

                  long value;

                  int len;

                  long start, end;

                  long t1,t2,t3;

                 

                  len = 40;

 

                  // 1. Recursion

                  start = System.currentTimeMillis();

                  for (int n = 0; n < len; n++) {

                           value = fibonacci_recursion(n);

                           System.out.println("finobacci(" + n + ")=" + value);

                  }

                  end = System.currentTimeMillis();

                  t1 = end-start;           

 

                  // 2. Dynamic_Table

                  start = System.currentTimeMillis();

                  for (int n = 0; n < len; n++) {

                           value = fibonacci_table(n);

                           System.out.println("finobacci(" + n + ")=" + value);

                  }

                  end = System.currentTimeMillis();

                  t2 = end-start;

                 

                  //3. Dynamic_Variable

                  start = System.currentTimeMillis();

                  for (int n = 0; n < len; n++) {

                           value = fibonacci_variable(n);

                           System.out.println("finobacci(" + n + ")=" + value);

                  }

                  end = System.currentTimeMillis();

                  t3 = end-start;

                 

                  //print

                  System.out.println("fibonacci_recursion: "+t1+"ms");

                  System.out.println("fibonacci_table: "+t2+"ms");

                  System.out.println("fibonacci_variable: "+t3+"ms");

 

         }

 

         private long fibonacci_recursion(int n) {

                  if (n == 0)

                           return 0;

                  if (n <= 1)

                           return 1;

                  return fibonacci_recursion(n - 2) + fibonacci_recursion(n - 1);

         }

 

         private long fibonacci_table(int n) {

                  if (n == 0)

                           return 0;

                  if (n <= 2)

                           return 1;

 

                  long[] table = new long[(int) n + 1];

                  table[0] = 0;

                  table[1] = 1;

                  table[2] = 1;

 

                  for (int i = 3; i <= n; i++) {

                           table[i] = table[i - 2] + table[i - 1];

                  }

 

                  return table[n];

         }

 

         private long fibonacci_variable(int n) {

                  if (n == 0)

                           return 0;

                  if (n <= 2)

                           return 1;

 

                  long a = 1, b = 1;

                  long c = 0;

                  for (int i = 3; i <= n; i++) {

                           c = a + b;

                           a = b;

                           b = c;

                  }

 

                  return c;

         }

 

        

 

}

 

 

-끝-