피보나치 함수 카운팅

문제 : https://www.acmicpc.net/problem/1003

1. 개요

재귀함수의 대명사 피보나치 함수가 구현은 쉽지만 얼마나 성능이 구린지 확인해보는 문제입니다.

2. 고난과 역경

ver 1.

fibo함수에 count만 추가하면 기능 자체는 쉽게 구현할 수 있지만

당연하게도 시간초과로 실패하고 말았습니다.

ver 2.

import java.util.*;

class Main {
    public static void main(String[] args) {
    
    	Scanner sc = new Scanner(System.in);
    	
    	int T = sc.nextInt(); 
    	int[] count = new int[2];
    	
    	while(T>0) {
    		int n = sc.nextInt();
    		fiboCount(count, n);
    		System.out.println(count[0]+" "+count[1]);
    		T--;
    		count[0] = 0; count[1] = 0;
    	}
    	
    }
    public static void fiboCount(int[] count, int n) {
    	Stack<Integer> st = new Stack<Integer>();
    	
    	int next=0;
    	st.push(n);
    	
    	while(!st.isEmpty()) {
    		next = st.pop();
    		if(next==1) count[1]++;
    		else if(next==0) count[0]++;
    		else {
    			st.push(next-1);
    			st.push(next-2);
    		}
    	}
    }
}

실제로 함수 호출은 하지 않으면서 시스템스택과 유사하게 스택에 fibo함수에 전달될 인자(n-1,  n-2 ... )를 저장하는 방식으로 구현해보았습니다.

이번에는 메모리 초과로 실패...

ver 3.

일단 입출력 방식도 바꾸고, 0부터 n까지 0,1의 호출횟수를 하나의 배열에 저장하는 방법을 시도해보았습니다.

import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
    	
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    	int T = Integer.parseInt(br.readLine()); 
    	
      	while(T>0) {
    		int n = Integer.parseInt(br.readLine());
    		int[][] count = new int[n+1][2];
    		fiboCount(count, n);
    		bw.write(count[n][0]+" "+count[n][1]+"\n");;;
    		T--;
    	}
      	bw.flush();
      	bw.close();
    	
    }
    public static void fiboCount(int[][] c, int n) {
    	
    	for(int i = 0; i < n+1; i++ ) {
    		for(int j = 0; j < 2; j++) {
    			if(i==0) c[i][j] = j^1;
    			else if(i==1) c[i][j] = j;
    			else {
    				c[i][j] = c[i-1][j] + c[i-2][j];
    			}
    		}
    	}
    	
    	
    	
    }
}

결과는 다행히도 통과네요 휴

 

3. 대안

 

3차례에 걸쳐 다른 방법으로 시도한 것이 무색하게, 그냥 피보나치 수열을 구하면 끝나는 문제였습니다.

0	1	2	3	4	5	6	7	8	9
0	1	1	2	3	5	8	13	21	34

f(5) 는 f(4)와 f(3)을 호출합니다.

f(4)에서 0,1을 호출하는 횟수와 f(3)이 0,1을 호출하는 횟수를 더하면 f(5)가 0,1을 호출하는 횟수를 알 수 있습니다.

f(3)은 2, 1  f(4) 는 3, 2 이를 더하면 5, 3이 나옵니다. 이런 식으로 f(n)까지를 모두 구한 게 제가 취한 방법입니다.

그런데 이 숫자는 각각 수열에서 f(5)=5에 해당하는 값과 f(4)=3에 해당하는 값이기도 합니다.

5를 완성하기 위해선 f(1)이 5개 있어야겠지요. f(6)은 8을 만들기 위해서 f(1)을 8번 호출했을 겁니다. 그래서 이 부분은 직관적으로 이해가 됩니다.

그런데, f(0)의 호출횟수는 선뜻 이해가 되지 않습니다. 뭐 그게 중요하겠습니까?

그냥 위 수열을 한번이라도 관찰해봤다면 규칙성을 발견할 수 있었을테죠.