CodeWars 아홉 번째 문제

Product of consecutive Fib numbers

public class ProdFib { // must be public for codewars 
  
  public static long[] productFib(long prod) {
    
    long i = 1;
    long firstFibo = 0;
    long secondFibo = 0;
    long sumFibo = 0;
    
    do {
      
      firstFibo = Fibonacci(i);
      secondFibo  = Fibonacci(i+1);
      sumFibo = firstFibo*secondFibo;
      i++;
            
    } while (sumFibo < prod);
    
    if(sumFibo == prod) {
      return new long[] {firstFibo, secondFibo, 1};
    } else {
      return new long[] {firstFibo, secondFibo, 0};
    }
  }
  
  public static long Fibonacci(long n) {
    long first = 0;
    long second = 1;
    
    for(long i=1; i < n; i++) {
      long sum = first+second;
      first = second;
      second = sum;
    }
    
    return second;
  }
}

*피보나치 수열 알고리즘을 이용하여 살짝 변형시킨 문제이다.

피보나치 수열하면 보통 학창시절 재귀함수를 배울 때 많이 배운다. 가끔 재귀함수에 대해서 이해가 잘 가지 않는 편인데 이번 기회에 다시 공부하게 되었다.

근데 문제는 재귀함수는 전혀 상관 없이 풀 수 있는 문제이다. 위에 내가 푼 정답은 맞으나 코드 가독성으로는 0점인듯 하다.

더욱이 피보나치 수열은 동적프로그래밍으로 충분히 해결 할 수 있고 해당 문제 조건은 클린하게 변경할 수 있다.

아래는 다른 사람들이 푼 문제를 참조하여 깔끔하게 정리한 코드이다.

public class ProdFib { // must be public for codewars 
  
  public static long[] productFib(long prod) {
    
    long firstFibo = 0;
    long secondFibo = 1;
    
    while (firstFibo*secondFibo < prod) {
      
      long temp = firstFibo;
      firstFibo = secondFibo;
      secondFibo  = temp + secondFibo;
                  
    }
	return new long[] {firstFibo, secondFibo, (firstFibo*secondFibo == prod ? 1 : 0)};
  }
}

*피보나치 수열 코딩 방법

1. 재귀함수 : 성능이 좋지 않음

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

1. 동적프로그래밍 : : 중간 중간 계산된 값을 재활용하는 기법. 코딩이 어려우나 성능이 빠름.

public static int dynamicFibonacci(int n) {
    int last1 = 1, last2 = 1, result = 0;
        
    if(n <= 1)
        return 1;
        
    for(int i=1; i < n; i++) {
      	result = last1 + last2;
      	last1 = last2;
     	last2 = result;
    }
        
    return result;
}