[백준] 2474번 : 피보나치 수 (Python / 파이썬)

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

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

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

 

 

조건 및 입출력

1. 첫째 줄에 n이 주어진다. n은 45보다 작거나 같은 자연수이다.

2. 첫째 줄에 n번째 피보나치 수를 출력한다.

 

 

코드 (Python 3)

# 입력부
num=int(input());

# 처리부
result=0;

if(num<2):
    result=1;
else:    
    last=0;
    current=1;

    for i in range(2,num+1):
        tmp=current;
        current+=last;
        last=tmp;
    
    result=current;

# 출력부
print(result);

 

 

풀이 과정

만약 그 수가 2보다 작다면 피보나치 수열의 합은 1이다. (1밖에 없으므로)

그렇지 않으면 그 앞의 두 수를 계속 더해주면 된다. 이 때, 처음수는 0, 처음 수 다음은 1이다.

그렇게 계속 연산을 하다보면 [0,1]->[1,1]->[1,2]->[2,3]->[3,5]->[5,8]-> ... 이런식으로 뻗어나간다.

 

임시 변수를 하나 생성하고 그 변수에 n-1의 값을 넣고, 기존의 변수에 n-2값을 넣어주고 루프를 돌리면 피보나치 수열이 완성된다.

 

 

---

여담

아래에는 내가 처음 생각한 코드이다.

 

# 정의부
def fib(n):
    if(n==0): return 0;
    elif(n==1): return 1;
    else: return fib(n-1)+fib(n-2);

# 출력부
print(fib(int(input())));

 

시간 초과가 발생했다. 나중에 시간 복잡도를 생각해 보았다.

이 함수(fib)를 쓰면 매 시행마다 2번의 연산을 해야한다. 그렇게 본다면 시간 복잡도는 (2^n)이다.

 

n=10이면 -> 1024번

n=20이면 ->  1,048,576번 (104만 8576)

n=30이면 -> 1,073,741,824 (10억 7341만 1824)

.

.

.

n=100이면 -> 1,267,650,600,228,229,401,496,703,205,376 (숫자가 너무 커서 읽지도 못하겠다.)

 

이런식으로 횟수가 늘어나면 기하급수적으로 연산횟수가 늘어난다.

자료 구조를 살짝 찍먹(?) 하니까 이런 것들이 이제 눈에 보이기 시작한다.

 

 

코드가 이상하거나, 이해되지 않는 부분이 있다면 댓글 남겨주세요! + 더 좋은 풀이 방법이 있다면 알려주세요 :)