1. Algorithm : 피보나치 수열 & 다이나믹 프로그래밍

 

 

피보나치 수열이란? 

- 피보나치 수열은 이탈리아 수학자 레오나르도 피보나치가 발견한 수열이다. 

앞의 두수를 더해서 다음 수를 만들어가는 규칙을 가지고 있음. 

 

참고로 알고리즘을 할 때 해당 수학적 걔념이 많이 쓰인다

 

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

규칙을 자세히 보면:

• 0번째: 0
• 1번째: 1
• 2번째: 0 + 1 = 1
• 3번째: 1 + 1 = 2
• 4번째: 1 + 2 = 3
• 5번째: 2 + 3 = 5

수학적으로 표현하면: F(n) = F(n-1) + F(n-2)이다. 

 

피보나치 수열을 구현하는 3가지 방법

1. 반복문 방식(for문) - 가장 직관적이다. 

2. 재귀 방식 - 수학적 정의와 가장 유사하다. 

3. 다이나믹 프로그래밍 방식 - 가장 효율적이다. 

 

1. 반복문(for문) 방식

아이디어 : 처음부터 차례대로 계산. 

 

가장 직관적인 방법으로 0번째, 1번째부터 시작해서 원하는 숫자까지 차례대로 계산하는 방식이다. 

#include<iostream>
using namespace std;

int main()
{
    int n;
    cout << "수를 입력하시오" << endl;
    cin >> n;
    
    int a = 0, b = 1, c;
    
    if(n == 0)
    {
        cout << "피보나치 수열." << n << "번째 항 : " << a << endl;
    }
    else if (n == 1)
    {
        cout << "피보나치 수열." << n << "번째 항 : " << b << endl;
    }
    else
    {
        for(int i = 2; i <= n; i++)
        {
            c = a + b;
            a = b;
            b = c;
        }
        cout << "피보나치 수열 " << n << "번째 항 : " << c << endl;
    }
    return 0;
}

 

수를 입력하시오
10
피보나치 수열 10번째 항 : 55
Program ended with exit code: 0

 

성능 분석

• 시간복잡도: O(n) - n번 반복
• 공간복잡도: O(1) - 추가 메모리 거의 안씀
• 장점: 이해하기 쉽고, 메모리 효율적
• 단점: 큰 수에서는 여전히 오래 걸림

---

 

2.재귀(Recursive) 방식

수학적 정의 그대로 구현해보자.

피보나치의 수학적 정의 F(n) = F(n-1) + F(n-2)를 그대로 코드로 옮긴 방식이다. 

 

#include <iostream>
using namespace std;

// 재귀 함수로 피보나치 계산
int Pibo(int n) {
    if (n <= 1) return n; // 종료 조건 (Base Case)

    cout << "F(" << n << ") 계산 중..." << endl; // 호출 과정 확인용
    return Pibo(n - 1) + Pibo(n - 2);
}

int main() {
    int n;
    cout << "피보나치 수열의 몇 번째 항을 구할까요? ";
    cin >> n;

    cout << "계산 과정:" << endl;
    int result = Pibo(n);
    cout << "피보나치 수열 " << n << "번째 항: " << result << endl;

    return 0;
}

 

결과는 동일하다. 

 

핵심 개념

1. Base Case (종료 조건) : if ( n<= 1) return n;

- F(0) =0, F(1) = 1

- 이 조건이 없으면 무한으로 호출되어 스택오버 플로우가 발생한다. 

 

2. Recursive Case(재귀 호출) : return Pibo(n-1) + Pibo(n-2);

- 자기 자신을 더 작은 값으로 호출 

 

 

성능 분석

• 시간복잡도: O(2^n) - 지수적 증가 발생.
• 공간복잡도: O(n) - 재귀 호출 스택
• 장점: 코드가 수학적 정의와 일치, 이해하기 쉬움
• 단점: 매우 비효율적, 큰 n에서 실행 불가능
• 성능 비교시, 반복문 방식이 0.001초, 재귀 방식은 약 30초가 소요되므로 사실상 비효율적.

 

3. 다이나믹 프로그래밍(DP) 방식

- 아이디어 : 한번 계산한 값은 저장해두고 재사용하자. 

 

재귀 방식의 중복적인 계산 문제를 해결하는 방식이다.

이는 총 두가지의 접근법이 있다. 

 

3-1: 메모이제이션 (Top-Down)

- 재귀와 저장을 한꺼번에 진행

#include <iostream>
#include <vector>
using namespace std;

vector<int> memo(100, -1);  // -1: 아직 계산 안됨

int PiboMemo(int n) {
    if (n <= 1) return n;  // Base Case

    // 이미 계산했다면 저장된 값 반환
    if (memo[n] != -1) {
        cout << "F(" << n << ") 저장된 값 사용: " << memo[n] << endl;
        return memo[n];
    }

    // 처음 계산하는 경우
    cout << "F(" << n << ") 새로 계산 중..." << endl;
    memo[n] = PiboMemo(n - 1) + PiboMemo(n - 2);
    return memo[n];
}

