백준#2747 피보나치 수

1. 문제

• https://www.acmicpc.net/problem/2747
  

2. 풀이

• 나의 풀이
  

import sys

number = int(sys.stdin.readline())
memory = {}


def fib(n: int):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return 1
    if n > 2:
        if memory.get(n-2) and memory.get(n-1):
            return memory.get(n-2) + memory.get(n-1)
        else:
            memory[n-2] = fib(n-2)
            memory[n-1] = fib(n-1)
        return memory.get(n-2) + memory.get(n-1)


print(fib(number))

• 남의 풀이

  피보나치 수열의 점화식
  F0 = 0
  F1 = 1
  Fn = Fn-1 + Fn-2 (n>=2)

# 실패하는 피보나치수열 계산 (시간초과)
# 시간복잡도 O(2^n)
def fibonacci(n):
	if n == 0:
    	return 0
    if n == 1:
    	return 1
    return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(int(input()))

n = int(input())

a, b = 0, 1

while n > 0:
    a, b = b, a+b
    n -= 1

print(a)

3. 느낀 점

• 피보나치는 항상 재귀로만 풀어야한다고 생각했는데, 반복문으로 간단하게 해결가능 하군(오히료 시간복잡도도 낮아짐)

4. Reference