[class1]백준 10870번(피보나치 수 5) - 코딩테스트 23일차(2025.02.13)

문제유형

재귀 함수

풀이 방법 도출 과정

1. 피보나치 수는 n = (n-1) + (n+1)의 형태를 띄고 있다.

2. 이런 경우 재귀함수를 쓰게 되면 간단하게 풀수가 있을 것이다.

3. 이를 이용하여 문제를 풀어보도록 하겠다. 

시간 복잡도

입력 받기 O(1)

재귀함수 O(2^n)

총 O(2^n)이 시간 복잡도이다

코드 및 간단설명

재귀함수를 사용하여 문제를 풀었다. 

def ponachi_num(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return ponachi_num(n-1) + ponachi_num(n-2)

n = int(input())
print(ponachi_num(n))

다른 풀이

1) 메모이제이션을 사용하는 재귀 구현

메모이제이션은 이미 계산한 결과를 저장해 두었다가 재사용하는 방식이다.
이를 통해 중복 계산을 피하고 시간 복잡도를 O(n)으로 줄일 수 있다.

def ponachi_num(n, memo={}):
    if n in memo:
        return memo[n]
    if n == 0:
        return 0
    if n == 1:
        return 1
    memo[n] = ponachi_num(n-1, memo) + ponachi_num(n-2, memo)
    return memo[n]

n = int(input())
print(ponachi_num(n))

 

 

설명:

• memo 딕셔너리에 이미 계산된 피보나치 값을 저장한다.
• 매 재귀 호출 전에 memo에 값이 있는지 확인하고, 있다면 바로 반환한다.
• 이렇게 하면 같은 값에 대해 여러 번 재귀 호출하는 일을 방지할 수 있다.

2) 반복문을 이용한 효율적인 구현

이 방법은 두 개의 변수만 사용하여 반복문으로 피보나치 수열을 구하는 방법이다.
이 방식은 O(n) 시간에 O(1) 공간 복잡도를 가진다.

def ponachi_num(n):
    if n == 0:
        return 0
    a, b = 0, 1
    for i in range(2, n+1):
        a, b = b, a + b
    return b

n = int(input())
print(ponachi_num(n))

 

설명:

• 초기값으로 a = 0, b = 1을 설정한다.
• 2부터 n까지 반복하면서, a와 b를 업데이트한다.
• 각 단계에서 b는 현재 피보나치 수가 되고, a는 바로 이전 값이 된다.
• 최종적으로 b를 반환하면 n번째 피보나치 수를 얻을 수 있다.