피보나치 수

문제 설명

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.
2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

풀이

public class FibonacciCalculator
{
    private const int DIVISOR = 1234567;
    
    public int Solution(int n)
    {
        int answer = 0;
        
        Dictionary<int, int> cache = new Dictionary<int, int>();
        
        cache.Add(0, 0);
        cache.Add(1, 1);
        
        long result = CalculateFibonacci(n, cache);
        
        return (int)result;
    }

    private int CalculateFibonacci(int n, Dictionary<int, int> cache)
    {
        if (cache.ContainsKey(n))
        {
            return cache[n];
        }
        
        int fibNMinus1 = CalculateFibonacci(n-1, cache);
        int fibNMinus2 = CalculateFibonacci(n-2, cache);
        
        int currentFib = (fibNMinus1 + fibNMinus2) % DIVISOR;
        
        cache.Add(n, currentFib);
        
        return currentFib;
    }
}

• 단순히 직관적으로 접근하여 F(n) = F(n-1) + F(n-2)라는 명시된 방식대로 연산을 수행할 경우 n이 매우 커졌을 때 재귀 방식으로 연산 할 경우 기본 스택 크기를 초과하는 부하가 가해질 수 있음

상수 선언

private const int DIVISOR = 1234567;

• 최종적으로 결과를 도출할 때 사용할 1234567이라는 값은 변하지 않는 상수이므로 클래스 전역에서 사용하도록 선언

재귀 함수

	private int CalculateFibonacci(int n, Dictionary<int, int> cache)
    {
        if (cache.ContainsKey(n))
        {
            return cache[n];
        }
        
        int fibNMinus1 = CalculateFibonacci(n-1, cache);
        int fibNMinus2 = CalculateFibonacci(n-2, cache);
        
        int currentFib = (fibNMinus1 + fibNMinus2) % DIVISOR;
        
        cache.Add(n, currentFib);
        
        return currentFib;
    }

• 피보나치 수 연산을 수행하는 과정 자체는 재귀 방식을 사용. 동일한 절차의 과정을 내부적으로 반복하는 과정이므로 유리하다고 판단
• 연산 과정을 줄이기 위해 Dictionary<int, int> cache를 통해 기존에 연산한 값에 대해서는 cache 찾아 반환하도록 하는 메모이제이션(Memoization) 방식을 활용
• 저장된 값이 없을 경우 새로 등록하긴 하지만 그 과정에서도 다른 저장된 값을 활용하므로 유리

  Ex) F(5) = F(4) + F(3)
  = F(4) + F(2) + F(1)
  = F(3) + F(2) + F(2) + F(1)

  • 더 큰 숫자들에 대해서도 이러한 과정이 반복되므로 값을 저장한 것을 활용할 수 있음

결과 도출

• 최종적으로 DIVISOR로 나눈 나머지를 계산하는 것이 목적이므로 cache에 값을 저장할 때부터 나머지를 연산
  (덧셈에 대해서는 나머지를 구하는 연산의 분배법칙이 성립)

  F(5) = F(4) + F(3) =
  → F(5) % DIVISOR = (F(1) + F(1) + F(1) + F(1) + F(1)) % DIVISOR

• 나머지를 저장함으로써 int 저장 범위를 초과하는 것도 방지할 수 있음