4/2(화) 오늘의 코테 2 - 피보나치 수

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

프로그래머스

 

정답코드 1. 재귀 - 시간초과

 

# 1. 재귀
def solution(n):

    if n < 2:
        return n
    else:
        return (solution(n-1) + solution(n-2)) % 1234567

 

 

정답코드 2. Memoization

 

def solution(n):

    memo = {}  # 메모이제이션을 위한 딕셔너리를 초기화합니다.

    def fib(n):
        """
        메모이제이션을 사용하여 재귀적으로 n번째 피보나치 수를 계산합니다.

        매개변수:
        - n: 계산할 n번째 피보나치 수입니다.

        반환 값:
        - 1234567로 나눈 n번째 피보나치 수의 나머지입니다.
        """
        if n in memo:  # 이전에 계산된 값이 있으면 그 값을 바로 반환합니다.
            return memo[n]
        if n <= 1:  # 기본 사례 처리: 0과 1의 경우 자기 자신을 반환합니다.
            return n

		memo[n] = (fib(n-1) + fib(n-2)) % 1234567
        return memo[n]

    return fib(n)

 

n번째 피보나치 수를 계산하고, 그 결과를 1234567로 나눈 나머지를 반환합니다.
이 함수는 메모이제이션을 사용하여 효율적으로 피보나치 수를 계산합니다.

매개변수:
    - n: 계산할 n번째 피보나치 수입니다.

반환 값:
    - 1234567로 나눈 n번째 피보나치 수의 나머지입니다.

 

 

정답코드 3. DP (동적계획법)

 

def solution(n):
    # n까지의 피보나치 수를 저장하기 위한 리스트를 초기화합니다. 첫 두 피보나치 수는 0과 1입니다.
    fib = [0, 1]

    # 2부터 n까지 루프를 돌면서 모든 피보나치 수를 계산합니다.
    # 첫 두 피보나치 수는 이미 알고 있으므로 2부터 시작합니다.
    for i in range(2, n + 1):
        # 다음 피보나치 수는 앞선 두 수의 합입니다.
        # 문제의 요구사항에 맞게 큰 수를 다루기 위해 1234567로 나눈 나머지를 사용합니다.
        next_fib = (fib[i - 1] + fib[i - 2]) % 1234567

        # 계산된 피보나치 수를 리스트에 추가합니다.
        fib.append(next_fib)

    # 문제에서 요구하는 것은 n번째 피보나치 수입니다.
    # 'fib' 리스트는 0부터 시작하므로, n번째 피보나치 수는 인덱스 n에 위치합니다.
    return fib[n]