중복 계산 제거를 통한 재귀 함수 시간 복잡도 최적화

Context

동일한 입력값에 대해 반복적으로 수행되는 고비용 계산으로 인한 리소스 낭비 발생. 특히 Recursive Function 구조에서 중복 Subproblem이 기하급수적으로 증가하며 시스템 성능 저하 유발.

Technical Solution

• Calculation 결과값을 저장하는 별도의 저장소(Notepad)를 활용한 Memoization 기법 도입
• Check 단계에서 기존 저장소 내 동일 입력값 존재 여부를 우선 확인하는 로직 설계
• Cache Miss 발생 시에만 실제 계산을 수행하고 결과를 저장소에 기록하는 Write-through 방식 적용
• Cache Hit 시 계산 과정을 생략하고 저장된 값을 즉시 반환하여 연산량 최소화
• Fibonacci 수열과 같은 중복 하위 문제 구조의 시간 복잡도를 지수 시간에서 선형 시간으로 개선