[백준] 2747. 피보나치 수 - 문제 풀이 (+파이썬 코드)

Question. 백준 2747. 피보나치 수

 

 

피보나치 수열을 구현하는 문제이다.

예전에는 면접 질문으로도 자주 나왔다고 하는데, 요즘은 쉬워서 잘 안 나오는 것 같다.

다만, '피보나치 수를 구현하는 모든 방법은?', '피보나치 수를 각각 반복법, 재귀로 구현해보면?'

이런 식으로 물어볼 수는 있겠다.

 

---

Answer.

 

피보나치 수열을 구현하는 방식은 크게 3가지가 있는데, 

1) 재귀

2) recursion with memoization

3) for문 이용해 구현

 

하지만 이 문제는 1)의 방식대로 재귀로 풀면 '시간초과'가 난다.

O(N)에 풀어야 하는 문제이기 때문에, 

재귀로 풀 경우, memoization을 해야 한다.

 

sol 1) recursion with memoization

 

재귀로 구현하되 memoization을 한다.

즉, fibo(i)를 구하면 dp[i]에 그 값을 저장해둔다.

또, dp[i]가 이미 방문되었다면(-1이 아니라면), 바로 return 한다.

 

*아래와 같이 구현했을 때, recursion tree가 어떤 모양인지 궁금하다면 이 블로그 보면 도움이 된다.

 

# recursion with memoization
# time complexity : O(N)

def solve(n: int) -> int:
    dp = [0, 1] + [-1] * (n+1)  # 0, 1 값 저장(종료조건) 및 -1로 초기화(not visited)

    def fibo(n: int) -> int:
        # 이미 방문한 노드인 경우
        if dp[n] != -1:
            return dp[n]

        # memoization하며 방문
        dp[n] = fibo(n-1) + fibo(n-2)
        return dp[n]

    ans = fibo(n)
    return ans

n = int(input())
print(solve(n))

 

sol 2) for문 이용해 구현

 

0, 1을 미리 dp에 저장해둔다.

그리고 2부터 n까지 for문을 돌며, 이전 값 2개를 더해나간다.

# for문 이용해 구현
# time complexity : O(N)

def fibo(n):
    dp = [0, 1]
    for _ in range(2, n+1):
        dp.append(dp[-1] + dp[-2])
    return dp[n]

n = int(input())
print(fibo(n))

 

풀이법	time complexity	space complexity
sol 1)  recursion with memoization	O(N)	O(N)
sol 2)  for문 이용해 구현	O(N)	O(N)