동적 계획법 1 설명의 피보나치 예시에서 설명한 문제다. 실제로 코드에 카운터를 삽입해서 DP 와 단순 완전 탐색간의 계산 횟수가 얼마나 차이나는지 확인해볼 수 있다.
문제 자체는 그냥 의사 코드를 구대로 구현하고 카운터 변수만 올바르게 삽입하면 된다.
#include <iostream>
using namespace std;
int f1 = 0, f2 = 0;
int fib(int n) {
if (n == 1 || n == 2) {
f1++;
return 1;
}
else {
return (fib(n - 1) + fib(n - 2));
}
}
int fibonacci(int n) {
int f[41]; f[1] = f[2] = 1;
for (int i = 3; i <= n; i++) {
f2++;
f[i] = f[i - 1] + f[i - 2];
}
return f[n];
}
int main() {
int n; cin >> n;
fib(n); fibonacci(n);
cout << f1 << " " << f2;
return 0;
}예제 입출력에 의하면 입력이 30일 때 무려 832040 대 28 이라는 극악한 차이가 나타난다.
문제에서 나타나는 재귀적인 중복 계산의 증가 속도가 어마어마하다는 걸 알 수 있다.
for문으로 계산하는 방식은 바로 계산 횟수가 예상되는데 재귀호출 방식은 직관적으로 잘 와닿지 않는다.
그래서 30의 실행 계보를 그래프로 만들어 넣고 싶었는데 Obsidian과 mermaid가 그래프 렌더링을 못해준다…11 이상에서도 edge 가 많다면서 죽어버리는 바람에 10짜리 밖에 못 만들었다. 30보단 훨씬 축소되었지만 그래도 8대 55라는 나름 극적인(?) 차이를 보여준다.
flowchart TD
1((10)) --> 2((9))
1((10)) --> 3((8))
2((9)) --> 4((8))
2((9)) --> 5((7))
4((8)) --> 8((7))
4((8)) --> 9((6))
8((7)) --> 16((6))
8((7)) --> 17((5))
16((6)) --> 32((5))
16((6)) --> 33((4))
32((5)) --> 64((4))
32((5)) --> 65((3))
64((4)) --> 128((3))
64((4)) --> 129((2))
128((3)) --> 256((2))
128((3)) --> 257((1))
256((2)) -."1".-> 128((3))
257((1)) -."1".-> 128((3))
128((3)) -."2".-> 64((4))
129((2)) -."1".-> 64((4))
65((3)) --> 130((2))
65((3)) --> 131((1))
130((2)) -."1".-> 65((3))
131((1)) -."1".-> 65((3))
64((4)) -."3".-> 32((5))
65((3)) -."2".-> 32((5))
33((4)) --> 66((3))
33((4)) --> 67((2))
66((3)) --> 132((2))
66((3)) --> 133((1))
132((2)) -."1".-> 66((3))
133((1)) -."1".-> 66((3))
66((3)) -."2".-> 33((4))
67((2)) -."1".-> 33((4))
32((5)) -."5".-> 16((6))
33((4)) -."3".-> 16((6))
17((5)) --> 34((4))
17((5)) --> 35((3))
34((4)) --> 68((3))
34((4)) --> 69((2))
68((3)) --> 136((2))
68((3)) --> 137((1))
136((2)) -."1".-> 68((3))
137((1)) -."1".-> 68((3))
68((3)) -."2".-> 34((4))
69((2)) -."1".-> 34((4))
35((3)) --> 70((2))
35((3)) --> 71((1))
70((2)) -."1".-> 35((3))
71((1)) -."1".-> 35((3))
34((4)) -."3".-> 17((5))
35((3)) -."2".-> 17((5))
16((6)) -."8".-> 8((7))
17((5)) -."5".-> 8((7))
9((6)) --> 18((5))
9((6)) --> 19((4))
18((5)) --> 36((4))
18((5)) --> 37((3))
36((4)) --> 72((3))
36((4)) --> 73((2))
72((3)) --> 144((2))
72((3)) --> 145((1))
144((2)) -."1".-> 72((3))
145((1)) -."1".-> 72((3))
72((3)) -."2".-> 36((4))
73((2)) -."1".-> 36((4))
37((3)) --> 74((2))
37((3)) --> 75((1))
74((2)) -."1".-> 37((3))
75((1)) -."1".-> 37((3))
36((4)) -."3".-> 18((5))
37((3)) -."2".-> 18((5))
19((4)) --> 38((3))
19((4)) --> 39((2))
38((3)) --> 76((2))
38((3)) --> 77((1))
76((2)) -."1".-> 38((3))
77((1)) -."1".-> 38((3))
38((3)) -."2".-> 19((4))
39((2)) -."1".-> 19((4))
18((5)) -."5".-> 9((6))
19((4)) -."3".-> 9((6))
8((7)) -."13".-> 4((8))
9((6)) -."8".-> 4((8))
5((7)) --> 10((6))
5((7)) --> 11((5))
10((6)) --> 20((5))
10((6)) --> 21((4))
20((5)) --> 40((4))
20((5)) --> 41((3))
40((4)) --> 80((3))
40((4)) --> 81((2))
80((3)) --> 160((2))
80((3)) --> 161((1))
160((2)) -."1".-> 80((3))
161((1)) -."1".-> 80((3))
80((3)) -."2".-> 40((4))
81((2)) -."1".-> 40((4))
41((3)) --> 82((2))
41((3)) --> 83((1))
82((2)) -."1".-> 41((3))
83((1)) -."1".-> 41((3))
40((4)) -."3".-> 20((5))
41((3)) -."2".-> 20((5))
21((4)) --> 42((3))
21((4)) --> 43((2))
42((3)) --> 84((2))
42((3)) --> 85((1))
84((2)) -."1".-> 42((3))
85((1)) -."1".-> 42((3))
42((3)) -."2".-> 21((4))
43((2)) -."1".-> 21((4))
20((5)) -."5".-> 10((6))
21((4)) -."3".-> 10((6))
11((5)) --> 22((4))
11((5)) --> 23((3))
22((4)) --> 44((3))
22((4)) --> 45((2))
44((3)) --> 88((2))
44((3)) --> 89((1))
88((2)) -."1".-> 44((3))
89((1)) -."1".-> 44((3))
44((3)) -."2".-> 22((4))
45((2)) -."1".-> 22((4))
23((3)) --> 46((2))
23((3)) --> 47((1))
46((2)) -."1".-> 23((3))
47((1)) -."1".-> 23((3))
22((4)) -."3".-> 11((5))
23((3)) -."2".-> 11((5))
10((6)) -."8".-> 5((7))
11((5)) -."5".-> 5((7))
4((8)) -."21".-> 2((9))
5((7)) -."13".-> 2((9))
3((8)) --> 6((7))
3((8)) --> 7((6))
6((7)) --> 12((6))
6((7)) --> 13((5))
12((6)) --> 24((5))
12((6)) --> 25((4))
24((5)) --> 48((4))
24((5)) --> 49((3))
48((4)) --> 96((3))
48((4)) --> 97((2))
96((3)) --> 192((2))
96((3)) --> 193((1))
192((2)) -."1".-> 96((3))
193((1)) -."1".-> 96((3))
96((3)) -."2".-> 48((4))
97((2)) -."1".-> 48((4))
49((3)) --> 98((2))
49((3)) --> 99((1))
98((2)) -."1".-> 49((3))
99((1)) -."1".-> 49((3))
48((4)) -."3".-> 24((5))
49((3)) -."2".-> 24((5))
25((4)) --> 50((3))
25((4)) --> 51((2))
50((3)) --> 100((2))
50((3)) --> 101((1))
100((2)) -."1".-> 50((3))
101((1)) -."1".-> 50((3))
50((3)) -."2".-> 25((4))
51((2)) -."1".-> 25((4))
24((5)) -."5".-> 12((6))
25((4)) -."3".-> 12((6))
13((5)) --> 26((4))
13((5)) --> 27((3))
26((4)) --> 52((3))
26((4)) --> 53((2))
52((3)) --> 104((2))
52((3)) --> 105((1))
104((2)) -."1".-> 52((3))
105((1)) -."1".-> 52((3))
52((3)) -."2".-> 26((4))
53((2)) -."1".-> 26((4))
27((3)) --> 54((2))
27((3)) --> 55((1))
54((2)) -."1".-> 27((3))
55((1)) -."1".-> 27((3))
26((4)) -."3".-> 13((5))
27((3)) -."2".-> 13((5))
12((6)) -."8".-> 6((7))
13((5)) -."5".-> 6((7))
7((6)) --> 14((5))
7((6)) --> 15((4))
14((5)) --> 28((4))
14((5)) --> 29((3))
28((4)) --> 56((3))
28((4)) --> 57((2))
56((3)) --> 112((2))
56((3)) --> 113((1))
112((2)) -."1".-> 56((3))
113((1)) -."1".-> 56((3))
56((3)) -."2".-> 28((4))
57((2)) -."1".-> 28((4))
29((3)) --> 58((2))
29((3)) --> 59((1))
58((2)) -."1".-> 29((3))
59((1)) -."1".-> 29((3))
28((4)) -."3".-> 14((5))
29((3)) -."2".-> 14((5))
15((4)) --> 30((3))
15((4)) --> 31((2))
30((3)) --> 60((2))
30((3)) --> 61((1))
60((2)) -."1".-> 30((3))
61((1)) -."1".-> 30((3))
30((3)) -."2".-> 15((4))
31((2)) -."1".-> 15((4))
14((5)) -."5".-> 7((6))
15((4)) -."3".-> 7((6))
6((7)) -."13".-> 3((8))
7((6)) -."8".-> 3((8))
2((9)) -."34".-> 1((10))
3((8)) -."21".-> 1((10))