JArchive 프로그래밍 일기

피보나치 수열(Fibonacci Sequence)

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, . . . .

앞의 두 수를 더해서 다음 수를 구하는 수열이다.  

n번째 값 = n-1번쨰 값 + n-2번째 값 이다. 

첫 번째 값과 두 번째 값은 주어져 있어야 한다. 

1번째 값을 요구하면 0리턴

2번째 값을 요구하면 1리턴

3번째 값을 요구하면 n-1값 + n-2값 리턴 

#include <stdio.h>

#include 

int Fibo(int num)
{
	if (num == 0)
		return 0;
	else if (num == 1)
		return 1;
	else
		return Fibo(num - 1) + Fibo(num - 2);
}

int main()
{
	for (int i = 0; i < 12; i++)
		printf("%d ", Fibo(i));
	return 0;
}

재귀함수 (Recursive)

재귀함수가 호출되면, 재귀함수의 복사본이 만들어져서 복사본이 호출되어 실행된다.

재귀함수의 탈출 조건이 중요하다.

다음은 팩토리얼(factorial) 값을 반환하는 함수를 재귀적으로 구현한 코드다. 

정수 n의 팩토리얼 n!을 수식적으로 나타내면 다음과 같다. 

n! = n * (n-1) * (n-2) * ..... 2 * 1;

정수 n 에 대하여 

n>=1인 경우 n * f(n-1)을 반환하고 

n==0인 경우 1을 반환한다 

#include <stdio.h>

int Recursive(int num)
{
	if (num == 0)
		return 1;
	else
		return Recursive(num - 1)*num;
}

int main()
{
	printf("%d!\n", Recursive(8));
	printf("%d!\n", Recursive(5));
	printf("%d!\n", Recursive(3));
	printf("%d!\n", Recursive(2));
	printf("%d!\n", Recursive(1));
	return 0;
}

전제: 배열의 데이터는 정렬된 상태이다.

<순서> 

1. 배열의 중앙(mid)에 찾는 값(target)이 저장되어 있는지 확인한다.

2. 대소 결과 탐색의 대상을 반으로 줄인다.

3. 1과 2를 반복한다.

#include <stdio.h>

int BSearch(int *arr, int len, int target)
{
	int first = 0;			//탐색 시작 인덱스
	int last = len - 1;		//탐색 마지막 인덱스 
	int mid;			

	while (first <= last)    
	{
		mid = (first + last) / 2;		//mid: 중앙인덱스 
		if (target == arr[mid])
		{
			return mid;		//찾은 경우 인덱스 mid를 리턴(탐색 완료)
		}
		else  //아니라면, 탐색 대상을 반으로 줄인다 
		{
			if (target > arr[mid])
			{
				first = mid + 1;	//타겟이 더 크면 first의 위치를 옮김
			}
			else
			{
				last = mid - 1;		//타겟이 더 작으면 last의 위치를 옮김
			}
		}
	}
	return -1;	//탐색 실패한 경우 
}

int main()
{
	int arr[] = { 1, 4, 5, 7, 9, 14 };		//정렬되어 있는 배열임을 전제.
	int len = sizeof(arr) / sizeof(int);
	int index;

	index = BSearch(arr, len, 9);	//'9'를 찾아본다 
	if (index == -1)
		printf("탐색실패!\n");
	else
		printf("target의 인덱스: %d\n", index);

	return 0;
}

순차 탐색 알고리즘은 배열에 순차적으로 접근해서 target값과 비교하여 탐색한다.

#include <stdio.h>
int LSearch(int arr[], int len, int target)
{
	int i;
	for (i = 0; i < len; i++)
	{
		if (target == arr[i])
			return i;	//찾은 경우 
	}
	return -1;	//찾지 못한 경우 
}

int main()
{
	int arr[] = { 3, 5, 2, 4, 9 };
	int index;

	index = LSearch(arr, sizeof(arr) / sizeof(int), 4);
	if (index == -1)
		printf("찾기 실패");
	else
		printf("%d \n", index);


	return 0;
}

버블정렬(Bubble Sort)은 인접한 숫자를 비교하여 자기보다 큰 수가 나오면 교환하는 정렬 알고리즘이다. 

시간복잡도는 O(n^2)로 상당히 느리지만 구현히 쉽고 안정적이다. 

메모리 사용 공간 : n개의 원소에 대하여 n개의 메모리를 사용한다. 

다음은 '오름차순'으로 정렬하는 코드다.

#include <stdio.h>
#include <stdlib.h>
#define SWAP(a,b) {int t=a; a=b; b=t; };

int BubbleSort(int *dataArray, int length)
{
	int i, j;
	for (i = 0; i < length - 1; i++)
	{
		for (j = 0; j < length - i -1; j++)
		{
			if (dataArray[j]>dataArray[j + 1])    //앞의 수가 더 클 경우 자리교환 ! 
			{
				SWAP(dataArray[j], dataArray[j + 1]);
			}
		}
	}
}

int main()
{
	int *dataArray;
	int length=0;
	int i = 0;

	printf("배열의 크기를 입력하세요:");
	scanf("%d", &length);
	dataArray = (int*)malloc(sizeof(int)*length);
	//입력 
	printf("크기 %d배열의 원소를 입력하세요: ", length);
	for (i = 0; i < length; i++)
	{
		scanf("%d", &dataArray[i]);
	}

	BubbleSort(dataArray, length);
	//출력
	for (i = 0; i < length; i++)
		printf("%d ", dataArray[i]);

	return 0;
}

의미 하나님의 초대장을 받고 티스토리를 시작하게 되었습니다. (감사해요!)

항상 티스토리 글을 읽기만 하다가 직접 운영하게 되니 정말 설레고 뭔가 새내기가 된 느낌입니다.

저에게도 누군가에게도 도움이 되는 공간이 되었으면 합니다. ^^

ps. 티스토리 소개해준 동빈찡 고마워:)