알고리즘 03 - (기본 패턴 03) 유형 - 4. 피피보나치 문제 핵심 정리

피보나치 문제 핵심 정리

피보나치 문제를 쉽게 이해하고 암기하기 위해 다음과 같은 핵심 내용을 단계별로 정리합니다.

---

1. 피보나치 문제의 정의

• 점화식: [ F(n) = F(n-1) + F(n-2), \quad (n \geq 2) ]
• 초기 조건: [ F(0) = 0, \quad F(1) = 1 ]
• 의미: 피보나치 수열의 각 항은 이전 두 항의 합으로 정의됨.

---

2. 피보나치 문제 접근 방식

2.1 문제 파악

1. 기저 조건(Base Case):
   • 문제를 해결할 수 있는 가장 작은 입력값을 파악.
   • 예: ( F(0) = 0, F(1) = 1 ).
2. 점화식 이해:
   • 큰 문제(( F(n) ))를 작은 문제(( F(n-1), F(n-2) ))로 나눌 수 있는지 확인.

---

2.2 해결 방법 선택

피보나치 수열 문제는 크게 4가지 방식으로 해결할 수 있습니다.

방식	특징	시간 복잡도	공간 복잡도
1. 단순 재귀	중복 계산이 많아 비효율적. 작은 문제 연습에 적합.	( O(2^n) )	( O(n) )*
2. 메모이제이션	재귀 + 캐싱으로 중복 계산을 방지. 효율적이고 직관적.	( O(n) )	( O(n) )
3. 테이블 방식	작은 문제부터 반복적으로 계산하며 배열에 저장.	( O(n) )	( O(n) )
4. 공간 최적화	테이블 대신 변수 2개만 사용하여 메모리 절약. 큰 입력에 적합.	( O(n) )	( O(1) )

---

3. 각 방식의 핵심 암기 포인트

3.1 단순 재귀

def fibonacci_recursive(n):
    if n <= 1:
        return n
    return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

• 암기 포인트:
  • 기저 조건: ( F(0) = 0, F(1) = 1 ).
  • 점화식 ( F(n) = F(n-1) + F(n-2) )를 그대로 재귀적으로 구현.
• 문제점:
  • 중복 계산이 많아 ( O(2^n) )의 시간 복잡도를 가짐.
  • ( F(n-1) )과 ( F(n-2) )를 반복적으로 계산.

---

3.2 메모이제이션

def fibonacci_memoization(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci_memoization(n-1, memo) + fibonacci_memoization(n-2, memo)
    return memo[n]

• 암기 포인트:
  • 캐싱: 이전 계산 결과를 저장하여 중복 계산 방지.
  • 재귀와 딕셔너리를 결합.
• 장점:
  • 시간 복잡도 ( O(n) ), 공간 복잡도 ( O(n) ).
  • 직관적인 코드로 효율적인 계산 가능.

---

3.3 테이블 방식

def fibonacci_tabulation(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

• 암기 포인트:
  • 배열 사용: 작은 문제부터 ( dp[i] = dp[i-1] + dp[i-2] )로 계산.
  • 반복문: 작은 문제부터 순차적으로 계산.
• 장점:
  • 시간 복잡도 ( O(n) ), 공간 복잡도 ( O(n) ).
  • 재귀 호출이 없어 스택 오버플로우 걱정이 없음.

---

3.4 공간 최적화

def fibonacci_optimized(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

• 암기 포인트:
  • 변수 2개 사용: 배열 대신 ( a, b )를 사용하여 공간 절약.
  • 반복문으로 계산.
• 장점:
  • 시간 복잡도 ( O(n) ), 공간 복잡도 ( O(1) ).
  • ( n )이 매우 큰 경우에도 효율적.

---

4. 피보나치 문제 접근 3단계

1. 문제 이해:
   • ( n )번째 피보나치 값을 구하는 문제.
   • 기저 조건과 점화식을 반드시 파악.
   • 큰 문제를 작은 문제로 나누는 구조를 이해.
2. 해결 방식 선택:
   • ( n )이 작을 경우:
     • 단순 재귀나 메모이제이션 사용.
   • ( n )이 클 경우:
     • 테이블 방식 또는 공간 최적화를 사용.
3. 효율성 고려:
   • 중복 계산 방지(메모이제이션).
   • 메모리 사용 절약(공간 최적화).

---

5. 암기용 요약 정리

항목	핵심 내용
점화식	( F(n) = F(n-1) + F(n-2) ), 초기 조건: ( F(0) = 0, F(1) = 1 ).
단순 재귀	점화식을 그대로 구현. 중복 계산 많음. 시간 복잡도 ( O(2^n) ).
메모이제이션	재귀 + 캐싱. 중복 계산 방지. 시간 복잡도 ( O(n) ), 공간 복잡도 ( O(n) ).
테이블 방식	반복문 + 배열. 작은 문제부터 순차적으로 계산. 시간 복잡도 ( O(n) ), 공간 복잡도 ( O(n) ).
공간 최적화	배열 대신 변수 2개로 공간 절약. 시간 복잡도 ( O(n) ), 공간 복잡도 ( O(1) ).

---

6. 피보나치 문제 확장

• 계단 오르기 문제:
  • 한 번에 1칸 또는 2칸씩 오를 수 있을 때 ( n )개의 계단을 오르는 방법의 수.
  • 점화식: ( f(n) = f(n-1) + f(n-2) ).
• 동전 교환 문제:
  • 주어진 동전으로 ( n )원을 만드는 최소 동전 수.
• 최적 경로 문제:
  • 격자에서 오른쪽이나 아래로만 이동할 때, ( n \times m )의 최소 합 경로.