int main() {
    int n;
    cout << "피보나치 수열의 몇 번째 항을 구할까요? ";
    cin >> n;

    int result = PiboMemo(n);
    cout << "피보나치 수열 " << n << "번째 항: " << result << endl;

    return 0;
}

메모이제이션 동작 과정

n=5일 때 계산 순서:

1. PiboMemo(5) 호출
2. PiboMemo(4) 호출 → 새로 계산
3. PiboMemo(3) 호출 → 새로 계산
4. PiboMemo(2) 호출 → 새로 계산
5. PiboMemo(1) 호출 → 1 반환
6. PiboMemo(0) 호출 → 0 반환
7. memo[2] = 1 저장
8. PiboMemo(1) 호출 → 1 반환 (이미 Base Case)
9. memo[3] = 2 저장
10. PiboMemo(2) 호출 → 저장된 값 2 사용
11. memo[4] = 3 저장
12. PiboMemo(3) 호출 → 저장된 값 2 사용

각 값은 단 한 번만 계산된다. 

 

3-2: 타뷸레이션 (Bottom-Up)

- 작은 것 부터 차례대로 계산해서 표를 채우자. 

 

#include <iostream>
#include <vector>
using namespace std;

int PiboTable(int n) {
    if (n <= 1) return n;

    vector<int> dp(n + 1);  // 피보나치 값을 저장할 테이블
    dp[0] = 0;  // F(0) = 0
    dp[1] = 1;  // F(1) = 1

    cout << "계산 과정:" << endl;
    cout << "dp[0] = " << dp[0] << endl;
    cout << "dp[1] = " << dp[1] << endl;

    // 작은 것부터 차례대로 계산
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
        cout << "dp[" << i << "] = dp[" << (i-1) << "] + dp[" << (i-2) << "] = "
             << dp[i-1] << " + " << dp[i-2] << " = " << dp[i] << endl;
    }

    return dp[n];
}

int main() {
    int n;
    cout << "피보나치 수열의 몇 번째 항을 구할까요? ";
    cin >> n;

    int result = PiboTable(n);
    cout << "피보나치 수열 " << n << "번째 항: " << result << endl;

    return 0;
}

 

 

타뷸레이션 동작 과정 (n=5)

i	dp[i-2]	dp[i-1]	dp[i] = dp[i-1] + dp[i-2]
2	dp[0]=0	dp[1]=1	dp[2] = 1 + 0 = 1
3	dp[1]=1	dp[2]=1	dp[3] = 1 + 1 = 2
4	dp[2]=1	dp[3]=2	dp[4] = 2 + 1 = 3
5	dp[3]=2	dp[4]=3	dp[5] = 3 + 2 = 5

 

 

3-3: 공간 최적화 버전

배열도 사용하지 않고 변수 두개로만 사용하는 방법

 

#include <iostream>
using namespace std;

int PiboOptimal(int n) {
    if (n <= 1) return n;

    int prev2 = 0;  // F(n-2)
    int prev1 = 1;  // F(n-1)
    int current;    // F(n)

    cout << "계산 과정:" << endl;
    cout << "F(0) = " << prev2 << endl;
    cout << "F(1) = " << prev1 << endl;

    for (int i = 2; i <= n; i++) {
        current = prev1 + prev2;  // F(n) = F(n-1) + F(n-2)
        cout << "F(" << i << ") = " << prev1 << " + " << prev2 << " = " << current << endl;

        // 다음 계산을 위해 값 이동
        prev2 = prev1;
        prev1 = current;
    }

    return current;
}

int main() {
    int n;
    cout << "피보나치 수열의 몇 번째 항을 구할까요? ";
    cin >> n;

    int result = PiboOptimal(n);
    cout << "피보나치 수열 " << n << "번째 항: " << result << endl;

    return 0;
}

 

다이나믹 프로그래밍의 핵심 개념

최적 부분 구조 (Optimal Substructure)

"큰 문제의 답이 작은 문제들의 답으로 구성될 수 있다"

피보나치에서: F(n) = F(n-1) + F(n-2)

중복 부분 문제 (Overlapping Subproblems)

"같은 작은 문제가 여러 번 나타난다"

피보나치에서: F(3)을 구할 때 F(2), F(1)이 반복 계산됨

메모이제이션 vs 타뷸레이션

메모이제이션	타뷸레이션
Top-Down	Bottom-Up
재귀 + 저장	반복문 + 테이블
필요한 것만 계산	모든 값을 순서대로 계산
함수 호출 오버헤드 있음	함수 호출 오버헤드 없음

 

마무리

핵심 정리

1. 피보나치 수열: F(n) = F(n-1) + F(n-2)
2. 반복문: 가장 실용적이고 효율적
3. 재귀: 직관적이지만 비효율적
4. DP: 중복 계산을 방지하여 효율성 극대화

학습 순서 추천

1. 반복문 방식부터 확실히 이해
2. 재귀 방식으로 재귀 개념 학습
3. 메모이제이션으로 DP 개념 도입
4. 타뷸레이션으로 DP 완전 정복