[BOJ] 2747. 피보나치 수 (Java)

문제 링크 / level: Bronze III

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

2747번: 피보나치 수

 

 

내가 생각한 풀이

사실 나는 다른 문제를 풀고 싶었지만, 그 문제를 내 힘으로 풀기 위해서는 여러 가지에 대한 공부가 필요할 것 같았다.

그 중 피보나치로 대표되는 재귀, 메모이제이션, 큰수(BigInteger) 등에 대해 공부하면서 BOJ에 있는 피보나치 수 시리즈를 전부 다 풀어볼 생각이다.

 

굉장히 흔히 알고있을 식이지만 공부하는 차원에서 한 번 더 적어보도록 하자.

*피보나치 수열: f(n) = f(n-1) + f(n-2)

 

문제의 핵심 (출처: BOJ)

BOJ의 피보나치 수 시리즈들 중 몇 개는 input으로 주어지는 n값의 최대 범위만 다르게 되어있다.

얼핏 보면 다 똑같이 풀면 될 것 같지만 입력되는 n값이 다르기 때문에 어떤 것은 재귀로만도 풀 수 있지만 어떤 문제는 (예를 들면, 지금 풀 문제^_^) 재귀함수로 구현하면 터져버려서 메모이제이션을 활용해야 통과할 수 있기도 하다.

 

생각해봅시다!

통상적으로 피보나치를 재귀함수로 구현하면 n이 40~50정도 사이일 때 터진다고 배웠다.

하지만 나는 호기심 많은 코린이니까 일단 재귀함수로 구현해보자!

응 터졌어~

 

흠 그렇다면 이 몸이 나설 차례인가?🤭

메모이제이션(memoization) 曰: 가즈아!!

성공!!

아니, 피보나치 수 시리즈 첫 문제부터 이렇게 메모이제이션을 사용해야하다니...😨

참고로 메모이제이션은 피보나치처럼 한 번 구한 값을 또 구하고, 또 구하느라 메모리와 시간 측면에서 매우 비효율적인 부분을 해결해주는 기법이다. memo라는 배열의 원소(전부 0으로 초기화 되어있다)을 활용해서 이미 구한 적 있는 값은 배열에 저장해뒀다가 필요할 때마다 새로 계산할 필요 없이 바로 꺼내서 쓰고, 만약 계산한 적 없다면 f(n) = f(n-1) + f(n-2) 공식을 이용해서 값을 구해주면 된다. 그리고? 당연히 새로 구한 이 값은 memo 배열에 업데이트 된다.

 

그리고 n=45만 되어도 터져버리니 변수는 long type을 사용하도록 하자.

(참고로 45번째 피보나치 수는 1134903170이다. 아, 이렇게 보니 아직은 int type의 범위를 벗어나지 않아서 int type으로 써도 되긴하겠다. 하지만 나는 그냥 마음 편하게 long type으로 딱!!)

// 핵심 코드
private static long fibo1(int n) {
	if(n<=1) {return n;}
	if(memo[n]!=0) {return memo[n];}
	else {
		return memo[n] = fibo1(n-1) + fibo1(n-2);
	}
}

피보나치를 메모이제이션으로 구현하는 방법에는 크게 두 가지 정도가 있는 것 같다.

하나는 내가 구현한 방법이고, 다른 하나는 재귀적인 요소(?)가 전혀 없이 그냥 배열에다가 쭉 저장하는 것. 후자는 나도 구현을 직접 제대로 해본 적이 없기 때문에 다음에 직접 구현해서 비교를 한 번 해봐야겠다.

 

 

- 피보나치 수 시리즈는 계속된다, to be continued... -