[백준][JAVA알고리즘]1003번 풀이(피보나치 함수) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 1003번 풀이입니다. 

* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 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이 출력되는 횟수를 공백으로 구분해서 출력한다.

제한

시간제한 : 0.25초

메모리 제한

입력 예시

3
0
1
3

출력 예시

1 0
0 1
1 2

실패 코드

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

public class Main {
	
	static int zero_count = 0;
	static int one_count = 0;
	static int N = 0;
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		for(int i = 0 ; i < N ; i++) {
		fibonacci(Integer.parseInt(br.readLine()));
		sb.append(zero_count).append(" ").append(one_count).append("\n");
		zero_count=0; one_count=0;
		}
		System.out.println(sb);
}
	public static void fibonacci(int n) {
		if(n==0) {
			zero_count++;
		} else if(n== 1) {
			one_count++;
		} else if(n < 0) return;
		else {
			fibonacci(n-1);
			fibonacci(n-2);
		}
	}
}

간단히 실패했습니다. 혹시나 하고 해 봤는데 역시나 ㅎㅎ 시간 초과로 실패했습니다. 그냥 일반적인 재귀 방법이죠. 그러나 해당 문제에서 원하는 것은 큰 수를 넣어도 빠르게 풀 수 있는 방법을 원하기 때문입니다!

 

이에 따라 저희는 또 다른 기술을 찾으러 가야 합니다... ㅎㅎ

 

성공 코드

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

public class Main {
	
	static int zero_count = 0;
	static int one_count = 0;
	static int N = 0;
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());

		for(int i = 0 ; i < N ; i++) {
		fibonacci(Integer.parseInt(br.readLine()));
		sb.append(zero_count).append(" ").append(one_count).append("\n");
		zero_count=0; one_count=0;
		}
		System.out.println(sb);
}
	public static void fibonacci(int n) {
		
		int temp1 = 0;
		int temp2 = 1;
		int temp = 0;

		if(n==0) {
			zero_count++;
			return;
		} else if(n== 1) {
			one_count++;
			return;
		} else if(n < 0) return;
		else {
			for(int i = 1 ; i < n ; i++) {
				temp = temp1 + temp2;
				temp1 = temp2;
				temp2 = temp;
			}
			zero_count = temp1;
			one_count = temp2;
		}
	}
}

해당 피보나치 함수 알고리즘은 일반 재귀 방법으로는 시간 초과가 나기 때문에 따른 방식을 강구해야 합니다. 메모 제이 션 방법이나 FOR문으로 바꿔주는 형식이죠. 해당 방식을 아주 쉽게 풀이할 수 있는 방법을 알려드리겠습니다. STEP으로 GO GO

---

알고리즘 흐름도

입력받기 -> 받은 입력 피보나치 구하기 -> 출력

---

STEP1 입력받기

		for(int i = 0 ; i < N ; i++) {
		fibonacci(Integer.parseInt(br.readLine()));
		sb.append(zero_count).append(" ").append(one_count).append("\n");
		zero_count=0; one_count=0;
		}

입력받기는 입력 예제를 보면 쉽게 이해할 수 있죠. 처음 받은 입력으로 반복문을 돌리면서

받은 입력을 fibonacci에 넣어주면 끝!

나온 결과인 zero_count와 one_count를 stringbuilder에 저장해준 뒤 초기화해주면 됩니다.

 

 * 초기화하는 이유는 다음 반복문에는 다시 0부터 세줘야 하기 때문이죠~

---

STEP2 피보나치 구하기(패턴 찾기)

이번 알고리즘의 핵심입니다. 0과 1이 호출되는 것을 카운트하기 위해서는 그 규칙을 알아야 합니다. 간단합니다. 시중에 떠돌아다니는 아무 피보나치 관련 코드를 가져옵니다. 제거 실패 코드를 사용하셔도 되고요.

 

문제에서 준 코드를 사용해도 되죠 그리고 돌려보세요 ㅎ

 

15
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14		//입력끝
1 0		//결과
0 1
1 1
1 2
2 3
3 5
5 8
8 13
13 21
21 34
34 55
55 89
89 144
144 233
233 377

