백준 1003번 - 파이썬

안녕하세요 밥풀입니다.!

오늘 풀어볼 백준 문제는 1003번입니다.

https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

 

접근방법

이 문제는 얼핏보면 굉장히 쉬운 문제처럼 보이지만 시간제한이 0.25초라는것을 볼 수 있고 조금은 아이디어가 필요한 문제라는 것을 알 수 있습니다. 문제에 나와있는 c++함수의 경우에는 O(2^n)이라는 무시무시한 시간복잡도를 가지고 있기 때문에 쓸 수 없습니다! 대신 메모이제이션을 사용하면 더 빠른 성능 좋은 피보나치 수열 코드를 만들 수 있습니다. 

 

메모이제이션을 쉽게 말하자면 이미 계산한 값은 메모해둔 곳에서 가져와서 계산을 함으로써 불필요한 시간을 단축시키는 것입니다!

 

 저는 이 문제를 풀면서 굉장히 어렵게 접근을 했는데 아마 피보나치 수열의 특성을 잘 알고 계신 분들이라면 어렵지 않게 풀 수 있지 않을까 싶습니다. 

피보나치 수열은

F(1) = 1

F(2) = 1

F(N) = F(N-1) + F(N-2) (N >2)

 

라는 조건을 가지고 있는데요

0의 개수를 Z(n) 1의 갯수를 O(n)이라고 가정하고

n이 n-1 과 n-2로 재귀 호출을 하니까 Z(n) = Z(n-1) + Z(n-2)와 O(n) = O(n-1) + O(n-2)가 성립합니다.

그래서 우리는 Z(n)과 O(n)의 점화식이 동일한 것을 확인할 수 있슴니다!

 

하지만 시작값이 조금 다른 것을 확인할 수 있는데

Z(n)의 경우 n = 0부터 1, 0, 1, 1 ...이고 O(n)의 경우 0, 1, 1, 2 ... 인것을 확인할 수 있는데

Z(n)의 수열은 O(n)의 수열과 비교하면 앞에 1을 하나더 추가하면 동일한 것을 확인할 수 있습니다!

그렇기 때문에 우리는 Z(n+1) = O(n) 이 성립하는 것을 확인할 수 있습니다.

 

그러면 설명은 끝났습니다. 

출력을 할 때 "Z(n+1) O(n)"만 출력을 하면 정답이 나온다는 것을 유추할 수 있습니다.

그리고 시간 복잡도 또한 O(2n)인데 상수는 때버리고 계산하면 O(N)인 것을 알 수 있습니다.

def fibonacci(n, memo = {}):
    if n in memo:
        return memo[n]
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
        return memo[n]

T = int(input())

for _ in range(T):
    number = int(input())
    if number == 0:
        print(1, 0)
    elif number == 1:
        print(0, 1)
    else:
        print(fibonacci(number-1), fibonacci(number))