정의

피보나치 수열은 앞의 두 수를 더해서 다음 수를 만드는 수열입니다. 동적 계획법(DP)의 가장 기본적인 예시로, 이미 계산한 값을 저장해두고 재사용하는 방법을 배울 수 있습니다.

핵심 특성

• ✓점화식: fib(n) = fib(n-1) + fib(n-2)
• ✓기저 조건: fib(0) = 0, fib(1) = 1
• ✓중복 계산 제거: 같은 값을 여러 번 계산하지 않음
• ✓상향식(Bottom-up) 접근: 작은 문제부터 큰 문제로

시간 복잡도