C언어/따배씨 c언어

[따배씨] 피보나치 수열 feat. 하루 걸려서 푼

newbeverse 2022. 12. 18. 02:59

  우선 피보나치 수열을 처음 접했을땐, 피보나치 수열은 한눈에 이해할 수 있는 단순한 원리라서 곧이어 문제가 풀릴 줄 알았다. 하지만 처음 생각했던것과 달리, 내 논리대로 코딩이 잘안됐고 점점 산으로 가다못해 기괴해지면서 시간이 길어졌었다. (분명 7번째 수열까지는 계산이 되었는데, 8번쨰 부터 계산이 달라졌었던 문제를 겪었다.)

 첫번쨰 실패로 인해, 큰 틀에서 코드를 바꿔봤는데, 시간이 지날수록 머리가 점점 복잡해졌고, 더 이상 내 가정에 자신이 없어졌다. 그래서 우선 무의미하게 생각만 이어나가는 것을 그만 두기로 했다. 무엇이 진실인지 거짓인지 한치 앞을 볼수 없는 현 상태에서 감각적으로 문제를 해결하지말고, 수학식을 적듯이, 코드를 하나씩 적어가면서, 틀릴 수가 없게끔 옳은 가정만으로 시작하는 기초적인 것부터 코딩하기 시작했다. 즉, 나는 가장 단순하게 접근하는 방법을 택하게 됐고, 내가 피보나치 수열을 푸는 방법을 알고있으나, 그것을 코들 표현하지 못하는 것이기 때문임을 다시한번 인지하기 시작하면서 압박이 풀려갔고, 점점 논리를 쌓아올리자 답을 도출 할 수 있었다. 

 결국 12시간 전에 맨 처음 생각했던 그 아이디어를 그대로 적용해서 풀어냈다. 단, 그때는 아이디어는 있었을뿐 코드로 풀어내질 못했던 것이였고, 그 과정에서 큰 도움이 된 방식은 가정을 하지않고 가장 확실한 사실 -> 즉, 가장 쉬운 것이지만 기초적인 코드부터 하나씩적어나가는 것이였다.

피보나치 수열코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int fibonacci(int number);

int main()
{
	for (int count = 1; count < 20; ++count)
		printf("%d ", fibonacci(count));

	return 0;
}

int fibonacci(int number)
{
	int a = 1;
	int	b = 1;
	int c = 1;
	int remainder;
	int quotient;
	// 1, fibonacci(1)
	// 1, fibonacci(2)

	remainder = number / 3;
	quotient = number % 3;
	while (remainder > 0)
	{
		c = a + b; // 2, fibonacci(3)
		b = c + a; // 3, fibonacci(4)
		a = b + c; // 5, fibonacci(5)
		remainder = remainder - 1;
	}
	if (number == 1 & number == 2) return 1;	
	if (quotient == 0) return c;
	if (quotient == 1) return b;
	if (quotient == 2) return a;
}

사용했던 그림판, (패드가 하나 있으면 정말 좋겠지만)

 

자이제 교수님의 코드를 확인해보겠습니다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int fibonacci(int number);

int main()
{
	for (int count = 1; count < 20; ++count)
		printf("%d ", fibonacci(count));

	return 0;
}

int fibonacci(int number)
{
	if (number > 2)
		return fibonacci(number - 1) + fibonacci(number - 2); // double recursion
	else
		return 1;
}

내 예상외로 매우 짧고, 재귀함수로 구현되어있다.

교수님 말씀을 요약하자면

재귀함수 -> 세상에 공짜 점심은 없다.(다른 반복문에 비해 코드가 짧은 만큼 스택이 많이 쌓여서 효율이 안좋다.)

이다.

우선 나는 코드가 이해가 안돼서, 직접 숫자를 넣어보는 작업을 했다. 

답과 같은 결과가 나와서 눈으로 봤을땐 납득했지만, 그렇다고 이 재귀 코드를 이해했다고 보진 않는다.

다만 여러 재귀함수를 보면서 생각이 든것은, 가장 마지막 스택에 쌓인 함수에 숫자가 '특정값'으로 정해지면, 함수가 하나씩 풀리면서 착착 계산되는게 느껴진다... 아직까진 이렇게 알고 넘어가야 할 것 같다.

반응형