Algorithm Guidecomplexity: O(n)
피보나치 수열 (DP)
동적 계획법(Dynamic Programming)으로 이전 부분해(subsolution)를 테이블에 저장하고 재사용해 중복 계산을 제거합니다. 단순 재귀 O(2^n)을 O(n)으로 끌어내리는 가장 대표적인 메모이제이션 예시입니다.
01피보나치 수열 (DP)
알고리즘 작동 원리 탐색HOVER OR SCROLL
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
Live Python
02 쉽게 이해하기
For Everyone🔑비유
계단을 오를 때 이미 센 칸 수를 메모해 두고 다시 세지 않는 것.
💡쉽게 말하면
작은 문제의 답을 표에 저장해 두고 재사용합니다.
단순 재귀의 중복 계산을 없애 O(2^n)을 O(n)으로 줄여요.
📍어디에 쓰나
- –중복 부분문제가 있는 계산
- –DP 입문
03 파이썬 구현 코드
피보나치 수열 (DP)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.
core_implementation.py
04 자주 묻는 질문
FAQ피보나치 수열 (DP)란 무엇인가요?+
동적 계획법(Dynamic Programming)으로 이전 부분해(subsolution)를 테이블에 저장하고 재사용해 중복 계산을 제거합니다. 단순 재귀 O(2^n)을 O(n)으로 끌어내리는 가장 대표적인 메모이제이션 예시입니다.
피보나치 수열 (DP)의 시간복잡도는 어떻게 되나요?+
피보나치 수열 (DP)의 시간복잡도는 O(n) 입니다. 시각화의 단계별 진행을 따라가며 왜 이런 복잡도가 나오는지 직접 확인할 수 있습니다.
피보나치 수열 (DP)은(는) 어디에 사용하나요?+
중복 부분문제가 있는 계산, DP 입문.
피보나치 수열 (DP)를 쉽게 비유하면?+
계단을 오를 때 이미 센 칸 수를 메모해 두고 다시 세지 않는 것.
→ 동적 계획법 전체 보기Related