[C++ - TIL] 피보나치 수열과 동적 계획법 - 메모이제이션 이해하기

🎮 주제 : 피보나치 수열과 동적 계획법 - 메모이제이션 이해하기

태그 : #C++ #알고리즘 #동적계획법 #메모이제이션 #재귀함수 #시간복잡도

---

📌 학습 요약

• 피보나치 수열과 점화식 : 앞의 두 항을 더해 다음 항을 만드는 규칙**(F(n) = F(n-1) + F(n-2))**을 이해하고, 이를 코드로 옮기는 재귀적 사고 습득
• 재귀의 한계와 비효율성 : 단순 재귀로 구현 시 동일한 하위 문제들이 중복 호출되어 시간 복잡도가 지수적으로 증가**(O(2^n))**하는 문제점 파악
• 메모이제이션(Memoization) : 동적 계획법(DP)의 핵심 기법으로, 한 번 계산한 결과를 배열에 저장해 두었다가 필요할 때 꺼내 써서 시간 복잡도를 **O(n)**으로 단축
• 안전한 메모리 관리 : 동적 배열 할당 시 초기화의 중요성을 인식하고, 계산 여부를 판별하기 위한 초기값(0 또는 -1) 설정 방법 숙지
• 조건문의 정교화 : if와 else if의 동작 차이를 구분하여 상호 배타적인 조건 분기를 구성하는 논리력 배양

---

🛠 주요 코드 및 구현 상세

1. 메모이제이션 기반 피보나치 (Top-Down)

int fibonacci(int n, int list[]) {
    // 1. 기본 사례 (Base Case)
    if (n <= 0)
        return 0;
    else if (n <= 2)
        return 1;

    // 2. 메모이제이션 확인: 이미 계산된 결과가 배열에 있다면 즉시 반환
    if (list[n] != 0) 
        return list[n];

    // 3. 계산 및 저장: 결과를 배열에 저장함과 동시에 반환
    return list[n] = fibonacci(n - 1, list) + fibonacci(n - 2, list);
}

int main() {
    int n = 45;
    // 동적 배열 생성과 동시에 모든 요소를 0으로 초기화
    int* list = new int[n + 1]{0}; 

    cout << "피보나치 수열 (" << n << ") : " << fibonacci(n, list) << endl;

    delete[] list; // 메모리 해제 필수
    return 0;
}

---

✅ 주요 문법 및 개념 정리

개념 특징 효과

단순 재귀	중복된 함수 호출이 무수히 발생	시간 복잡도 O(2^n) (매우 느림)
메모이제이션	계산 결과를 배열 등에 기록(Memo)	시간 복잡도 O(n) (비약적 향상)
배열 초기화	{0}을 사용해 쓰레기 값 방지	'계산 안 됨'과 '결과가 0임'을 구분
if vs else if	상호 배타적 분기 처리에 유리	불필요한 조건 검사 생략으로 성능 최적화

💡 핵심 인사이트 : 왜 메모이제이션인가?

• 단순 재귀에서는 **F(5)**를 구할 때 F(3)을 두 번 계산하지만, n이 커질수록 이 중복은 기하급수적으로 늘어남
• 메모이제이션은 **"한 번 구한 건 다시 계산하지 않는다"**는 단순한 규칙만으로 슈퍼컴퓨터로도 오래 걸릴 연산을 순식간에 끝내게 해줌

---

✨ 느낀 점

• 배열 초기화가 단순히 값을 넣는 행위를 넘어, 알고리즘의 '상태'를 구분하는 중요한 장치임을 새삼 깨달음
• 메모이제이션 적용 전후의 실행 속도 차이를 보며, 알고리즘 설계가 하드웨어 성능보다 더 큰 영향을 미칠 수 있음을 체감함
• if와 else if의 사소한 차이가 전체 로직의 흐름과 효율성을 결정짓는 것을 보며 꼼꼼한 코드 작성의 중요성을 느낌
• 재귀의 화려함 속에 숨겨진 비효율을 DP라는 전략으로 정복하는 과정에서 코딩의 재미를 다시 한번 발견함