백준[10870번/C#] 피보나치 수 5

평소에 알고리즘 공부 안하다가 스텝업을 위해서 요즘 알고리즘 공부를 열심히 하고 있습니다.

 

사용언어 : C#

 

피보나치 수를 구하는 것은 일단 시간 복잡도 상 재귀함수로 구하는 것은 비효율적입니다.

재귀 함수 이용시 시간 복잡도가 O(2^n)이 되어버리기 때문에 효율적으로 하고 싶다면 '반복문'을 활용

하시는게  좋습니다. 반복문으로 구할 경우 시간 복잡도는 O(n)입니다.

 

원리는 

 

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

 

첫번째와 두번째 수를 더하면 세번째 값이 되고 한칸씩 오른쪽으로 밀려가면서 더해가는 수열입니다.

 

즉, C = A+BB = AA = C 이렇게 반복해나가면 되지만...문제는 재귀함수를 활용해달라고 했으니 재귀함수를 활용해봅시다.

 

피보나치 정의를 보면n == 0 return 0;n == 1 return 1;n > 1   return F(n-1) + F(n+2)이기 때문에 이를 그대로 옮겨 적는다면 

 

	int Fibo(int num)
        {
            if (num <= 1)
                return num;

            return Fibo(num - 1) + Fibo(num - 2);
        }

        public void Main()
        {
            int num = int.Parse(Console.ReadLine());
            Console.WriteLine(Fibo(num));
        }

로 풀면 되겠습니다.

조건문을 0일때랑 1일때 정확히 구분해주는 것도 좋겠지만...

어차피 같은거 아닌가 라는 생각에 조건문을 하나로 통합시켰습니다.

문제가 될 수 있으면 알려주세요.