[백준] 24416: 알고리즘 수업 - 피보나치 수 1 - python[파이썬]

처음에 의사코드를 그냥 그대로 옮겨서 적었더니 시간초과가 났다. 어쩐지 문제가 너무 쉽더라니... fib(n)에서 재귀를 너무 많이 호출하다보니 시간초과가 난 것 같아서 이 코드 대신 fib(1)과 fib(2)를 호출하는 경우를 구해서 반환하는 것으로 코드를 다시 짰다.

시간초과 코드

import sys
input = sys.stdin.readline

N = int(input())
cnt1 = 0
cnt2 = 0

# 피보나치 수 재귀 호출
def fib(n):
    global cnt1
    if n==1 or n==2:
        cnt1 += 1
        return 1
    else:
        return fib(n-1) + fib(n-2)

# 피보나치 수 동적 프로그래밍
def fibonacci(n):
    global cnt2
    f = [0, 1, 1]
    for i in range(3, n+1):
        cnt2 += 1
        f.append(f[i-1] + f[i-2])
    return f[n]

fib(N)
fibonacci(N)
print(cnt1, cnt2)

풀이

• fib(1)이나 fib(2)를 호출하는 경우는 재귀의 끝이다.
• 즉, fib(n)= afib(1) + bfin(2)꼴로 다시 나타낼 수 있다.
• fib(n) = fib(n-1) + fib(n-2)에 주목해보자.
  이는 다시 말해 fib(n)에서 fib(1)이나 fib(2)를 호출하는 횟수 = fib(n-1)에서 fib(1)이나 fib(2)를 호출한 횟수 + fib(n-2)에서 fib(1)이나 fib(2)를 호출하는 횟수이다.
• 그래서 fib(n)을 직접 만들어서 코드에 count를 집어넣는 게 아니라, fib(n)에서 fib(1)이나 fib(2)를 호출하는 횟수를 저장하는 리스트를 만들자. 그러면 재귀가 아니라 단순히 리스트를 만드는 것이므로 시간이 엄청나게 단축될 것이다.
• 위를 구하기 위해 코드를 짜다보니.. 어디서 많이 본 코드다..? 어라 fibonacci(n) 코드랑 똑같다. 짜기 전부터 뭔가 이건 fibonacci(n)랑 똑같아지는 거 아냐? 싶었는데 ㅎㅎ
• 결국 fibonacci(n)에서 return값이 우리가 구하고자 하는 횟수인 것이다.

코드

import sys
input = sys.stdin.readline

N = int(input())
cnt2 = 0

# 피보나치 수 동적 프로그래밍
def fibonacci(n):
    global cnt2
    f2 = [0, 1, 1]
    for i in range(3, n+1):
        cnt2 += 1
        f2.append(f2[i-1] + f2[i-2])
    return f2[n]

print(fibonacci(N), cnt2)

결과