[알고리즘 일기] 2. 피보나치 수열

문제 002. (2021-05-02)

​

피보나치 수열

피보나치 수열이란 첫 번째 항과 두 번째 항이 1이고, 세 번째 항부터는 바로 앞의 두 항의 합으로 정의된 수열입니다.

예를 들어서 세 번째 항은 첫 번째 항(1)과 두 번째 항(1)을 더한 2이며, 네 번째 항은 두 번째 항(1)과 세 번째 항(2)을 더한 3이 될 것입니다.

​

주의사항

* 파라미터로 1 이상의 자연수 n을 받고, n번째 피보나치 수를 리턴하는 재귀 함수 fib를 쓰세요.

​

❧ 테스트 셋

def fib(n):
    # Code

# Test : print fib(1) to fib(10)
for i in range(1, 11):
    print(fib(i))

 

❧ 출력 예시

1
1
2
3
5
8
13
21
34
55

 

---

 

❧ 정답

def fib(n):
    if (n < 3):
        return 1
    else:
        return fib(n-2) + fib(n-1)
    # Code

# Test
for i in range(1, 11):
    print(fib(i))

 

1️⃣ 재귀 함수 문제 풀이

* Recursive case: 현 문제가 너무 커서, 같은 형태의 더 작은 부분 문제를 재귀적으로 푸는 경우

* Base case: 이미 문제가 충분히 작아서, 더 작은 부분 문제로 나누지 않고도 바로 답을 알 수 있는 경우

​

2️⃣ 시간 복잡도

* base case, 두 번의 재귀적 호출

* fib 호출 한 번의 시간 복잡도는 O(1)

* 매 호출마다 fib 함수가 재귀적으로 두 번 더 호출(fib(2) · fib(1) 이전까지 두 배로 늘어남)

* fib(n)의 시간 복잡도 : O(2n)

​

​

​