[백준] 1003 -피보나치 함수 JAVA

Solved.ac Class 완전정복 프로젝트

Class : 3 ~ 3 ++

 

---

링크

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

1003번: 피보나치 함수

문제

다음 소스는 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이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

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

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

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

접근방법

 피보나치 N이 사용하는 0과 1의 개수를 출력하는 문제이다. 일반적으로 피보나치는 재귀 함수를 사용하지만, 문제의 제한 시간이 1초도 되지 않는다.(0.25초) 때문에 재귀 함수를 이용한다면, 수가 늘어날수록 급격한 호출 횟수에 시간이 오래 걸릴 수밖에 없다. 그렇기에 DP를 이용하여 문제를 해결해야 한다. 이 정도 감을 잡고 풀이로 들어가자.

풀이

 DP란 요즘 넷플릭스에서 핫한 군대 이슈를 다룬 드라마다. DP(Dynamic Programming)이란, 복잡한 문제를 나누어 정복하는(Divide & Conquer) 방법을 말한다. 분할 정복만 한다면, 사실 재귀 함수의 역할과 크게 차이가 없을 것이다. 그러나 DP는 메모 이제이 션(memoization)을 이용한다는 특징이 있다. 메모이제이션이란, 메모리에 계산된 값을 저장해 다음 반복을 수행 시 이용하는 것을 말한다. 쉽게 말해, 메모리를 사용하여, 반복 연산의 속도를 줄이는 방법이다.

 

 DP를 이용해 어떻게 풀 것인가?

피보나치의 반복 패턴은 이전과 그 이전 피보나치의 합이다. 이것을 수식으로 표현하면 다음과 같다.

 

fibonacci(N) = fibonacci(N-1) +  fibonacci(N-2)

 

 이전까지 이런 문제들에 대해 재귀 함수를 이용하여 풀었다면, DP는 배열을 이용하여 다음과 같이 사용한다.

 

DP [N] = DP [N-1] + DP [N-2]

 

 배열에 직접 저장하여 이용하므로, N=0 or N=1 때까지 함수를 호출할 필요 없이, 이전 데이터만으로 표현이 가능해진 것이다.

 

코드

 해당 문제에 대해 2가지 방법을 제시한다.

 

1. DP를 이용한 풀이

 나는 0과 1을 나누는 것이 귀찮아서, Pair 클래스를 정의하여 한번에 해결했다. (물론 엄청나게 메모리 낭비를 한 듯하다 -_-;) 

 두 개의 자료형을 갖는 Pair 객체를 정의하였고, 왼쪽에는 0의 개수, 오른쪽에는 1의 개수만 넣어가며, 진행했다.

 

import java.util.Scanner;

public class Main {


    public static void main(String[] args) {
        Main test = new Main();
    }

    public Main() {

        //left : 0 right : 1
        Pair<Integer, Integer>[] dp = new Pair[41];
        dp[0] = new Pair<>(1, 0);
        dp[1] = new Pair<>(0, 1);

        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        int tc = sc.nextInt();
        for (int i = 0; i < tc; i++) {
            int target = sc.nextInt();

            Pair<Integer, Integer> result = solution(dp, target);
            sb.append(result.left + " " + result.right + "\n");
        }

        System.out.println(sb);


    }

    public Pair<Integer, Integer> solution(Pair<Integer, Integer>[] dp, int target) {
        for (int i = 2; i <= target; i++) {
            if (dp[i] != null) {
                continue;
            }
            //왼쪽(0)과 오른쪽(1)을 나누어 계산
            int zero = dp[i - 1].left + dp[i - 2].left;
            int right = dp[i - 1].right + dp[i - 2].right;
            dp[i] = new Pair<>(zero, right);
        }


        return dp[target];
    }


    class Pair<L, R> {
        L left;
        R right;

        public Pair(L left, R right) {
            this.left = left;
            this.right = right;
        }
    }

}

 

 

2. 반복문을 이용한 풀이

 문제에서 요구하는 방법은 아니라고 생각한다. ST-LAB 블로거님의 자료를 보니 피보나치를 이런 식으로도 푸는 게 가능했다.

 

 0과 1의 횟수를 표로 나타내면 아래와 같다. 

 표를 자세히 보면 특징을 아래와 같이 정리할 수 있다.

 

DP [N] 0  : DP [N-1] 1 값 

DP [N] 1 : DP [N-1] 0 값 + DP [N-1] 1 값

 

 이를 이용한 코드가 아래의 코드이다. 엄연히 이것은 메모이제이션을 이용하는 방법은 아니다. 1회 입력에 대하여, 하나의 메모리를 지속적으로 수정하여 이용하지만, 각 tc마다 다시 계산해야 한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {


    public static void main(String[] args) throws IOException {
        Main test = new Main();
    }

    public Main() throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int tc = Integer.parseInt(br.readLine());

        int one = 0;
        int zero = 1;

        for (int i = 0; i < tc; i++) {
            int target = Integer.parseInt(br.readLine());

            int[] result = solution3(one, zero, target);
            sb.append(result[0] + " " + result[1] + "\n");
        }
        System.out.println(sb);
    }
    
     private int[] solution3(int one, int zero, int target) {


        int plus_data = one + zero;
        for (int i = 0; i < target; i++) {
            zero = one;
            one = plus_data;
            plus_data = one + zero;
        }

        return new int[]{zero, one};
    }
}

 

 

결과

 

33191687 - 2번을 이용

33191578 - int형 배열을 이용 1번과 같은 로직

33191387 - 1번 방법 이용

 

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.