[백준 BOJ 1003번] 피보나치 함수

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

 

1. 문제

 

다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

• fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
• fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
• 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
• fibonacci(0)은 0을 출력하고, 0을 리턴한다.
• fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
• 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
• fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

---

2. 입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

3
0
1
3

2
6
22

---

3. 출력

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

1 0
0 1
1 2

5 8
10946 17711

---

4. 풀이

이 문제를 풀 때 Dynacmic Programming(DP) 알고리즘을 사용하였다. 크게 Bottom-Up / Top-Down 방법을 이용했다.

Top-Down은 큰 수, 즉 입력 받은 숫자부터 시작하므로 재귀를 이용해서 계속하여 이전의 재귀 함수들을 불러오는 방식이고, Bottom-Up은 제일 작은 수부터해서 내가 입력한 숫자까지 스택해나가면서 값을 찾아내는 방식이다.

중간 중간 필요없는 계산식이 없기에 두 방식 모두 시간 효율면에서는 비슷할 것으로 생각되었고, 풀이 면에서 다음과 같은 방식들을 생각했었다.

---

Top-Down

1. 이차원배열을 만들어서 [a][0]에는 a까지 계산 시 0 카운팅, [a][1]에는 a까지 계산 시 1 카운팅, [a][2]는 a번째 피보나치 수를 넣어주려고 하였다.

2. 피보나치 수는 결과값을 도출하는데에 있어서 전혀 필요치 않은 수이기에 [a][0]과 [a][1]만을 사용하기로 하였다. 초기 값으로 0과 1에 대한 0,1카운팅 값을 미리 할당해두고 시작하니 피보나치 함수에서 0,1을 고려하는 else-if 도입이 필요치 않아 편리하였다.

 

Bottom-Up

1. 0과 1부터 시작해서 n번째 수까지의 모든 0,1카운팅 값들을 더해나갔다.

---

 

이 문제를 풀면서 가장 중요한 건 DP 알고리즘의 가장 중요한 요소인 Memoization을 사용하는 것이었다.

 

Memoization 이란?

동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장(Memo)함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술.

 

-> 간단히 하자면 이전에 계산했던걸 메모해둘 배열에 적어두고 나중에 그값을 필요로 할 때 다시 계산치 않고 그 배열의 값을 바로 갖다 쓰는 것이다.

---

5. 소스코드

 

<Top-Down>

 

import java.io.*;

class Main{
    static Integer [][] memo;

    public static void main(String []args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int T = Integer.parseInt(br.readLine());
        for(int i=0; i<T; i++){
            int T_Case = Integer.parseInt(br.readLine());
            memo = new Integer [41][2];
            memo[0][0] = 1;
            memo[0][1] = 0;
            memo[1][0] = 0;
            memo[1][1] = 1;
            fibonacci(T_Case);
            System.out.println(memo[T_Case][0]+" "+memo[T_Case][1]);
        }
    }

    public static Integer[] fibonacci(int i){
        if(memo[i][0] == null || memo[i][1] == null){
            memo[i][0] = fibonacci(i-1)[0] + fibonacci(i-2)[0];
            memo[i][1] = fibonacci(i-1)[1] + fibonacci(i-2)[1];
        }
        return memo[i];
    }
}

 

<Bottom-Up>

 

import java.io.*;

class Main{
    static Integer [][] memo;

    public static void main(String []args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int [][] count = new int [41][2];
        int T = Integer.parseInt(br.readLine());
        for(int i=0; i<T; i++){
            
            int num = Integer.parseInt(br.readLine());
            count[0][0] = 1;
            count[0][1] = 0;
            count[1][0] = 0;
            count[1][1] = 1;

            for(int j=2; j<=num; j++){
                count[j][0] = count[j-1][0] + count[j-2][0];
                count[j][1] = count[j-1][1] + count[j-2][1];
            }
            System.out.println(count[num][0]+" "+count[num][1]);
        }
    }
}

 

---

6. 배운 것

이 문제를 풀이하다가 ArraysIndexOutOfBounds에러를 접하였다. 문제에 대해 찾다보니 초반에 입력하는 숫자 길이만큼의 2차원 배열을 형성했었는데 그것이 만약 1보다 작다면 초반에 초기값으로 주는 4줄의 할당 코드 부분에서 길이가 안되는 배열에 입력해 넣으려하기에 에러를 내는 것이었다. 초반에 길이를 동적으로 줄여주고 최대한 아끼는 것은 좋으나 만약 초기값 할당 부분이 있다면 그 부분을 고려해서 배열 크기를 할당해야겠다.