✍️ 피보나치 수열 - 재귀함수
수학에서, 피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 처음 여섯 항은 각각 1, 1, 2, 3, 5, 8이다
즉, n번째 피보나치 수를 Fibo(n)라고 표현한다면,
Fibo(1) 은 1이고,
Fibo(2) 도 1입니다! (첫째 및 둘째 항을 1이라고 정함!)
Fibo(3) 부터는 이전 값과 이전 이전 값의 합입니다!
즉, Fibo(3) = Fibo(1) + Fibo(2) = 1 + 1 = 2 입니다.
그러면
Fibo(4) = Fibo(3) + Fibo(2) = 2 + 1 = 3
Fibo(5) = Fibo(4) + Fibo(3) = 3 + 2 = 5
Fibo(6) = Fibo(5) + Fibo(4) = 5 + 3 = 8 .....
Fibo(n) = Fibo(n - 1) + Fibo(n-2) 라고 표현할 수 있다!
Q. 피보나치 수열의 20번째 수를 구하시오.
-> Fibo(n) = Fibo(n - 1) + Fibo(n-2) 라는 수식을 그대로 표현해주시면 됩니다!
그리고 피보나치의 탈출 조건은?
n 이 1이거나 2일 때 1을 반환해주시면 된다.
input = 20
def fibo_recursion(n):
if n == 1 or n == 2:
return 1
return fibo_recursion(n - 1) + fibo_recursion(n - 2)
print(fibo_recursion(input)) # 6765
동적 계획법(Dynamic Programming)이란?
DP = 큰 문제를 같은 유형의 작은 문제들로 나누고, 그 작은 문제들의 답을 한 번만 계산해서(저장해서) 전체 문제를 빠르게 푸는 기법.
심 조건은 (1) 겹치는 부분 문제(overlapping subproblems) 와 (2) 최적 부분 구조(optimal substructure) 가 있어야 해요.
겹치는 부분 문제: 같은 작은 문제가 여러 번 등장함 → 결과를 저장(memoize)하면 중복 계산 제거.
최적 부분 구조: 전체 문제의 최적 해가 작은 부분 문제들의 최적 해로부터 구성될 수 있음.
비교: Divide & Conquer(분할정복)는 문제를 나누지만 부분 문제들이 서로 겹치지 않는 경우가 많아요(예: 퀵소트). DP는 겹칠 때 쓰면 좋아요.
동적 계획법은
- 여러 개의 하위 문제를 풀고 그 결과를 기록하고 이용해 문제를 해결하는 알고리즘!
- 재귀함수를 풀어나갈 때 많이 했던 함수의 수식화를 시키면 됨.
- F(string) = F(string[1:n-2]) 라고 수식을 정의했던 것 처럼,
문제를 쪼개서 정의할 수 있으면 동적 계획법을 쓸 수 있습니다!
이처럼 문제를 반복해서 해결해 나가는 모습이 재귀 알고리즘과 닮았다!
그러나 다른 점은, 그 결과를 기록하고 이용한다는 점!
용어정리
결과를 기록하는 것을 메모이제이션(Memoization) 이라고 하고,
문제를 쪼갤 수 있는 구조를 겹치는 부분 문제(Overlapping Subproblem)라고 함!
- 예시에서 설명 드렸던 부분에서
각 구간마다의 시간을 계산하면 최적의 시간을 구할 수 있는 것을 겹치는 부분 문제,
이미 실험했던 내용은 기록해두고 쓰면 된다는 것을 메모이제이션 이라고 생각하시면 됨!
즉, 겹치는 부분 문제일 경우 동적 계획법을 사용하면 되는데,
이 때 사용하는 방법은 메모이제이션을 이용하는구나! 라고 생각하시면 된다.
DP 풀기 위한 사고 순서(체크리스트)
- 상태(state)를 정의하라 — 문제의 어떤 정보를 변수로 남겨야 할까? (예: 인덱스 i, 남은 무게 w 등)
- 점화식(전이식, recurrence)을 세워라 — state끼리 어떻게 연결되는가?
- 초기값(base case)을 정하라 — 더 이상 나눌 수 없는 경우의 값.
- 계산 순서(탑다운/바텀업) 결정 — 재귀+메모(탑다운) 또는 반복 테이블(바텀업).
- 복원(path reconstruction)이 필요하면 부모 정보(parent)도 저장하라.
- 시간/공간 복잡도 확인 — 상태의 수 × 각 상태 계산 비용.
쉬운 예제들
1) 예제 — Fibonacci (비교적 가장 쉬움)
점화식: F(n) = F(n-1) + F(n-2), F(0)=0, F(1)=1
재귀(나쁜 예): 지수 시간 O(2^n) — 중복 계산 심함.
탑다운(메모이제이션) — O(n)
from functools import lru_cache
@lru_cache(None)
def fib_top(n):
if n <= 1:
return n
return fib_top(n-1) + fib_top(n-2)
# 사용 예
print(fib_top(10)) # 55
2) 새로 배운 동적 계획법의 메모이제이션
구현의 방법은 다음과 같습니다.
1. 메모용 데이터를 만든다. 처음 값인 Fibo(1), Fibo(2) 는 각각 1씩 넣어서 저장해둔다.
2. Fibo(n) 을 구할 때 만약 메모에 그 값이 있다면 바로 반환한다.
3. Fibo(n) 을 처음 구했다면 메모에 그 값을 기록한다.
input = 50
# memo 라는 변수에 Fibo(1)과 Fibo(2) 값을 저장해놨습니다!
memo = {
1: 1,
2: 1
}
def fibo_dynamic_programming(n, fibo_memo):
if n in fibo_memo:
return fibo_memo[n]
nth_fibo = fibo_dynamic_programming(n - 1, fibo_memo) + fibo_dynamic_programming(n - 2, fibo_memo)
fibo_memo[n] = nth_fibo
return nth_fibo
print(fibo_dynamic_programming(input, memo))
