[알고리즘] [java] 피보나치 수열과 메모이제이션

알고리즘을 이해하자 하자 하자 하자!

 

Table of Contents

---

Q. 문제

특정 양의 정수가 첫줄에 주어진다.
해당 항까지의 피보나치 수열을 출력하시오.

예) 6  출력값 ) 1 1 2 3 5 8

 

A. 구현

1. 재귀를 활용해 단순 (naive) 한 방법으로 푸는 경우

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

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    Main T = new Main();
    try {
        int n = Integer.parseInt(br.readLine());
        for (int i = 1; i < n; i++) bw.write(fibo(i) +" ");
    } catch (IOException e) {
        throw new IOException(e);
    }
    bw.close();
    br.close();
}

 

• `BufferedReader`, `BufferedWriter`를 활용한 입출력 구현
• 순서대로 피보나치를 구하는 `1 ~ n` 까지의 피보나치 함수를 호출할 때 재귀함수 호출 순서
  1. `fibo(1)` : fibo(1) 호출
  2. `fibo(2)` : fibo(2) 호출
  3. `fibo(3)` : fibo(1), fibo(2) 호출
  4. `fibo(4)` : fibo(3)(fibo(1), fibo(2)), fibo(2) 호출
  5.  ` · · ·  `
  6. `fibo(n)` : fibo 함수를 `n + n-1 + n-2 · · · 2 + 1` 번 호출 = 총 `n(n+1)/2` 번 호출
• `1 ~ n` 까지의 피보나치 함수 호출 수 : 총 `n² * (n + 1)/2` , `O(n) = n³`

 

• 문제점
  1. method call로 인한 스택 프레임 중첩
  2. 값을 구한 함수를 중복해서 연산
     • 예 : fibo(4)에서 이미 fibo(3)은 구해져 있으나 하위 ibo(1), fibo(2)를 다시 호출하며 fibo(3)을 구함
• 해결방법 : 기존에 미리 계산한 값은 저장해놓고 호출 시 해당 값을 불러옵니다.

 

2. 재귀 + 메모이제이션(memoization, 캐싱) 을 통해 개선한 코드

메모이제이션 : 중복 계산을 방지할 수 있게 하는 기법입니다.

동일한 계산을 반복해야 할 경우 한번 계산된 결과를 메모리에 저장해두었다가 꺼내 쓰는 방식으로,
메모리라는 공간 비용을 투입해 시간 비용을 줄이는 방식입니다.

static int[] arr; // 피보나치 함수의 결과값 저장

public int fibo(int n) {
  if (arr[n] > 0) return arr[n]; // memozation : 해당 값이 0이 아니면 계산해놓은 저장값으로 대체
  if (n == 1) return arr[n] = 1;
  else if (n == 2) return arr[n] = 1;
  else return arr[n] = fibo(n-2) + fibo(n-1);
}

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    Main T = new Main();
    try {
        int n = Integer.parseInt(br.readLine());
        arr = new int[n+1];
        T.fibo(n);
        
        for (int i = 1; i < n; i++) bw.write(arr[i] +" ");
    } catch (IOException e) {
        throw new IOException(e);
    }
    bw.close();
    br.close();
}

• 개선 방법
  1. 피보나치 함수의 값을 인덱스별로 배열에 저장
  2. 피보나치 함수 호출 시 해당 배열의 인덱스에 저장되어 있는 함수 계산 값을 호출
     • 예 : fibo(4)에서 fibo(3) 호출 시 기존에 계산, 저장되어 있는 arr[3] 값으로 대체

 

3. 결론

• 그럼에도 불구하고 재귀보다는 for / while 문으로 구현하는 방식이 성능이 좋습니다.
  • 재귀라는 특성상 메소드 호출이 부르는 성능 저하를 생각해봐야
• 재귀를 쓸꺼면 메모이제이션을 십분 백분 천분 활용합시다.