C#에서 탑다운(Top-Down) 접근 방식으로 피보나치 수열 구현하기

피보나치 수열은 0 또는 1로 시작하여 그다음 1이 이어지고, 이후의 각 숫자(피보나치 수)가 바로 앞의 두 숫자를 더한 값이 되는 규칙에 따라 진행되는 수열입니다.

탑다운(Top-Down) 접근 방식은 하나의 큰 문제를 더 작고 이해하기 쉬운 단위로 분해하는 데 초점을 맞춥니다. 재귀 호출을 통해 문제를 쪼개어 해결하고, 이미 계산된 결과는 배열(메모이제이션)에 저장해 두었다가 다시 활용함으로써 중복 계산을 제거할 수 있습니다.

이 방식은 결과를 저장하기 위해 입력 크기와 같은 크기의 추가 배열 메모리를 생성하므로, 공간 복잡도는 O(N)입니다.

시간 및 공간 복잡도

• 시간 복잡도: O(N)
• 공간 복잡도: O(N)

예제 코드

public class DynamicProgramming{
    public int fibonacciTopdownApproach(int n, int[] dpArr){
        if(n == 0 || n == 1){
            return n;
        }
        if(dpArr[n] != 0){
            return dpArr[n];
        }
        int res = fibonacciTopdownApproach(n - 1, dpArr) + fibonacciTopdownApproach(n - 2, dpArr);
        return dpArr[n] = res;
    }
}

static void Main(string[] args){
    DynamicProgramming dp = new DynamicProgramming();
    int[] dpArr = new int[150];
    Console.WriteLine(dp.fibonacciTopdownApproach(12, dpArr));
}

실행 결과

144

위 코드에서 dpArr 배열은 메모이제이션 역할을 합니다. 각 피보나치 수가 한 번만 계산되며, 이후에는 저장된 값을 그대로 반환하기 때문에 단순 재귀 방식의 지수 시간 복잡도(O(2^N))를 O(N)으로 크게 개선할 수 있습니다.