피보나치 수열
피사의 레오나르도로 널리 알려진 레오나르도 피보나치가 1202년 토끼의 번식을 언급하면서 이 수에 대하여 연구했다. 하지만, 피보나치가 최초로 연구한 것은 아니고 인도의 수학자가 최초란 기록이 남아있다. 기원전 450년 핑갈라가 쓴 책에서 최초로 이 패턴이 언급되었고 이후 인도의 수학자들이 이 수에 대하여 연구한 흔적들이 발견되었다. 그 때문에 피보나치도 동방쪽에서 넘어온 정보를 접한 적이 있지 않았을까 생각하는 무리들도 있긴 하나 공식적인 연관성은 불명. 어쨌든 서유럽에서 이 수열을 연구하고 체계화할 수 있는 업적을 세운 것은 피보나치였기 때문에 피보나치 수열이란 이름이 붙게 됐다. 다만 피보나치수열이란 이름은 19세기가 되어서야 붙여졌다.
제0항을 0, 제1항을 1로 두고, 둘째 번 항부터는 바로 앞의 두 수를 더한 수로 놓는다. 1번째 수를 1로, 2번째 수도 1로 놓고, 3번째 수부터는 바로 앞의 두 수를 더한 수로 정의하는 게 좀더 흔하게 알려져 있는 피보나치 수열이다. 이 둘은 시작점이 다르다는 정도를 빼면 사실상 동일하다.
그 중에서 16 번째 항까지만 나열해 보자면 (0), 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987
이렇게 간다.
피보나치 수열의 이웃한 두 항이 항상 서로소라는 것은 수학적 귀납법으로 쉽게 증명할 수 있다. 피보나치 소수가 무한히 존재하는지는 유명한 미해결 문제다.
재귀
n 이 0이나 1일 때는 값도 0, 1이기 때문에 그대로 반환하면 되고, 2 이상일 때만 재귀 함수 두개로 분기해 값을 반환한다.
시간 복잡도는 함수가 한 번 호출되면 다시 두 번 호출되기 때문에 지수적으로 증가해 O(2^n)이 된다.
동적 프로그래밍
피보나치 알고리즘에서 동적 계획법이 쓰이는 이유는 기본적인 피보나치 수 알고리즘이 너무나 비효율적이기 때문이다.
반복적 풀이
n 이 2 미만일 때는 아까와 같이 그대로 반환한다. 그 다음이 재밌는데 n 이 2 이상일 때는 n-1 번만큼 반복문을 시행한다. 그 이유는 우리가 0번째 값 a 와 첫 번째 값 b 를 계속 반복하면서 원하는 값을 만들텐데, n 이 2일 때는 단 한 번(n-1)만 계산하면 원하는 값을 만들 수 있기 때문이다.
그리고 한 번의 반복마다 ‘a, b = b, a + b’를 시행한다. 파이썬에서 이와 같이 대입을 사용하면, ‘a = b’, ‘b = a + b’와 같이 대입이 이루어지는데 이는 파이썬의 packing & unpacking과 관련이 있다. 새로 만든 b 에 이전의 a, b 값을 더해 새로운 피보나치 값을 만들어 나간다. 반복문이 끝나면 b 가 우리가 고대하던 n 번째 피보나치 수가 되며 이를 반환하면 된다.
앞선 재귀에 비해 매우 효율적인 방법이며 시간 복잡도는 O(n)이 된다.
참고자료
https://namu.wiki/w/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98%20%EC%88%98%EC%97%B4
https://makefortune2.tistory.com/60
https://shoark7.github.io/programming/algorithm/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%84-%ED%95%B4%EA%B2%B0%ED%95%98%EB%8A%94-5%EA%B0%80%EC%A7%80-%EB%B0%A9%EB%B2%95.html
좋은 성과를 얻으려면 한 걸음 한 걸음이 힘차고 충실하지 않으면 안 된다, -단테
