C++ 피보나치 함수 문제 풀기 (백준 1003)

읽어주셔서 감사합니다. 오늘은 백준의 1003번, 피보나치 함수 문제에 대해 풀어보도록 하겠습니다.

 

---

코드

아래 내용은 수학적인 내용을 다량 함유하고 있습니다. 사실상 수학적인 내용을 제외하면 일반적인 초보자가 짤 수 있는 수준의 코드이지요. 수학적 내용은 아래에서 설명하겠습니다.

#include <iostream>
#include <algorithm>

using namespace std;


static pair<int, int> mem[41];

pair<int, int> fibo(int n) {
	pair<int, int> F, S;
	if (mem[n] != make_pair(0, 0))
		return mem[n];
	if (n == 0)
		return make_pair(1, 0);
	else if (n == 1)
		return make_pair(0, 1);
	else {
		F = fibo(n - 2);
		S = fibo(n - 1);
		return mem[n] = make_pair(F.first + S.first, F.second + S.second);
	}
}

int main(void) {
	int T, N;
	pair<int, int> A;
	cin >> T;
	for (int i = 0; i < 41; i++) {
		mem[i] = make_pair(0, 0);
	}
	for (int i = 0; i < T; i++) {
		cin >> N;
		A = fibo(N);
		cout << A.first << " " << A.second << endl;
	}
	return 0;
}

---

describe

이 내용은 간단합니다. 상대적으로 시간 제한이 널널하기에 복잡한 수식은 사용하지 않았기 때문이죠.

핵심은 메모리제이션입니다.

 

먼저 함수 fibo(int n)의 결과인 pair(first, second)의 정의를 다음과 같이 정해봅시다.

first는 fibonacci(n)이 fibonacci(0)을 호출한 횟수, second는 fibonacci(n)이 fibonacci(1)을 호출한 횟수, 

 

그렇다면 fibo(n)은 아래 점화식으로 표현됩니다.

1) n = 0이면 (1, 0), n = 1이면 (0, 1)

2) n >= 0이 항상 성립

3) fibo(n + 2).first = fibo(x + 1).first + fibo(x).first 인 동시에, fibo(n + 2).second = fibo(n + 1).second + fibo(n).second

 

위 내용을 조합한 코드는 아래와 같을 것입니다. (접은 글 참조)

위 점화식만을 보고 구현한 fibo함수

pair<int, int> fibo(int n) {
	pair<int, int> F, S;
	if (n == 0)
		return make_pair(1, 0);
	else if (n == 1)
		return make_pair(0, 1);
	else {
		F = fibo(n - 2);
		S = fibo(n - 1);
		return make_pair(F.first + S.first, F.second + S.second);
	}
}

그러나, fibo의 함수를 그래도 사용하기에는 상당히 느립니다. 아마 이대로 fibo함수를 만들어 제출하면 시간 초과가 나겠지요, 이 상황에서 필요한 것이 바로 메모리 제이션입니다.

 

메모이(리)제이션의 내용은 간단합니다.

어떤 함수f에 대해, f(factor)를 어떤 시점에 호출한다 하여도 그 결괏값이 동일한 경우에, f(factor)을 최초호출하였을때, 그 값을 메모리에 저장하고, 두번째 호출때는 f(factor)를 계산하지않고 메모리에 계산된 값을 바로 반환하는 알고리즘이죠.

자세한 내용은 아래 내용을 참조 바랍니다. 메모이제이션 관련 자료

 

메모리제이션까지 적용한 fibo의 코드는 아래와 같습니다. (접은 글 참조)

메모이제이션까지 적용한 fibo함수

static pair<int, int> mem[41];
//main함수에서 mem의 값을 모두 (0, 0)으로 초기화 할 것임

pair<int, int> fibo(int n) {
	pair<int, int> F, S;
	if (mem[n] != make_pair(0, 0))
		return mem[n];
	if (n == 0)
		return make_pair(1, 0);
	else if (n == 1)
		return make_pair(0, 1);
	else {
		F = fibo(n - 2);
		S = fibo(n - 1);
		return mem[n] = make_pair(F.first + S.first, F.second + S.second);
	}
}

그리고 이가 문제의 조건을 만족하는 함수이지요.

---

사용방법

백준 1003번 참고

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

1003번: 피보나치 함수

---

실행화면

프로그램의 사용 목적을 고려하여 실행화면은 생략하도록 하겠습니다.