백준 1003번 피보나치 함수 :: 마이구미

이번 글은 백준 알고리즘 문제 1003번 "피보나치 함수"에 대해 다뤄본다.

피보나치 수는 너무도 대중적이기에 많이 들어보았으리라 생각한다.

' 0 1 1 2 3 5 8 13 21 34 55.......' 

일단 문제를 보자.

n번째 피보나치 수를 구하는 과정에서 

재귀를 통해 돌아갈 때 n이 0일 때와 1일 때의 경우가 얼마나 되는지 카운트를 구하는 문제이다.

먼저 순수한 방법으로 풀어보자.

위 그림에 있는 소스를 활용해서 0일때 1일때 카운트 변수 만들어서 if문 들어가면 ++해주면 된다.

이렇게 하더라도 사실상 원하는 결과값이 나온다.

알고리즘 문제에는 시간 제한이 있다.

그 말은 막 짜면 안되고, 문제가 원하는 로직은 꼭 존재한다.

그걸 캐치하여 최소한의 시간으로 돌아가도록 소스를 짜야한다. (속도를 고려하는 것은 결코 쉬운 것이 아니다.)

사람마다 생각하는 게 달라서 해결 방법은 다양할 것이다.

본인은 고민 끝에 규칙을 찾아냈다.

4번째 수를 찾는다면 fibonacci(3) + fibonacci(2) 가 돌아갈 것이다.

또한 fibonacci(3)는 fibonacci(2) + fibonacci(1)이 돌아갈 것이고,

fibonacci(2)는 fibonacci(1) + fibonacci(0)이 돌아갈 것이다.

그리고 fibonacci(2) 또한 fibonacci(1) + fibonacci(0)이 돌아갈 것이다.

색깔별로 잘 보길 바란다. 내가 무슨 말은 하고 있는건지 캐치하길 바란다.

이해를 돕기 위해 하나의 그림을 추가하겠다.

fib(1)은 n이 1일 때, fib(0)은 n이 0일때라는 것은 알 것이다.

벌써 뭔가 보인다면 Good. 

자세히 보자!

n이 5일 경우는 fib(0)이 3번이고, fib(1)이 5번 나온다. 

n이 6일 경우는 fib(0)이 5번이고, fib(1)은 8번 나온다.

n이 7일 경우는 fib(0)이 8번이고, fib(1)이 13번 나온다.

이러한 규칙이 존재한다.

' 0 1 1 2 3 5 8 13 21 34 55.......'  이게 피보나치 수라고 했었다.

그렇다.

결론은 n번째 수의 0이 나오는 경우의 수는 n-1번째 수이고 1이 나오는 경우의 수는 n번째 수이다.

바로 이해가 안 될 수 있다. 생각하지말고 직접 연필 잡고 해보길 바란다.

본인은 아래와 같이 코드를 작성했다.

void fibonaci(int n)
{
	int current=1;
	int last=0;
	int result=0;

	for(int i=0;i<n;i++)
	{
		last = current;
		current = result;

		result = last + current;		
	}
	
}

전체 소스는 Github을 통해 확인하길바란다.

백준 알고리즘 1003번 피보나치 함수 전체 소스 

https://github.com/hotehrud/acmicpc/blob/master/math/1003.java

피보나치 정의

https://ko.wikipedia.org/wiki/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98_%EC%88%98

백준 알고리즘 1003번 피보나치 함수

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