문제

피보나치 수는 F(0) = 0, F(1) = 1일 때, 2 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 점화식입니다. 2 이상의 n이 입력되었을 때, fibonacci 함수를 제작하여 n번째 피보나치 수를 반환해 주세요. 예를 들어 n = 3이라면 2를 반환해주면 됩니다.

풀이 1

class Fibonacci {
    public long fibonacci(int num) {
        long answer = 0;
        long num1 = 0;
        long num2 = 1;

        for(int i=1; i<num; ++i){
            answer = num1 + num2;
            num1 = num2;
            num2 = answer;
        }    

        return answer;
    }



    // 아래는 테스트로 출력해 보기 위한 코드입니다.
    public static void main(String[] args) {
        Fibonacci c = new Fibonacci();
        int testCase = 69;
        System.out.println(c.fibonacci(testCase));
    }
}

내가 푼 방식이다. 먼저 문제에서 첫번째 수, 두번째 수는 각각 0과 1로 주어졌기 때문에 num1, num2라는 변수를 선언해준다. 만약 테스트케이스가 3이면 총 4개의 수가 나와야 한다. 이미 2개의 수(0, 1)가 나와있기 때문에 3까지는 총 2개만 더 나오면 된다. 그렇기에 for문의 시작은 1부터하고 끝은 num 전까지만 해준다.

풀이 2

class Fibonacci {
    public long fibonacci(int num) {
        long answer = 0;
        long[] dp = new long[num+1];
        dp[0]=0;dp[1]=1;

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

        return dp[num];
    }



    // 아래는 테스트로 출력해 보기 위한 코드입니다.
    public static void main(String[] args) {
        Fibonacci c = new Fibonacci();
        int testCase = 3;
        System.out.println(c.fibonacci(testCase));
    }
}

배열로 풀어도 되는데 너무 for문을 통해서만 풀려고 생각했는 것 같다. 다른 사람의 풀이를 보니 제일 위에 이 풀이가 올라와 있었다. 딱히 설명이 필요없고 코드만 봐도 이해가 잘 되는 풀이이다.

풀이 3

class Fibonacci {
    public long fibonacci(int num) {
		long answer = 0;
		if(num<2){
			answer = num;
		}else{
			answer = fibonacci(num-1) + fibonacci(num-2);
		}

		return answer;
	}


  // 아래는 테스트로 출력해 보기 위한 코드입니다.
    public static void main(String[] args) {
        Fibonacci c = new Fibonacci();
        int testCase = 3;
        System.out.println(c.fibonacci(testCase));
    }
}

피보나치 수하면 재귀함수로도 푸는 방법이 유명한데 떠오르질 않아서(-_-) 쓰지 못했다가 다른 사람 풀이를 보고 떠올랐다. 재귀함수는 입력값이 클수록 성능상 좋지 않다고 하니 1번이나 2번으로 풀면 될 듯 하다.