Note
동적 프로그래밍과 재귀 호출의 실행 횟수를 비교하는 문제입니다.
문제
오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.
오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍으로 구하는 알고리즘을 배웠다. 재귀호출에 비해 동적 프로그래밍이 얼마나 빠른지 확인해 보자. 아래 의사 코드를 이용하여 n의 피보나치 수를 구할 경우 코드1 코드2 실행 횟수를 출력하자.
문제 링크: https://www.acmicpc.net/problem/24416
피보나치 수 재귀호출 의사 코드
fib(n) {
if (n = 1 or n = 2)
then return 1; # 코드1
else return (fib(n - 1) + fib(n - 2));
}
피보나치 수 동적 프로그래밍 의사 코드
fibonacci(n) {
f[1] <- f[2] <- 1;
for i <- 3 to n
f[i] <- f[i - 1] + f[i - 2]; # 코드2
return f[n];
}
입력
첫째 줄에 n(5 ≤ n ≤ 40)이 주어진다.
출력
코드1 코드2 실행 횟수를 한 줄에 출력한다.
예제
예제 입력 1:
5
예제 출력 1:
5 3
예제 입력 2:
30
예제 출력 2:
832040 28
문제 분석
이 문제는 동적 프로그래밍과 재귀 호출의 실행 횟수 차이를 보여주는 교육적인 문제입니다.
핵심 이해
- 코드1: 재귀 호출에서
n == 1 or n == 2조건이 실행되는 횟수 - 코드2: 동적 프로그래밍에서 반복문이 실행되는 횟수
실행 횟수 분석
재귀 호출 (fib):
fib(5)를 호출하면:fib(4)와fib(3)호출fib(4)는fib(3)과fib(2)호출fib(3)은fib(2)와fib(1)호출fib(2)와fib(1)이 여러 번 호출됨
- 코드1 실행 횟수 = 재귀 호출에서 기저 조건에 도달한 횟수
동적 프로그래밍 (fibonacci):
- 반복문이 3부터 n까지 실행됨
- 코드2 실행 횟수 = n - 2
해결 방법
동적 프로그래밍의 원리를 이해하고, 각 방법의 실행 횟수를 정확히 카운트해야 합니다.
재귀 호출 실행 횟수
재귀 호출에서 코드1이 실행되는 횟수는 fib(n)의 값과 같습니다.
- 각 재귀 호출이 기저 조건에 도달할 때마다 1을 반환
- 반환된 값들의 합이 fib(n)이 되므로, 기저 조건 도달 횟수 = fib(n)
동적 프로그래밍 실행 횟수
반복문이 3부터 n까지 실행되므로:
- 코드2 실행 횟수 = n - 2
코드 구현
올바른 구현
n = int(input())
# 재귀 호출 실행 횟수 카운터
code1 = 0
def fib(i):
global code1
if i == 1 or i == 2:
code1 += 1
return 1
return fib(i - 1) + fib(i - 2)
# 동적 프로그래밍 실행 횟수
code2 = 0
d = [0] * (n + 1)
d[1] = 1
d[2] = 1
for i in range(3, n + 1):
code2 += 1
d[i] = d[i - 1] + d[i - 2]
fib(n) # 재귀 호출 실행
print(code1, code2)제공된 코드의 문제점
원래 제공된 코드에서 fibonacci 함수에 문제가 있습니다:
def fibonacci(i):
global code2
if i == 1 or i == 2:
return d[i]
for i in range(3, n + 1): # 문제: 매번 전체 루프를 실행
code2 += 1
d[i] = d[i - 1] + d[i - 2]
return d[i]이 함수는 매번 호출될 때마다 3부터 n까지 전체 루프를 실행하므로 잘못된 결과가 나옵니다. 올바른 방법은 반복문을 함수 밖에서 한 번만 실행하는 것입니다.
실행 횟수 분석
예제 1: n = 5
재귀 호출 (fib(5)):
fib(5)
→ fib(4) + fib(3)
→ fib(3) + fib(2) [fib(2) = 1, code1++]
→ fib(2) + fib(1) [fib(2) = 1, code1++]
[fib(1) = 1, code1++]
→ fib(2) + fib(1) [fib(2) = 1, code1++]
[fib(1) = 1, code1++]
코드1 실행 횟수: 5 (fib(5)의 값)
동적 프로그래밍:
- 반복문: i = 3, 4, 5
- 코드2 실행 횟수: 3
결과: 5 3
예제 2: n = 30
- 코드1 실행 횟수: fib(30) = 832,040
- 코드2 실행 횟수: 30 - 2 = 28
결과: 832040 28
시간 복잡도 비교
| 방법 | 시간 복잡도 | n=30일 때 실행 횟수 |
|---|---|---|
| 재귀 호출 | O(2^n) | 약 832,040번 |
| 동적 프로그래밍 | O(n) | 28번 |
동적 프로그래밍이 훨씬 효율적임을 보여줍니다!