수열 | Notion

피보나치 문제가 나올때마다

def fib(n):
	if n<=1:
		return 0
	elif n==2:
		return 1
	else:
		return fib(n-1)+fib(n-2)

K = int(input())
print(fib(K))

이렇게 빠르게 재귀로 풀 수 있는 것은 떠오른다.

하지만 이렇게 풀면 안되고 DP로 풀어야된다

왜 dp로 풀어야 되냐면..

K가 100 000 즉 100k면 어떻게 되겠나

fib(n-1)과 fib(n-2)를 각각 다시 호출하는 게 문제다.

fib(n-1)과 fib(n-2)는 또 각각 fib(n-2), fi(n-3) 그리고 fib(n-3), fib(n-4)를 호출한다.

계속해서 2배가 된다는 뜻이다. 즉 O(2^n)이다.

그리고 이거 말고도, 파이썬 재귀 깊이 제한 (기본 1000)에 걸린다.

K=int(input())

dp = [0] * (K+1)
dp[1] = 0
dp[2] = 1

for i in range(3, K+1):
	dp[i] = dp[i-1] + dp[i-2]
	
print(dp[K])

대충 이런 느낌

K = int(input())
MOD = 1000000007

if K==1:
	print('0')
else:
	dp = [0] * (K+1)
	dp[1] = 0
	dp[2] = 1

	for i in range(3, K+1):
		dp[i] = dp[i-1] + dp[i-2]
	
	print(dp[K] % MOD)

CLAUDE OPUS 4.8 PROMPT: 함정은 문제는 재귀적으로 주어졌는데, 그걸 dp적으로 생각하는 거라고 생각해. 문제가 dp적으로 주어졌면, 문제 지문은 어땠을까?

좋은 통찰입니다. 그 관점을 지문으로 뒤집어보면 이렇게 됩니다.
재귀적으로 주어진 원래 지문은 "위에서 아래로" 정의하는 말투입니다:

F(n) = F(n−1) + F(n−2)

즉 "F(n)을 알려면 F(n−1)과 F(n−2)를 알아야 한다" — 큰 걸 작은 것들로 쪼개는 방향. 이걸 곧이곧대로 코드로 옮기면 재귀가 나오고, 중복 계산 때문에 터집니다. 함정은 여기 있죠 — 정의를 그대로 번역하면 안 되고, 방향을 뒤집어 "아래에서 위로 쌓아야" 한다는 걸 스스로 깨달아야 한다는 것.
만약 DP적으로(=올라가는 방향으로) 주어졌다면 지문은 이런 식이었을 겁니다:

F(1) = 0, F(2) = 1 에서 시작한다.
i = 3부터 K까지, 앞의 두 값을 더해 F(i)를 차례로 구해 나간다.
이렇게 K번째까지 채웠을 때의 F(K)를 출력하시오.

이러면 지문 자체가 이미 반복문 구조라, 읽는 사람이 그대로 for i in range(3, K+1): dp[i] = dp[i-1] + dp[i-2]로 옮기면 끝. 깨달을 게 없어집니다. 함정이 사라지는 거죠.
핵심 차이를 정리하면:
재귀 지문은 "무엇인가"(what)를 정의합니다 — F(n)이 무엇과 같은지. 계산 순서는 안 알려줍니다. 순서는 님이 정해야 하고, 순진하게 정하면(top-down 그대로) 지수 시간이 됩니다.
DP 지문은 "어떻게 구하는가"(how)를 정의합니다 — 어떤 순서로 채워 나가는지. 순서가 지문에 박혀 있으니 그대로 따라가면 됩니다.
그래서 이 문제의 진짜 시험 포인트는 "피보나치를 아느냐"가 아니라, 선언적 정의(재귀식)를 절차적 계산(반복)으로 번역할 줄 아느냐입니다. 같은 수학적 사실을 what으로 던져주고 how를 요구하는 것 — 그게 함정의 본질이라는 님 생각이 정확합니다.
한 가지 덧붙이면, 재귀식을 그대로 두면서도 함정을 피하는 방법도 있습니다. 메모이제이션이죠:
pythonimport sys
from functools import lru_cache
sys.setrecursionlimit(200000)

@lru_cache(maxsize=None)
def F(n):
    if n <= 2:
        return n - 1          # F(1)=0, F(2)=1
    return (F(n-1) + F(n-2)) % 1000000007

print(F(int(input())))
이건 지문의 재귀 방향(top-down)을 유지하면서 중복 계산만 캐시로 없앤 겁니다. 그래서 "재귀로 주어졌으니 재귀로 풀되, 대신 기억하게 만든다"는 절충안이에요. 다만 K=100,000이면 재귀 깊이 제한을 손봐야 하고(위처럼), 파이썬에선 스택 오버플로 위험 때문에 반복 DP가 더 안전합니다. 그래서 실전에선 결국 아래에서 위로 쌓는 방식으로 귀결되죠 — 이 지점이 딱 "재귀로 생각하되 DP로 구현한다"는 님 표현 그대로입니다.