<프로그래머스 C++> 피보나치 수 풀이(재귀 함수)

문제

F(0) = 0

F(1) = 1 일때 F(n) = F(n-1) + (n-2)인 피보나치 수열에서 n번째 수를 1234567로 나눈 나머지를 return하는 문제이다.

---

풀이 아이디어

처음엔 재귀함수로 접근했다.

int Fib(int n) {
    if(n < 2) return n;
    return Fib(n-1) + Fib(n-2);
}

재귀 방식은 구현이 직관적이라서 사용하기 좋지만 시간복잡도가 O(2^n)이라 n이 커질수록 급격히 느려진다.

Fib(5)만 호출해도 Fib(3)이 2번 Fib(2)가 3번이 중복 호출되어 매우 비효율적이다.

Fib(5)
├── Fib(4)
│   ├── Fib(3)  ← 중복
│   └── Fib(2)  ← 중복
└── Fib(3)      ← 중복
    └── Fib(2)  ← 중복

n이 최대 100,000인 이 문제에서 재귀함수를 쓰면 시간 초과가 발생할 수 있다. 

그래서 반복문으로 바꿔 O(n)으로 해결하려고 한다.

---

문제 풀이

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

int Fib(int n)
{
    if(n < 2) return n;
    int a = 0, b = 1;
    for(int i = 2; i <= n; ++i)
    {
        int c = (a + b) % 1234567;
        a = b;
        b = c;
    }
    return b % 1234567;
}

int solution(int n) {
    return Fib(n);
}

---

나머지를 매번 나누는 이유?

문제에서는 "n번째 피보나치 수를 1234567로 나눈 나머지를 return" 하라고 했다.

그래서 처음엔 n번째 수까지 피보나치를 적용한 후 마지막에 나눈 수를 return했다. 

하지만 이렇게 되면 오버플로우가 발생하게 된다.

 

n = 100,000일 때 피보나치수는 천문학적으로 커져 int는 물론, long long으로도 표현이 불가능한 숫자가 된다.

중간 계산 값이 범위를 넘어버리면 이미 틀린 값이 되어버려 오답이 된다.

 

수학적으로

(a + b) % m = ((a % m) + (b % m)) % m

이 성립하기 때문에 매번 나눠도 최종 결과가 동일하다.

 

// 마지막에 한 번만 나누면
Fib(100000) = 천문학적으로 큰 수 → overflow → 오답

// 매번 나누면
c = (a + b) % 1234567  // 매 반복시 1234567 미만으로 유지 → 정답

---

코드 흐름

1. 초기값 설정

int a = 0, b = 1;

재귀함수 기준 a는 F(n-2), b는 F(n-1)을 의미한다.

재귀 함수의 조건 중 하나인 명확한 이탈 조건을 명시해야 하기 때문에 시작값인 F(0) = 0과 F(1) = 1로 초기화해준다.

 

2. 반복문으로 피보나치 계산

for(int i = 2; i <= n; ++i)
{
    int c = (a + b) % 1234567;
    a = b;
    b = c;
}

매 반복마다 세 변수가 한 칸씩 앞으로 당겨진다.

 

변수	역할
a	F(n-2)
b	F(n-1)
c	F(n) = a + b

 

예시로 Fib(5)라고 했을 때,

초기: a=0(F0), b=1(F1)

i=2: c = a+b = 0+1 = 1           → a=b=1,  b=c=1   // a=F(1), b=F(2)
i=3: c = a+b = 1+1 = 2           → a=b=1,  b=c=2   // a=F(2), b=F(3)
i=4: c = a+b = 1+2 = 3           → a=b=2,  b=c=3   // a=F(3), b=F(4)
i=5: c = a+b = 2+3 = 5           → a=b=3,  b=c=5   // a=F(4), b=F(5)

return b = 5

매 반복마다 a → b → c 순서로 한 칸씩 앞으로 당겨지는 구조이다.

c를 먼저 계산한 뒤 a=b, b=c 순서로 대입해야 한다. 순서가 바뀌면 a가 덮어씌워져서 c계산이 틀어진다.

 

3. 결과 반환

return b % 1234567;

최종 결과도 한 번 더 나눠서 반환한다.

---

트러블슈팅

나머지 연산을 조건부로만 적용해서 몇 개의 케이스에서 오류가 났다.

 

처음 코드

if(a > 1234567)
{
    a %= 1234567;
    b %= 1234567;
}
int c = a + b;

여기서 두 가지 문제가 있었다.

 

 

문제 1 - 조건이 틀림

 

a > 1234567 일 때만 나머지 연산을 하게 되면, a가 1234566, b가 그보다 더 큰 수이면 더했을 때 범위를 벗어나게 되어 매번 나눠주는 것이 좋다.

 

문제 2 - 나누는 시점이 늦다.

// a와 b를 먼저 나누고
a %= 1234567;
b %= 1234567;
// 그 다음 더함
int c = a + b;  // 여기서도 overflow 가능

a와 b를 따로따로 나눠도 더하는 순간 다시 범위를 넘을 수 있었다.

덧셈과 나머지 연산을 동시에 처리해야 한다.

int c = (a + b) % 1234567;

---

핵심포인트

 

• 재귀 방식은 O(2^n)으로 n이 클 때 시간 초과가 발생한다. 반복문으로 O(n)으로 줄인다
• (a + b) % m = ((a % m) + (b % m)) % m이 성립하므로 매번 나눠도 최종 결과가 동일하다
• 매번 나머지 연산을 적용해 overflow를 방지한다