문제 요약
피보나치 수를 구할 때,
- 재귀(의사코드
fib)에서 코드1(if n==1 or n==2 then return 1)이 실행되는 횟수 - DP(의사코드
fibonacci)에서 코드2(f[i] = f[i-1] + f[i-2])가 실행되는 횟수
를 출력한다. (5 ≤ n ≤ 40)
내가 작성한 코드 (정답)
n = int(input())
f = [1, 1]
fib_count = 1
fibonacci_count = 0
def fib(n):
global fib_count
if n == 1 or n == 2:
return 1
else:
fib_count += 1
return fib(n - 1) + fib(n - 2)
def fibonacci(n):
global fibonacci_count
for i in range(2, n):
fibonacci_count += 1
f.append(f[i - 2] + f[i - 1])
return f[n - 1]
fib(n)
fibonacci(n)
print(fib_count, fibonacci_count)
fib_count를 0에서 시작하면 1씩 작게 나왔던 이유
문제에서 세는 코드1 실행 횟수는 “재귀가 끝나는 지점(=base case)”의 실행 횟수다.
즉 fib(n) 호출 트리에서 n==1 또는 n==2에 도달한 호출의 개수를 세어야 한다.
그런데 위 코드에서는:
- base case에서 카운트를 올리지 않고
- else(재귀 분기)에서만
fib_count += 1을 하고 있다
그래서 실제로는 “코드1 실행 횟수”가 아니라
“재귀 분기(내부 노드) 횟수 + 보정값” 비슷한 걸 세게 된다.
fib_count = 1로 시작해서 통과한 이유는, 우연히 특정 n에서 결과가 맞아떨어지도록 상수 보정이 된 것에 가깝고, 카운트의 정의에 맞는 방식은 아니다.
제대로 고치는 방법: base case에서 카운트하기
아래처럼 n==1 or n==2일 때 카운트를 올리면, 코드1 실행 횟수를 정확히 셀 수 있다.
n = int(input())
code1 = 0
code2 = 0
def fib(k):
global code1
if k == 1 or k == 2:
code1 += 1 # 코드1 실행 횟수
return 1
return fib(k - 1) + fib(k - 2)
def fibonacci(k):
global code2
f = [0] * (k + 1)
f[1] = f[2] = 1
for i in range(3, k + 1):
code2 += 1 # 코드2 실행 횟수
f[i] = f[i - 1] + f[i - 2]
return f[k]
fib(n)
fibonacci(n)
print(code1, code2)
이 코드에서 배울 수 있는 점
- “어떤 줄의 실행 횟수”를 세는 문제는, 그 줄이 실행되는 분기에서 카운트를 올려야 한다.
- 재귀의 코드1 실행 횟수는 “base case 도달 횟수”이고, 이 값은 피보나치 수 F(n) 과 동일하다.
- 예: n=30이면 코드1 실행 횟수는 832040 (예제 출력과 동일)
- DP의 코드2 실행 횟수는 반복문의 횟수이므로 정확히
n-2번이다.