Oh My Algorithm
Algorithm Guidecomplexity: O(n)

피보나치 수열 (DP)

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

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step
TAP OR HOVER
Fibonacci DP
dp[0]·
dp[1]·
dp[2]·
dp[3]·
dp[4]·
dp[5]·
dp[6]·
dp[7]·
dp[8]·
dp[9]·
dp[10]·

피보나치 DP를 시작합니다. n=10까지의 dp 테이블을 채워 dp[10]을 구합니다. 부분해를 저장·재사용해 O(n)에 수렴합니다.

Logic Node1 / 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]
Guide Progress0%