이런 식으로요~!  결과는 1 0이 출력된 곳부터고요 그 위는 입력입니다.

 

자 0을 살펴보면 1 0 1 1 2 3 5 8 13 21....

다음 1을 살펴보면 0 1 1 2 3 5 8 13 21....

보이시나요? 이것 또한 피보나치수열인 것을 알 수 있죠! 물론 가장 처음인 0과 1을 제외하면 말이죠

 

그렇다면 점점 어떻게 풀어야 할지 감이 오시나요?? 이런 규칙성을 기억하시고 STEP 3로 넘어가 보죠

---

STEP 3 피보나치 구하기 (피보나치 구현하기)

우선 예외 상황을 처리해 줘야 합니다. 앞서 0과 1일 때 이후에는 피보나치 수로 나열되는 것을 볼 수 있었죠. 이에 따라 0과 1일 때만 처리해 줍니다.

 

public static void fibonacci(int n) {
		if(n==0) {
			zero_count++;
			return;
		} else if(n== 1) {
			one_count++;
			return;
		} else if(n < 0) return;
		
	}

0일 때는 0 카운트만 올려주고 해당 함수를 return 해주어 종료!

1일 때는 1 카운트만 올려주고 해당 함수를 return 해주어 종료!

 

마지막으로 0보다 작은 값이 나오면 그냥 종료!

간단하죠??

 

가장 핵심인 이제 그 이외의 값을 처리해 주겠습니다. 여기서 핵심은 피보나치수열을 재귀가 아닌 for문을 이용해야 한다는 것이지요! 물론 메모제이션을 사용하여 풀이하셔도 될 거라고 봐요 (해보진 않았습니다.. ㅎㅎ)

 

public static void fibonacci(int n) {
		
		int temp1 = 0;
		int temp2 = 1;
		int temp = 0;

		if(n==0) {
			zero_count++;
			return;
		} else if(n== 1) {
			one_count++;
			return;
		} else if(n < 0) return;
		else {
			for(int i = 1 ; i < n ; i++) {
				temp = temp1 + temp2;
				temp1 = temp2;
				temp2 = temp;
			}
			zero_count = temp1;
			one_count = temp2;
		}
	}

일단 변수 temp, temp1, temp2를 설정해 줍니다. 왜 0 1 0이 되느냐?

temp1은 첫 번째 수

temp2는 두 번째 수

temp는 temp1과 temp2를 더한 결과를 담기 위한 변수이지요

 

반복문을 n만큼 반복해 줍니다. 물론 i는 1부터지요

 

i가 1일 때

temp에 temp1 + temp2를 더해줍니다 그러면 1이 되겠죠? => temp = 1

temp1 = temp2  => temp1 = 1

temp2 = temp  => temp2 = 1

 

i가 2일 때

temp = 2

temp1 = 1

temp2 = 2

이런 식으로 형성되죠 이제 눈에 보이시나요?

 

i가 3일 때

temp = 3

temp1 = 2

temp2 =3

 

i가 4 일대

temp = 5

temp1 = 2

temp2 =5

 

네 temp1이 (n-2) temp2가 (n-1) 역할을 하여 다음 반복문 처음에 temp에 그다음 값을 넣어줍니다.

 

그렇다면 해당 앞서 STEP2에서 살펴보았던 0과 1의 카운터를 보시면 뒤에 있는 값이 0 앞 에이 쓴 값이 1이 되겠죠.

 

쉽게 말해서 zero_count = temp1이 들어가고 one_count = temp2가 들어가면 원하는 결과 값이 나오게 됩니다.

 

여기서 temp들 초기에 왜 010으로 설정하고 왜 for문이 1로 시작하시는지 의문이 드시는 분이 있으실 겁니다.

 

두게 가 연관되어 있기 때문입니다. temp1, temp2를 11로 설정하시고 for문의 i의 초기값을 바꿔주셔도 충분히 풀이하실 수 있습니다 ㅎㅎ

 

사실 그런 문제는 값을 뭐로 설정하는지는 자신 마음이기 때문이죠 참고해주세요