피보나치 일반항

이 글은 바야흐로 알고리즘 시험문제를 풀다가 궁금증이 생겨서 쓰는 글이다.

알고리즘을 처음 배우게 되면 피보나치 수열을 재귀 방식으로 풀다가 나중에 다이나믹 프로그래밍을 통한 기법을 배우게 된다. 

재귀에서 다이나믹 프로그래밍으로 피보나치 수열을 풀면 시간복잡도도 O(N)으로 시간을 효율적으로 풀 수 있게 된다.

여기서 피보나치 수열이란 F(3) = F(2) + F(1)처럼 전전의 수와 전의 수를 합하여 현재 수를 구하는 수열이다.

아무튼 시험을 치다가 심심해서 피보나치 수열을 좀 더 간단히 풀고 싶어졌다.

그래서 점화식으로 나열된 피보나치 수열을 일반식으로 구해볼려고 20분동안 열심히 구해보려고 노력했다. N일때 F(N)을 바로 구할려고 했으나 규칙이 보이지 않았다.

그래서 시험을 끝나고 조교님한테 물어봤다. "혹시 피보나치 수열을 일반식으로 풀 수 있나요?"

그러자 포스텍 대학원생인 조교님은 이에 대한 답변을 해주셨다.
피보나치 수열의 일반식은 무리식으로 되어 있어 컴퓨터가 연산할 시 정수로 나누어떨어지지않아 안된다는 것이었다.
아니 역시 포스텍답다. 어떻게 알고 있었지? 이미 해본게 진짜 신기했고, 조교님 친구가 2분이 더 오셨는데 친구분이 당연하다시피 그렇게 하면 타임 리미트가 뜬다고도 알려주셨다. 클라스오졌다.
그러고나서 하시는 말씀은 더 빠르게 하고 싶으면 분할정복알고리즘으로 풀면 O(N)보다 더 빠르게 풀 수 있다고 알려 주셨다.

그래서 진짜 일반식이 뭔지 찾아보았다.
https://nous-temperature.tistory.com/678

피보나치수열의 일반항 구하기

위 블로그를 참고해보니, 피보나치 수열을 An+2 - An+1 - An=0이라는 수열로 바꾸어 이차방정식의 근을 구하는 방식대로 풀면 된다는 것이었다. 진짜 천잰데?

암튼 위와 같이 작성하면 피보나치수열을 바로 구할 수 있다! 

또한 분할정복은 재귀적으로 배열을 쪼갠다음 다시 합쳐서 구하는 방법이다. 이는 퀵정렬, 병합정렬이 대표적이다. 이것을 공부하기엔 과제가 너무 많으므로 추후에 시간이 나면 해야겠다.