[프로그래머스] 피보나치수 (재귀함수, 메모이제이션)

문제 설명 

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다. 

예를 들어 F(2) = F(0) + F(1) = 0 + 1 = 1 F(3) = F(1) + F(2) = 1 + 1 = 2 F(4) = F(2) + F(3) = 1 + 2 = 3 F(5) = F(3) + F(4) = 2 + 3 = 5 와 같이 이어집니다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

 

제한 사항

n은 2 이상 100,000 이하인 자연수입니다.

 

입출력 예

n	return
3	2
5	5

 

입출력 예 설명

피보나치수는 0번째부터 0, 1, 1, 2, 3, 5, ... 와 같이 이어집니다.

---

문제 풀이

def solution(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    
    result = (solution(n-1) + solution(n-2)) % 1234567
    return result

재귀함수를 이용하여 이렇게 풀어봤는데, 런타임 에러가 발생 하였다.

 

그도 그럴 것이, 

• 시간 복잡도: O(2^n) (지수적 시간 복잡도, 호출 수가 지수적으로 증가)
• 공간 복잡도: O(n) (재귀 호출 스택의 깊이)

 

assert fibo(10) == 55
assert fibo(100) == 354224848179261915075  # ➡️ 안끝난다...!

 

이걸 해결하기 위해서 메모이제이션을 사용해보았다.

memo = {0: 0, 1: 1, 2: 1}

def solution(n):
	# 1234567으로 나눈 나머지
	MOD = 1234567

    if n in memo:
        return memo[n]
        
                                           # 1234567으로 나눈 나머지
    memo[n] = solution(n-1) + solution(n-2) % MOD
    
    return memo[n]

이렇게 하면

• 시간 복잡도: O(n) (메모이제이션 덕분에 각 피보나치 수를 한 번만 계산)
• 공간 복잡도: O(n) (메모이제이션에 사용하는 메모리와 재귀 호출 스택)

그래도 런타임 에러로 실패.. ㅠㅠㅠ!!!

메모이제이션을 사용한다 해도 n 값이 너무 커질 때가 여전히 문제이다..

* 그리고 2:1은 굳이 안해줘도 된다. 어차피 n=2 일때 구하는 과정은 O(1)이므로 굳이 변수 할당 해줄 필요가 없음.

 

완성코드

def solution(n):
    MOD = 1234567

    a, b = 0, 1
    
    # n이 2 이상이라는 제약이 있으므로, 반복문을 2부터 n까지 실행
    for _ in range(2, n + 1):
        a, b = b, (a + b) % MOD
    
    return b

# test
print(solution(3))  # 2
print(solution(5))  # 5

답은 반복문을 사용하여 재귀 호출 깊이에 따른 문제를 피하는 것이였다!

• 시간 복잡도: O(n)
  반복문은 2부터 n까지의 항목에 대해 한 번씩 수행되므로 전체 시간 복잡도는 O(n)

• 공간 복잡도: O(1)
  추가적인 메모리 사용은 상수 공간만 필요하며, a, b, 그리고 반복문 카운터와 같은 변수를 사용
  ➡️ 피보나치 수를 저장하는 데 별도의 추가 메모리를 사용하지 않기 때문에 공간 복잡도는 O(1)

둘다 시간 복잡도는 O(n)이지만, 

메모이제이션을 사용하는 재귀적 접근은 많은 함수 호출을 유발한다.

특히, n이 크면 많은 재귀 호출을 발생시키고, memo 딕셔너리가 매우 커질 수 있으며, 이로 인해 메모리 부족이나 스택 오버플로우가 발생할 수 있다.

 

반복적 접근을 통한 단순 업데이트는 n에 따라 O(n) 시간 복잡도를 가지며, 상수 개수의 변수만을 사용하여 메모리 사용이 적고, 재귀 호출로 인한 문제를 피할 수 있어 pass 하였다.

---

https://school.programmers.co.kr/learn/courses/30/lessons/12945

프로그래머스