본문 바로가기
Problem Solving/백준

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

by sohyunwriter 2021. 2. 5.

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)

 

 

728x90

댓글0