백준 24416번: 알고리즘 수업 - 피보나치 수 1 (Python)

백준 문제번호 24416번 문제명: 알고리즘 수업 - 피보나치 수 1 (Python)

문제 설명

문제

오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있습니다. 아버지가 수업한 내용을 학생들이 잘 이해했는지 확인하기 위해 문제를 풀어봅니다.

주어진 n에 대해 재귀 호출과 동적 계획법(DP) 두 가지 방법으로 피보나치 수를 계산합니다. 각 방법이 실행된 횟수를 출력합니다.

테스트케이스 예시

입력: 5
출력: 5 3
(재귀는 if문을 5번 검사했고, DP는 덧셈을 3번 수행함)

입력: 30
출력: 832040 28

아이디어

1. 재귀 함수를 만들어 n==1 or n==2 조건이 몇 번 실행되는지 센다.
2. 동적 계획법 함수를 만들어 배열에 값을 저장하며 덧셈이 몇 번 일어나는지 센다.

전체코드

def fib(n):
    global cnt1
    if n == 1 or n == 2:
        cnt1 += 1
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

def fibonacci(n):
    global cnt2
    f = [0] * (n + 1)
    f[1] = 1
    f[2] = 1
    for i in range(3, n + 1):
        f[i] = f[i - 1] + f[i - 2]
        cnt2 += 1

cnt1 = 0
cnt2 = 0
N = int(input())
fib(N)
fibonacci(N)
print(f"{cnt1} {cnt2}")

개별코드 설명

재귀 함수

def fib(n):
    global cnt1
    if n == 1 or n == 2:
        cnt1 += 1
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

fib(n)이라는 함수가 호출됩니다.
n==1 또는 n==2가 되면 cnt1을 1 증가시킵니다.
그렇지 않으면 fib(n-1)과 fib(n-2)를 각각 다시 호출합니다.
특징: 같은 계산을 반복하므로 실행 횟수가 매우 많습니다.

DP 함수

def fibonacci(n):
    global cnt2
    f = [0] * (n + 1)
    f[1] = 1
    f[2] = 1
    for i in range(3, n + 1):
        f[i] = f[i - 1] + f[i - 2]
        cnt2 += 1

fibonacci(n)이라는 함수가 호출됩니다.
배열 f를 만들어 f[1]과 f[2]를 1로 초기화합니다.
i=3부터 n까지 반복하면서 f[i]=f[i-1]+f[i-2]로 계산합니다.
덧셈이 일어날 때마다 cnt2를 1 증가시킵니다.
특징: 같은 계산을 하지 않고, 매우 효율적입니다.

구체적인 실행 예시

입력값: 5

fib(5) 호출:
fib(5) → fib(4)+fib(3) → fib(3)+fib(2)+fib(2)+fib(1)
if문 조건 검사 총 5회

fibonacci(5) 호출:
i=3, i=4, i=5에서 덧셈이 총 3회

출력:

5 3

입력값: 30

fib(30) 호출:
if문 조건 검사 총 832040회

fibonacci(30) 호출:
덧셈이 총 28회

출력:

832040 28

결론

• 재귀 함수 방식은 매우 비효율적이며, 같은 계산을 반복하기 때문에 실행 횟수가 기하급수적으로 많아집니다.
• 동적 계획법(DP) 방식은 이전에 계산한 값을 저장하여 불필요한 계산을 없애고, 실행 횟수를 최소화합니다.
• 입력값이 커질수록 두 방식의 차이는 극적으로 벌어지며, DP 방식의 효율성이 돋보입니다.
• 알고리즘 문제를 풀 때는 단순히 결과만 구하는 것이 아니라, 어떤 방법이 더 효율적인지 고려하는 습관이 중요합니다.