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

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

문제 설명

문제

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

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

테스트케이스 예시

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

입력: 30
출력: 832040 28

아이디어

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

전체코드

#include 

using namespace std;

int cnt1 = 0, cnt2 = 0;
int arr[41];
int fib(int n)
{
    if (n == 1 || n == 2)
    {
        cnt1++;
        return 1;
    }
    else
        return fib(n - 1) + fib(n - 2);
}

void fibonacci(int n)
{
    arr[1] = 1;
    arr[2] = 1;

    for (int i = 3; i <= n; i++)
    {
        arr[i] = arr[i - 1] + arr[i - 2];
        cnt2++;
    }
}

int main(void)
{
    int N;
    cin >> N;
    fib(N);
    fibonacci(N);
    cout << cnt1 << " " << cnt2 << endl;
    return 0;
}

개별코드 설명

재귀 함수

int fib(int n)
{
    if (n == 1 || n == 2)
    {
        cnt1++;
        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 함수

void fibonacci(int n)
{
    arr[1] = 1;
    arr[2] = 1;

    for (int i = 3; i <= n; i++)
    {
        arr[i] = arr[i - 1] + arr[i - 2];
        cnt2++;
    }
}

fibonacci(n)이라는 함수가 호출됩니다.
배열 arr를 만들어 arr[1]과 arr[2]를 1로 초기화합니다.
i=3부터 n까지 반복하면서 arr[i]=arr[i-1]+arr[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 방식의 효율성이 돋보입니다.
• 알고리즘 문제를 풀 때는 단순히 결과만 구하는 것이 아니라, 어떤 방법이 더 효율적인지 고려하는 습관이 중요합니다.