중앙대 자료구조 피보나치 수열의 계산-Memoization

(1)recursive call 을 이용한 code

if n `= 1return nelsereturn fibonacci(n- + fibonacci(n-``` 이 코드는 n이 1 또는 0일 때 간단히 n을 반환하고, 그렇지 않을 경우 재귀 호출을 통해 F(n-과 F(n-의 값을 더하여 반환한다. 이 방식은 쉽게 이해할 수 있지만, 큰 n에 대해선 크기가 기하급수적으로 증가하는 호출의 수로 인해 비효율적이다. 예를 들어 n이 40일 때, 이 코드는 약 4억 번의 호출을 수행하게 된다. 이 문제를 해결하기 위해서 memoization을 적용할 수 있다. memoization은 재귀 호출 시 계산한 값을 사전에 저장하고, 필요할 때 저장된 값을 참조하여 중복 계산을 방지하는 방법이다. ```pythondef fibonacci_memo(n, memo={})if n in memoreturn memo[n]if n `= 1return nmemo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)return memo[n]``` 이 코드에서는 memo라는 기본 인자 딕셔너리를 사용하여 이미 계산된 피보나치 수의 값을 저장한다. 함수가 호출되면 먼저 memo 딕셔너리에서 해당 값이 존재하는지를 확인한다. 존재한다면 그 값을 즉시 반환하여 불필요한 계산을 방지한다. 만약 값이 존재하지 않는다면, 기본적인 재귀 호출을…(생략)