Oh My Algorithm
Algorithm Guidecomplexity: O(n)

피보나치 수열 (DP)

동적 계획법(Dynamic Programming)으로 이전 부분해(subsolution)를 테이블에 저장하고 재사용해 중복 계산을 제거합니다. 단순 재귀 O(2^n)을 O(n)으로 끌어내리는 가장 대표적인 메모이제이션 예시입니다.

01피보나치 수열 (DP)

피보나치를 DP로 구합니다. 앞의 두 답을 적어 두고 재사용하면 같은 계산을 두 번 하지 않아 10번째까지 O(n)에 끝납니다.

표를 비워 둡니다. 아직 아무것도 계산하지 않은 상태입니다.

출발점 두 칸만 직접 채웁니다. 0번째는 0, 1번째는 1 — 나머지는 전부 여기서 나옵니다.

앞의 두 칸을 더합니다 · 1 + 0 = 1. 이미 적어 둔 값이라 덧셈 한 번으로 끝납니다.

앞의 두 칸을 더합니다 · 1 + 1 = 2.

앞의 두 칸을 더합니다 · 2 + 1 = 3.

앞의 두 칸을 더합니다 · 3 + 2 = 5.

앞의 두 칸을 더합니다 · 5 + 3 = 8.

앞의 두 칸을 더합니다 · 8 + 5 = 13.

앞의 두 칸을 더합니다 · 13 + 8 = 21.

앞의 두 칸을 더합니다 · 21 + 13 = 34.

앞의 두 칸을 더합니다 · 34 + 21 = 55. 마지막 칸까지 찼습니다.

완료 · 답은 55입니다. 각 칸을 딱 한 번씩만 계산했습니다 — 재귀로 풀면 같은 값을 수없이 다시 셉니다.

dp[0]·
dp[1]·
dp[2]·
dp[3]·
dp[4]·
dp[5]·
dp[6]·
dp[7]·
dp[8]·
dp[9]·
dp[10]·
1 / 13

02 쉽게 이해하기

For Everyone
🔑핵심 동작

같은 부분 문제를 다시 풀지 않고 한 번 구한 값을 저장해 두었다가 꺼내 씁니다. 지수 시간이 선형 시간이 됩니다.

💡쉽게 말하면

작은 문제의 답을 표에 저장해 두고 재사용합니다.

단순 재귀의 중복 계산을 없애 O(2^n)을 O(n)으로 줄여요.

📍어디에 쓰나
  • –중복 부분문제가 있는 계산
  • –DP 입문

03 파이썬 구현 코드

피보나치 수열 (DP)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

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

04 자주 묻는 질문

FAQ
피보나치 수열 (DP)란 무엇인가요?+

동적 계획법(Dynamic Programming)으로 이전 부분해(subsolution)를 테이블에 저장하고 재사용해 중복 계산을 제거합니다. 단순 재귀 O(2^n)을 O(n)으로 끌어내리는 가장 대표적인 메모이제이션 예시입니다.

피보나치 수열 (DP)의 시간복잡도는 어떻게 되나요?+

피보나치 수열 (DP)의 시간복잡도는 O(n) 입니다. 시각화의 단계별 진행을 따라가며 왜 이런 복잡도가 나오는지 직접 확인할 수 있습니다.

피보나치 수열 (DP)은(는) 어디에 사용하나요?+

중복 부분문제가 있는 계산, DP 입문.

피보나치 수열 (DP)를 쉽게 비유하면?+

같은 부분 문제를 다시 풀지 않고 한 번 구한 값을 저장해 두었다가 꺼내 씁니다. 지수 시간이 선형 시간이 됩니다.

→ 동적 계획법 전체 보기Related
🧠최장 증가 부분 수열 (LIS)
O(n²)