[프로그래머스] 피보나치 수

문제 설명

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.

예를들어

• F(2) = F(0) + F(1) = 0 + 1 = 1
• F(3) = F(1) + F(2) = 1 + 1 = 2
• F(4) = F(2) + F(3) = 1 + 2 = 3
• F(5) = F(3) + F(4) = 2 + 3 = 5

와 같이 이어집니다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

제한사항

• n은 1이상, 100000이하인 자연수입니다.

---

풀이

15분
별 생각없이 long long형으로 선언해두고, return 문에서만 mod연산을 해주어서 바로 제출하니 문제를 아예 틀렸다. 이 간단한 문제 풀이에서 뭐가 잘못된건지 고민을 잠깐 하다가, 계산 과정에서 오버플로우가 발생한다는 것을 알아차리고 고쳤다.
피보나치를 처음 배울 때 재귀를 이용하는 방법을 배우는데, 문제 조건을 봤을 때 딱 보아도 스택오버플로우가 발생할 것 같았다. 그런데 알고리즘 문제를 풀 때 재귀를 사용할지 결정하기 위해 가늠하는 방법이 궁금해서 찾아보았고, 꼬리 재귀 최적화라는 방법을 알게 되었다. 재귀 호출의 대표적인 예시인 factorial의 일반항을 보면,

int Factorial(int n){
	if (n == 1) return 1;
	return n * Factorial(n-1);
}

위와 같은 코드는 컴파일러는 다음과 같이 해석한다.

int Factorial(int n){
	if (n == 1) return 1;

	int result = Factorial(n - 1);
	return n * result;
}

이 때, 코드를 다음과 같이 바꾸어 주면 반환할 때 추가적인 연산이 필요하지 않게 되고,

int FactorialTail(int n, int acc){
	if (n == 1) return acc;
	return FactorialTail(n - 1, acc * n); 
}

int Factorial(int n){
	return FactorialTail(n, 1);
}

컴파일러는 이것을 인식하여 다음과 같이 해석해준다.

int FactorialTail(int n){
	int acc = 1;

	do{
		if (n == 1) return;
		acc = acc * n;
		n = n - 1;
	} while (true);
}

실제로 동작하는 것을 살펴보아도 스택을 한번만 호출하는데, 이 꼬리 재귀 개념을 사용하기 위해서는 컴파일러가 이 기능을 지원해주어야 한다.
그리고 처음 궁금했던

재귀는 몇 번까지 호출할 수 있을까

의 해답은, 파이썬 언어 같은 경우는 재귀함수 호출 횟수가 제한되어 있기도 하지만, 작성한 코드에 따라 스택에 올라가는 크기도 달라지므로 예측이 매우 어려우니 통상 1만번은 넘기지 않도록 어림잡는 방법이 있다고 한다.

코드

// 09:53 ~ 10:08
#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int pprev = 0, prev = 1, temp;
    
    for(int i = 0; i < n; ++i){
        temp = prev;
        prev = (pprev + prev) % 1234567;
        pprev = temp % 1234567;
    }
    
    return pprev;
}

꼬리 재귀 코드

#include <string>
#include <vector>

using namespace std;

int fibo(int n, int pprev, int prev){
    if(n == 0) return pprev;
    return fibo(n - 1, prev, (prev + pprev) % 1234567);
}

int fibo_tail(int n){
    return fibo(n, 0, 1);
}

int solution(int n) {
    return fibo_tail(n);
}