[정글 알고리즘] - [하] 백준2748- 피보나치 수 2- 브론즈1

백준 · DP · 메모이제이션 · 브론즈1

메모이제이션을 이용해 피보나치 수를 빠르게 구하는 DP 기초 문제

문제 링크 바로가기

문제 한눈에 보기

목표	n번째 피보나치 수 구하기
핵심 개념	재귀 + 메모이제이션(하향식 DP)
점화식	fib(n) = fib(n-1) + fib(n-2)

핵심 1

일반 재귀는 같은 값을 계속 다시 계산해서 매우 느리다.

핵심 2

이미 구한 값은 memo 에 저장해서 재사용한다.

핵심 3

메모이제이션의 흐름은 확인 → 계산 → 저장 → 반환 이다.

최종 코드

def fib_memo(n, memo=None):
    if memo is None:
        memo = {}

    if n in memo:
        return memo[n]

    if n == 0:
        return 0
    if n == 1:
        return 1

    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

n = int(input())
print(fib_memo(n))

한 줄씩 설명

줄	코드	설명
1	def fib_memo(n, memo=None):	n번째 피보나치 수를 구하는 함수다.
2-3	if memo is None: memo = {}	처음 호출일 때만 빈 딕셔너리를 만든다.
5-6	if n in memo: return memo[n]	이미 계산한 값이면 바로 반환한다.
8-11	if n == 0: return 0 if n == 1: return 1	피보나치의 기저 조건이다.
13	memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)	아직 없는 값이면 재귀로 계산해서 저장한다.
14	return memo[n]	저장한 값을 반환한다.

왜 DP인가?

fib(5)를 일반 재귀로 구하면 fib(3), fib(2)를 여러 번 다시 계산한다. 하지만 메모이제이션을 쓰면 각 값은 한 번만 계산되어 시간 복잡도가 O(n) 으로 줄어든다.

시간복잡도

O(n)

공간복잡도

O(n) (memo + 재귀 스택)

한 문장 정리

피보나치 수 2는 메모이제이션을 이용해 중복 계산을 제거하는 가장 대표적인 DP 입문 문제다.