2748번 - - 피보나치 수 2 다국어

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

Top-down (재귀)

def f(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return f(n - 1) + f(n - 2)


print(f(int(input())))Í

테스트 케이스

25까지는 무사히 잘 나온다.

다만 입력을 90까지 늘렸는데 갑자기 무한루프가 도는 느낌이다.

f(90) 부터 계속 수많은 f(x)들을 호출하는데 캐싱을 하지 않은 상태이므로 f(88)을 호출하고 f(88)을 한번더 호출할 가능성이 있기 때문에 f를 호출 할 때 시간이 오래 걸린다. 이럴때 메모이제이션을 적용해야 한다.

메모이제이션 VS 비메모이제이션

메모이제이션 사용 안한 f 호출 횟수

count = 0

def f(n):
    global count
    count += 1

    if n == 0:
        return 0
    elif n == 1:
        return 1
    return f(n-1) + f(n-2)


print(f(int(input())))
print(f'count: {count}')

메모이제이션 사용 한 f 호출 횟수

# 초기값을 음수로 입력해주면 n번째 캐시가 음수가 있는여부를 새로 구한 문제인지 판단
cache = [-1] * 91
cache[0] = 0
cache[1] = 1

count = 0


def f(n):
    global count
    count += 1
    if cache[n] == -1:
        cache[n] = f(n - 1) + f(n - 2)

    return cache[n]


print(f(int(input())))
print(f'count: {count}')

전체 코드

# 초기값을 음수로 입력해주면 n번째 캐시가 음수가 있는여부를 새로 구한 문제인지 판단
cache = [-1] * 91
cache[0] = 0
cache[1] = 1

count = 0


def f(n):
    global count
    count += 1
    if cache[n] == -1:
        cache[n] = f(n - 1) + f(n - 2)

    return cache[n]

    # if n == 0:
    #     return 0
    # elif n == 1:
    #     return 1
    # return f(n-1) + f(n-2)


print(f(int(input())))
# print(f'count: {count}')

Bottom-up (반복문)

N = int(input())
cache = [-1] * 91
cache[0] = 0
cache[1] = 1

for i in range(2, N + 1):
    cache[i] = cache[i - 1] + cache[i - 2]

print(cache[N])