C#에서 바텀업(Bottom-Up) 방식으로 피보나치 수열 구현하기

피보나치 수열은 0 또는 1로 시작하고 그다음에 1이 이어지며, 이후에는 각 숫자(피보나치 수)가 바로 앞의 두 숫자의 합과 같아진다는 규칙에 따라 전개되는 수열입니다.

바텀업(Bottom-Up, 상향식) 접근 방식은 동적 계획법(Dynamic Programming)의 대표적인 기법으로, 가장 작고 기본적인 하위 문제부터 먼저 해결한 뒤, 그 결과를 차곡차곡 쌓아 올려 최종적으로 완전한 해답을 도출하는 방식입니다. 재귀 호출을 사용하지 않기 때문에 스택 오버플로우 걱정 없이 안정적으로 동작합니다.

복잡도 분석

• 시간 복잡도 — O(N): 반복문을 통해 각 피보나치 수를 한 번씩만 계산합니다.
• 공간 복잡도 — O(N): 계산 결과를 저장하기 위한 배열이 필요합니다.

구현 예제

public class DynamicProgramming {
    public int fibonacciBottomupApproach(int n) {
        int[] dpArr = new int[150];
        dpArr[1] = 1;
        for (int i = 2; i <= n; i++) {
            dpArr[i] = dpArr[i - 1] + dpArr[i - 2];
        }
        return dpArr[n];
    }
}

static void Main(string[] args) {
    DynamicProgramming dp = new DynamicProgramming();
    Console.WriteLine(dp.fibonacciBottomupApproach(5));
}

코드 설명

위 코드는 크기 150의 정수 배열 dpArr을 선언하여 각 인덱스에 해당하는 피보나치 값을 저장합니다. 초기값으로 dpArr[1] = 1을 설정한 후, 인덱스 2부터 n까지 반복하면서 dpArr[i] = dpArr[i - 1] + dpArr[i - 2] 공식으로 이전 두 값의 합을 순차적으로 계산합니다. 최종적으로 dpArr[n]을 반환하면 n번째 피보나치 수를 얻을 수 있습니다.

실행 결과

5

n = 5를 입력했을 때 피보나치 수열은 0, 1, 1, 2, 3, 5와 같이 전개되므로, 다섯 번째 피보나치 수인 5가 출력됩니다.