백준 1003번 피보나치 함수 (JavaScript 풀이)

[백준 1003] 피보나치 함수 - 동적 프로그래밍

📖 동적 프로그래밍(DP)이란?

정의: 중복되는 부분 문제를 한 번만 계산하고 저장해서 재사용하는 알고리즘
특징: 같은 계산을 반복하지 않음 (메모이제이션)
핵심: "이미 계산한 건 다시 계산하지 말자!"

재귀 vs DP 비교

일반 재귀: fibonacci(5) → fibonacci(4) + fibonacci(3)
                         → fibonacci(3) + fibonacci(2) + fibonacci(2) + fibonacci(1)
                         → 같은 계산을 계속 반복! (비효율적)

DP: fibonacci(0), fibonacci(1) 계산 → 저장
    fibonacci(2) = fibonacci(1) + fibonacci(0) → 저장된 값 사용
    fibonacci(3) = fibonacci(2) + fibonacci(1) → 저장된 값 사용
    ...

DP를 쓸 수 있는 조건

1. 최적 부분 구조: 큰 문제를 작은 문제들로 나눌 수 있음
2. 중복되는 부분 문제: 같은 계산이 여러 번 반복됨

---

📌 문제 요약
재귀적으로 구현된 피보나치 함수에서 fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 문제.

입력: T (테스트 케이스 개수), 각 줄마다 N (0 ≤ N ≤ 40)
출력: 각 N에 대해 0이 출력되는 횟수와 1이 출력되는 횟수

출처: https://www.acmicpc.net/problem/1003

---

💡 문제 접근

fibonacci(3) 호출 과정 그림으로 이해하기

                fibonacci(3)
                     |
          fibonacci(2) + fibonacci(1)
               |              |
    fibonacci(1) + fibonacci(0)   print('1')
         |              |
    print('1')     print('0')

 

  출력 결과 세어보기:

• 1️⃣ fibonacci(1) 호출 → '1' 출력
• 2️⃣ fibonacci(0) 호출 → '0' 출력
• 3️⃣ fibonacci(1) 호출 → '1' 출력 (또!!)

  최종 결과: 0이 1번, 1이 2번 출력 → 답: 1 2

---

작은 것부터 천천히 분석

🟢 fibonacci(0):

→ 그냥 '0' 출력하고 끝
→ 0: 1번, 1: 0번

 

🔵 fibonacci(1):

→ 그냥 '1' 출력하고 끝
→ 0: 0번, 1: 1번

 

🟡 fibonacci(2):

fibonacci(2)
     |
fibonacci(1) + fibonacci(0)
     |              |
print('1')    print('0')
→ 0: 1번, 1: 1번

 

🔴 fibonacci(3): (위에서 본 것처럼)

→ 0: 1번, 1: 2번

---

패턴 발견!

정리표:

n | 0의 횟수 | 1의 횟수
--|---------|----------
0 |    1    |    0
1 |    0    |    1
2 |    1    |    1
3 |    1    |    2
4 |    2    |    3
5 |    3    |    5

패턴:

• 0의 횟수: 1, 0, 1, 1, 2, 3, 5...
• 1의 횟수: 0, 1, 1, 2, 3, 5, 8...
• 공식: count[n] = count[n-1] + count[n-2] (앞의 두 개를 더하면 다음!)

---

📝 풀이 코드 (JavaScript)

const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim().split('\n');

const T = +input[0];

// 0과 1이 몇 번 출력되는지 저장하는 배열
let count0 = [1, 0]; // [n=0일때, n=1일때]
let count1 = [0, 1]; // [n=0일때, n=1일때]

// n=2부터 n=40까지 패턴으로 계산
for (let i = 2; i <= 40; i++) {
    count0[i] = count0[i-1] + count0[i-2];
    count1[i] = count1[i-1] + count1[i-2];
}

// 테스트 케이스마다 답 출력
for (let i = 1; i <= T; i++) {
    const n = +input[i];
    console.log(count0[n], count1[n]);
}

---

🔎 풀이 해설

단계별 실행 과정:

시작값 설정: count0 = [1, 0] → fibonacci(0)에서 0이 1번, fibonacci(1)에서 0이 0번 count1 = [0, 1] → fibonacci(0)에서 1이 0번, fibonacci(1)에서 1이 1번 패턴으로 계속 계산: count0[2] = count0[1] + count0[0] = 0 + 1 = 1 count1[2] = count1[1] + count1[0] = 1 + 0 = 1 count0[3] = count0[2] + count0[1] = 1 + 0 = 1 count1[3] = count1[2] + count1[1] = 1 + 1 = 2 답 출력: N이 주어지면 count0[N] count1[N] 출력

효율성:

• 시간복잡도: O(N) - 한 번만 계산
• 공간복잡도: O(N) - 배열 2개 사용
• 재귀 대비: O(2^N) → O(N)로 대폭 개선!

---

💭 내 생각

• 처음엔 "출력 횟수를 어떻게 세지?" 했는데, 그림 그려보니 이해됨!
• fibonacci(3) 그림에서 fibonacci(1)이 2번 나오는 게 핵심이었음
• "패턴도 피보나치네?" 하고 깨달았을 때 소름! 수학은 정말 신기해
• DP = "똑같은 계산 두 번 하지 말기" 이렇게 이해하니 쉬워짐

---

📚 배운 점

• 그림의 중요성: 복잡한 재귀 호출도 그림으로 그리면 한눈에 이해됨
• 패턴 인식: 작은 예시부터 차례로 계산하면 규칙이 보임
• 메모이제이션: 계산 결과를 저장해서 재사용하는 DP의 핵심 아이디어
• 전처리 효과: 미리 계산해두면 여러 테스트케이스를 빠르게 처리 가능
• 시간복잡도 개선: 지수적 → 선형적으로 극적인 성능 향상