😥 백준 1003 : 피보나치 함수

1003: 피보나치 함수

solved.ac의 CLASS 3 문제를 첨 건들여봤다..!

📌 Try 1

import sys

def sumEach(x, y):
    return x[0]+y[0], x[1]+y[1]

def fibonacci(n, cnt0, cnt1): 
    if n == 0: 
        return cnt0+1, cnt1
    if n == 1: 
        return cnt0, cnt1+1
    else: 
        return sumEach(fibonacci(n-1, cnt0, cnt1), fibonacci(n-2, cnt0, cnt1))

N = int(sys.stdin.readline().rstrip())
cnt0, cnt1 = 0, 0

for _ in range(N): 
    print(*fibonacci(int(sys.stdin.readline().rstrip()), cnt0, cnt1))

피보나치는 워낙 많이 해봤으니까,,, 얕보고 귀찮아서 막했더니 시간초과 떠버렸다..

📌 Try 2

import sys

def fibonacci(n, arr):
    if n == 0:
        arr.append(0);
    elif n == 1:
        arr.append(1)
    else:
        fibonacci(n-1, arr)
        fibonacci(n-2, arr)

N = int(sys.stdin.readline().rstrip())

for _ in range(N):
    arr, i = [], int(sys.stdin.readline().rstrip())
    fibonacci(i, arr)
    print(arr.count(0), arr.count(1))

list에 넣어서 갯수 세는 방법으로 풀었는데,,, 여전히 시간초과 떴다.
재귀가 문제가 되는 것 같다.

재귀함수도 시간이 오래 걸리지만, list의 count함수의 시간 복잡도 역시 O(n)이기 때문에 오래 걸린다.

📌 Try 3

import sys

def fibonacci(n, arr):
    if n == 0:
        arr[0] += 1
    elif n == 1:
        arr[1] += 1
    else:
        fibonacci(n-1, arr)
        fibonacci(n-2, arr)

N = int(sys.stdin.readline().rstrip())

for _ in range(N):
    i = int(sys.stdin.readline().rstrip())
    arr = {0 : 0, 1 : 0}
    fibonacci(i, arr)
    print(arr[0], arr[1])

list가 아닌 dict를 사용해서 count함수로 발생하는 시간을 줄여봤는데, 그래도 시간초과가 뜬다.

피보나치 재귀함수의 시간 복잡도는 2^(n/2)로 O(2^n)라고 한다.

피보나치를 반복문으로 푼다면 O(n)으로 줄긴 하지만,
재귀함수 사용하지 않고는 풀지 못하겠다.

🎯 Solution

import sys

def fibonacci(n):
    zero, one, tmp = 1, 0, 0
    
    for _ in range(n):
        zero, one = one, one + zero
        
    print(zero, one)
    
    
N = int(sys.stdin.readline().rstrip())

for _ in range(N):
    i = int(sys.stdin.readline().rstrip())
    fibonacci(i)

재귀론 풀지 못하고 방법은 반복문 같았다.
도저히 반복문으로 풀지 못해서, 다른 분의 풀이를 봤다.

각 숫자마다 0과 1의 출현빈도 역시 재귀적으로 반복된다는 규칙이 있었다.

위의 규칙만 알면 아주 간단하게 풀 수 있었다,,,

🎁 Reference

• python으로 피보나치 수열 갖고 놀기
  https://www.crocus.co.kr/1643

• 깨지고 부서져라 - 백준 알고리즘 1003(python 파이썬)
  https://pacific-ocean.tistory.com/107