백준 2747 / 2748 - 피보나치 수 1,2 (재귀 vs 반복)

 

 

2747번: 피보나치 수

 

2748번: 피보나치 수 2

 

피보나치 수

피 보나 치수에 대해 정리하자면 다음과 같습니다. 

 

• 피보나치 수는 0과 1로 시작합니다.
• 0번째 피보나치 수 = 0
• 1번째 피보나치 수 = 1
• 2번째 피보나치 수부터는 바로 앞 2개의 피보나치 수의 합입니다.
• 2번째 피보나치 수 = 1 (0번째 + 1번째)
• 이런 식으로 피보나치 수가 구성됩니다.

문제 파악 및 구현 준비

• 피보나치 수에 대한 이해가 필요하다.
• N번 째 피보나치 수의 값을 찾아보자.

본 포스트에서는 반복문을 통한 구현과 재귀적 표현을 통한 구현 2가지를 만들어 보도록 하겠습니다.

 

for문을 이용한 구현

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>


//함수 정의 
long long int fibo_for(int N) {

	//피보나치 수들을 저장해둘 변수 설정
	long long int fibo_before2 = 1; // 전전 피보나치 수 (1번째 = 1)
	long long int fibo_before1 = 1; // 전 피보나치 수 (2번째 = 1)
	long long int fibo_current = 2; // 현재 피보나치 수(3번째= 2)

	for (int i = 0; i <= N; i++) {
		if (N == 0) return 0; // 0번째 피보나치 수 리턴
		else if (N <= 2) return 1; // 1번 째 2번 째 피보나치 수 리턴
		//그 외의 N번째 피보나치 수를 요구한다면 하나씩 밀려나며 다음 피보나치 수를 구한다
		else if (i > 3){
			fibo_before2 = fibo_before1;
			fibo_before1 = fibo_current;
			fibo_current = fibo_before1 + fibo_before2;
		}

	}
	return fibo_current;
}



int main(void)
{
	//변수 선언 찾고자 하는 피보나치 수의 N번째 자리 및
	//수의 값을 저장하는 결과
	int N ;
	long long int result = 0;
	scanf("%d", &N);
	result = fibo_for(N);
	printf("%lld\n", result);
	return 0;
}

• 단순하게 피보나치 규칙대로 절차 지향 구현을 하였습니다.
• 단, 수가 크기 때문에 long long int를 이용했습니다.

재귀를 이용한 구현 

• 피보나치 수를 식으로 표현한다면 다음과 같습니다. 
• 몇 번째를 표현하는 N번이 2 이상이라면 Fn = Fn-1 + Fn-2
• 재귀 함수를 이용해서 프로그래밍을 하려면 2가지 조건이 필요합니다.
  • 함수의 종료 조건 (해당 문제의 경우 N의 값이 2 이하의 조건)
  • 재귀적 표현 조건 (해당 문제의 경우 Fn = Fn-1 + Fn-2)

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

int fibo_recur(int N) {
	//탈출 조건
	if (N == 0) return 0;
	if (N == 1 || N == 2) return 1;
	
	//재귀적 표현
	return fibo_recur(N - 1) + fibo_recur(N - 2);
}


int main(void)
{
	//변수 선언 찾고자 하는 피보나치 수의 N번째 자리 및
	//수의 값을 저장하는 결과
	int N ;
	long long int result = 0;
	scanf("%d", &N);
	result = fibo_recur(N);
	printf("%lld\n", result);
	return 0;
}

 

어떤 것이 더 좋은가? 

사실 프로그래밍에 완벽한 정답은 없습니다. 상황에 따라 더 적합한 방법이 있을 뿐입니다. 

위의 2가지 예시를 들어 보이는 차이점을 말하자면 아래와 같습니다.

• 반복문 보다 재귀적인 표현이 더 간결하게 소스코드 작성이 될 수 있다.

결국 소스코드의 가독성의 향상이 된다는 의미입니다.

하지만 위의 링크를 들어가서 2가지 문제를 2가지 방법으로 풀어본다면 조금 다른 결과가 나옵니다.

재귀적 표현을 써서 N의 값이 큰 피보나치를 찾기 위해서는 시간 초과가 뜹니다.

이로서 유추해 볼 수 있는 결과는 다음과 같습니다.

• 재귀를 이용한 프로그래밍은 비교적 속도가 느리다(자원을 많이 사용한다)

 

알고리즘 - 재귀함수 (Recursion Funtion)

재귀에 대한 개념이 궁금하시다면 다시 한번 포스트를 보는 것을 추천드립니다.