Fibonacci Number

정의를 한 글자도 빠짐없이 그대로 옮기세요. fib(0)은 0이고, fib(1)은 1이며, 그보다 큰 값은 모두 fib(n-1) + fib(n-2)를 반환합니다. 모든 호출 체인은 두 기본 사례 중 하나에서 끝나므로 답은 정확합니다.

이제 호출 횟수를 세어 보세요. fib(5)는 fib(4)와 fib(3)을 호출하지만, fib(4)도 fib(3)을 다시 호출합니다. 결국 fib(3)은 두 번, fib(2)는 세 번, fib(1)은 다섯 번 실행되고, fib(5)는 총 15번 호출합니다. 같은 값들이 계속해서 반복 계산됩니다.

호출 횟수는 피보나치 수 자체를 따릅니다. F(n)을 계산하면 2 × F(n+1) - 1번 호출합니다. n = 45일 때 이는 약 3.7 × 10^9번의 호출로, 시간 제한을 훨씬 초과합니다. 상한은 보통 O(2^n)으로 표기하며, 정확한 증가율은 약 1.618^n입니다. 재귀 깊이는 n단계에 불과하므로 스택에는 O(n)의 공간이 필요합니다.

재귀가 느린 것은 값을 기억하지 않기 때문입니다. 각 피보나치 수를 처음 계산할 때 적어 두면, 각 수를 계산하는 데 덧셈 한 번이면 됩니다. 인덱스 0부터 n까지의 칸이 있는 표 f를 만들고, f[0] = 0과 f[1] = 1을 설정한 다음, 나머지를 왼쪽에서 오른쪽으로 f[i] = f[i-1] + f[i-2]를 이용해 채우세요.

왼쪽에서 오른쪽으로 채우는 순서가 이 방법을 가능하게 합니다. f[i]에 도달했을 때 필요한 두 수가 이미 표에 들어 있기 때문입니다. n = 10일 때 표는 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 순으로 채워지고, 답은 마지막 칸에 있습니다.

이것은 가장 기본적인 형태의 동적 프로그래밍으로, 점화식과 더 작은 경우들의 답을 담은 표로 이루어집니다. 덧셈은 n-1번 필요하며, 시간 복잡도는 O(n)입니다. 표에는 n + 1개의 수가 들어가므로 공간 복잡도는 O(n)입니다. 이제 n = 45를 계산하는 데는 수십억 번의 호출 대신 덧셈 44번이면 됩니다.

테이블 반복문이 무엇을 읽는지 살펴보세요. f[i]를 채우려면 f[i-1]과 f[i-2]만 필요하고 그보다 오래된 값은 필요하지 않으므로, 이전의 모든 항목은 불필요합니다. 테이블 대신 변수 두 개를 사용하세요. prev는 두 단계 전의 숫자를 저장하고 curr는 한 단계 전의 숫자를 저장합니다.

F(0)과 F(1)에 해당하는 prev = 0과 curr = 1로 시작하세요. 각 단계에서 next = prev + curr를 계산한 다음, 두 값을 앞으로 한 칸씩 옮깁니다. prev에는 이전의 curr을 넣고, curr에는 next를 넣습니다. n = 4일 때 쌍은 (0, 1)에서 (1, 1), (1, 2), (2, 3)으로 이동하며, curr = 3이 답입니다.

연산은 동일하게 n-1번 덧셈을 하므로 시간 복잡도는 O(n)이고, 메모리에는 정수 세 개만 사용하므로 공간 복잡도는 O(1)입니다. 값을 갱신하는 순서가 중요합니다. 더하기 전에 prev를 덮어쓰면 잘못된 값으로 합을 계산하게 됩니다.