[백준] 24416번 : 알고리즘 수업 - 피보나치 수 1 - 우당탕탕 개발자 되기 프로젝트

 

24416번: 알고리즘 수업 - 피보나치 수 1

 

1. 문제 설명

2. 풀이과정

처음에 문제를 아래의 코드처럼 풀었다.

문제에 있는 두 함수를 그대로 사용하면서 각 함수가 호출되는 횟수를 구하는 방식으로 문제를 해결하였으나, 시간 초과가 발생하였다.

 

import sys

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[1] = 1
    f[2] = 1

    for i in range(3, n + 1):
        f[i] = f[i - 1] + f[i - 2]
        cnt2 += 1

    return f[n]

n = int(sys.stdin.readline())
f = [0] * (n + 1)

cnt1 = 0
cnt2 = 0
fib(n)
fibonacci(n)

print(cnt1)
print(cnt2)

 

첫 번째 함수인 재귀 함수로 인해 시간 초과가 발생한다고 생각하여 해당 문제를 어떻게 해결할지 고민하던 중

두 번째 함수의 호출 횟수는 n - 2회인 것을 확인할 수 있다. (n이 5 이상이기 때문에)

하여 두 번째 함수의 호출 횟수를 간단하게 구할 수 있었다.

재귀 함수가 호출되는 횟수는 각 피보나치 수와 일치한다는 것을 알게 되었다.

하여 문제에서 주어진 두 번째 함수를 응용해 첫 번째 함수의 호출 횟수를 구하도록 하였다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 첫 번째 함수의 호출 횟수를 구할 함수를 정의한다. def fib(n)
3. 첫 번째와 두 번째 피보나치 수를 구할 때는 해당 함수가 각 1회 호출된다. f[1] = 1  f[2] = 1
4. 세 번째 피보나치 수부터 n 번째 피보나치 수까지 각 피보나치 수를 구할 때 해당 함수가 호출되는 횟수는 각 피보나치 수와 동일하므로 3부터 n까지 수를 불러와 for i in range(3, n + 1)
5. 각 피보나치 수를 구해 저장한다. f[i] = f[i - 1] + f[i - 2]
6. 구하고자 하는 피보나치 수의 값을 반환한다. return f[n]
7. 두 번째 함수의 호출 횟수를 구할 함수를 정의한다. def fibonacci(n)
8. 해당 함수의 호출 횟수는 n - 2이므로 해당 값을 반환한다. return n - 2
9. 수를 입력받고 n = int(sys.stdin.readline())
10. 첫 번째 함수의 호출 횟수를 저장할 리스트를 생성해 준다. f = [0] * (n + 1)
11. 각 함수를 호출하며 해당 함수의 호출 횟수를 출력한다. print(fib(n))  print(fibonacci(n))

반응형

3. 소스코드

import sys

def fib(n):
    f[1] = 1
    f[2] = 1

    for i in range(3, n + 1):
        f[i] = f[i - 1] + f[i - 2]

    return f[n]

def fibonacci(n):
    return n - 2

n = int(sys.stdin.readline())

f = [0] * (n + 1)

print(fib(n))
print(fibonacci(n))