[CS] 재귀함수, 재귀 깊이, 메모이제이션, 동적 프로그래밍

1. 점화식: 문제를 정의하는 "공식"

- 예: 피보나치 수열 => F(n) = F(n-1) + F(n-2), F(1)=1, F(0)=0

 

1) 재귀 : 자기 자신을 호출, 간단하지만 느릴 수 있음

=> 시간복잡도: 지수 시간  O(2^n), 재귀 깊이 초과 가능, (n<=1000일때만 사용권장)

* 재귀 깊이: Python은 타 언어에 비해 최대 재귀 호출 깊이가 작다 => sys.setrecursionlimit()을 이용해 재귀 호출 깊이 조정 가능하지만, 너무 높게 설정하면 메모리 부족이나 파이썬 인터프리터 자체가 죽을 수 있다.

** 왜 제한이 있을까? 파이썬은 함수 호출마다 스택 프레임이라는 메모리 공간을 사용하는데, 재귀 호출이 너무 깊어지면 스택 오버플로우가 발생할 수 있어 제한을 둔 것이다!

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)
    
# 계산이 반복되어 느리다    
fib(5)
├─ fib(4)
│  ├─ fib(3)
│  │  ├─ fib(2)
│  │  │  ├─ fib(1)
│  │  │  └─ fib(0)
│  │  └─ fib(1)
│  └─ fib(2)
│     ├─ fib(1)
│     └─ fib(0)
└─ fib(3)
   ...

2) 재귀 + 메모이제이션(계산된 값 저장) => 성능 향상, 시간복잡도: 선형시간 O(n)

from functools import lru_cache

# lru = Least Recently Used, 최근에 사용하지 않은 값을 먼저 지움
@lru_cache(maxsize=None) # maxsize는 저장할 최대 결과 개수, None이면 무제한 저장
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)
    
# 한 번 계산하면 결과를 저장해서 다시 계산 안함! => 호출 트리가 작아져 속도 빠름

- 캐싱 안한 경우와 한 경우 비교

# 캐싱 안 한 경우
def slow_add(x, y):
    print("계산 중...")
    return x + y

slow_add(1, 2)  # 계산 중...
slow_add(1, 2)  # 계산 중...


# 캐싱 한 경우
@lru_cache(maxsize=None)
def fast_add(x, y):
    print("계산 중...")
    return x + y

fast_add(1, 2)  # 계산 중...
fast_add(1, 2)  # 캐시 사용, 계산 안 함!

 

3) 반복문(Bottom-up DP) : 재귀 없이 for문으로 점화식 계산, 빠르고 안정적

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

4) 변수 2개만 쓰는 최적화 방식 => 시간 O(n), 공간O(1)

def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

 

2. DP: 동적 프로그래밍

- 큰 문제를 작은 부분 문제로 나누고, 그 결과를 저장하며 차례대로 해결

- 보통 반복문과 배열을 이용한다

 

1) 메모이제이션

- Top-Down 방식, 재귀+메모이제이션

2) Bottom-up : 반복문으로 차례대로 계산

 

3. 오버플로우

- 변수에 저장할 수 있는 최대값을 초과해서 에러가 발생하거나 이상한 값이 들어가는 현상

- 나머지 연산의 성질

(a + b) % m = ((a % m) + (b % m)) % m

# 피보나치에 적용
F(n) % m 
= (F(n-1) + F(n-2)) % m
= (F(n-1) % m + F(n-2) % m) % m