[Java 문제풀이] - 피보나치

Task 

아래 수식으로 정의되는 피보나치 함수에 대하여 구현하기

Given , complete the fibonacci function so it returns .:

나의 문제풀이

import java.util.*;
public class Fibonacci {
        public static int fibonacci_case1(int n) {
            //재귀함수를 사용. 
            if (n ==0){
                return 0;
            }else if(n==1){
                return 1;
            }else{
                int result = fibonacci_case1(n-1)+fibonacci_case1(n-2);
                return result;
                
            }
            
        }
        
        public static int fibonacci_case2(HashMap<Integer, Integer> dp, int n) {
            
            if (dp.containsKey(n)) {
                return dp.get(n);//이미 n을 계산했다면 해쉬맵에서 꺼내서 돌려준다.다시 계산하지 않아도 되도록
            }
            if (n <=1){
                return n;
            }else{//계산한 후 dp에 저장
                int result = fibonacci_case2(dp,n-1)+fibonacci_case2(dp,n-2);
                dp.put(n, result);
                return result;
                
            }
            
        }

        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int n = scanner.nextInt();
            scanner.close();
            System.out.println(fibonacci_case1(n)+"is the result_case1");
            
            HashMap<Integer, Integer> dp = new HashMap<Integer, Integer>(); //동적할당
            System.out.println(fibonacci_case2(dp, n)+"is the result_case2");
        }
}

• Case 1 : n 이 0<n<=30으로 규정되었으므로 recursive 로 풀고제출
• 재귀함수로 풀었을때 O(2N) 의 시간복잡도로 계산된다.

• Case 2 : 메모이제이션 을 사용 

재귀함수로 표현했을 때, 중복되어 계산되는부분이 많기때문에 중복되는 부분을 HashMap 에 넣어놓고, 한번 계산한 값은 다시 계산하지 않아도 되도록 구현 

출처 : https://www.hackerrank.com/challenges/ctci-fibonacci-numbers/problem