C 언어 기초#7 배열, 정렬, 탐색(순차탐색, 이진탐색), 다차원배열

*배열

동일한 타입의 데이터가 여러 개 저장되어 있는 데이터 저장 장소.

 

int grade[배열의 크기] // 배열의 크기 >0

grade[배열의 순서] // 0=< 배열의 순서 < 배열의 크기

배열의 초기화 : int grade[5]= { 10, 20, 30 };  // 5개의 배열 중 0~2에 차례로 들어가고 나머지는 0으로 초기화

int grade [5] = { 0 };  //  첫 번째 원소가 0이고 나머지 원소들도 0으로 초기화된다.

배열의 크기를 알아내는 법 -> sizeof(grade)는 전체 배열의 크기, sizeof(grade[0]);는 배열 원소의 크기

 

*배열과 함수

1.배열 원소를 인수로 하여서 함수를 호출하면 복사본이 전달된다. 배열은 원본이 전달되지만 배열 원소는 복사본이 전달된다.

2. 원본 배열의 변경을 금지하는 방법 – const 지정자를 배열 매개 변수 앞에 붙이면 그 배열 원소는 변경이 불가능.

void print_array(const int a[], int size)
{	...
	a[0] = 100; 	// 컴파일 오류
}

#include<stdio.h>
#define SIZE 7

void square_array(int a[], int size);	// void는 반환값이 없음을 나타냄.
void print_array(int a[], int size);

int main(void)
{
	int list[SIZE] = { 1,2,3,4,5,6,7 };

	print_array(list, SIZE);
	square_array(list, SIZE);	//배열은 원본이 전달된다.
	print_array(list, SIZE);

	return 0;
}
// a[]를 변경하면 원본이 변경된다.
void square_array(int a[], int size)	
{
	int i;	//배열은 원본이 전달됨로, 호출된 함수가 배열의 원소를 수정하면 원본 배열의 내용도 동시에 수정됨.

	for (i = 0; i < size; i++)
		a[i] = a[i] * a[i];
}
//배열 원소들을 화면에 출력한다.
void print_array(int a[], int size)
{
	int i;

	for (i = 0; i < size; i++)
		printf("%3d", a[i]);	// %3d 정수를 3자리로 출력, 빈 자리는 공백으로 채움.
	printf("\n");
}
-------------------------------------------------------------------------------------
실행결과
1	2	3	4	5	6	7
1	4	9	16	25	36	49
-------------------------------------------------------------------------------------

 

*정렬(sorting)

정렬은 오름차순(ascending order)이나 내림차순(descending order)으로 나열하는 것을 의미

 

선택 정렬(selection sort) : 가장 이해하기 쉬운 정렬 방법.

똑같은 크기의 배열을 만들고, 대상 배열에서 가장 작은 숫자를 선택하여 새로운 배열에 크기 순서대로 추가해가는 방법.

 

#include<stdio.h>
#define SIZE 10

int main(void)
{
	int list[SIZE] = { 3,2,9,7,1,4,8,0,6,5 };

	int i, j, temp, least;

	for (i = 0; i < SIZE - 1; i++)	// 외부 for 루프로서 아직 정렬되지 않은 숫자들 중에서 최소값을 선택해서
					// 정렬되지 않은 숫자들 중 맨 앞에 위치한 숫자와 교환하는 반복 루프이다. 
        		     	       // n-1번 반복된다.
	{
		least = i;	// i번째 원소부터 시작하여 배열의 맨 마지막 원소 중에서 최소값을 찾아야 한다. 
				// 일단은 i번째 원소를 최소값이라고 가정한다.
                
		for (j = i + 1; j < SIZE; j++)	// 내부 for루프로서(i+1)번째 원소부터 배열의 마지막 원소 중에서 
        					// 최소값을 찾는다. 
			if (list[j] < list[least])	//현재의 최소값과 비교하여 더 작은 정수가 발견되면
				least = j;		// 그 정수가 들어있는 인덱스를 least에 저장한다.
                
		temp = list[i];		// i번째 원소와 least 위치의 원소를 교환한다.
		list[i] = list[least];
		list[least] = temp;
	}
	for (i = 0; i < SIZE; i++)
		printf("%d", list[i]);
	printf("\n");
	return 0;
}

*탐색(search)

- 순차 탐색(sequential search) : 배열의 원소를 순서대로 하나씩 꺼내서 탐색키와 비교하여 원하는 값을 찾아가는 방법.

- 이진 탐색(binary search): 배열의 중앙에 있는 값을 탐색키와 비교. 정렬되어 있어야 함. 절반씩 비교해나감

 

순차 탐색

#define _CRT_SECURE_NO_WARNINGS		//scanf 오류 무시하고 사용하기 위한 정의.
#include<stdio.h>
#define SIZE 10

int main(void)
{
	int key, i;
	int list[SIZE] = { 1,2,3,4,5,6,7,8,9 };

	printf("탐색할 값을 입력하시오:");
	scanf("%d", &key);		// 사용자로부터 탐색할 값을 입력받음.

	for (i = 0; i < SIZE; i++)
		if (list[i] == key)
			printf("탐색 성공 인덱스=%d\n", i);
	// for 루프를 이용하여 list[i]와 key를 비교하는 연산을 배열의 크기만큼 반복. 
	// 만약 list[i]와 key가 같으면 탐색은 성공되고 키 값이 발견된 배열의 인덱스를 출력.
	printf("탐색 종료\n");
	return 0;
}

이진 탐색

#define _CRT_SECURE_NO_WARNINGS		//scanf 오류 무시하고 사용하기 위한 정의.
#include<stdio.h>
#define SIZE 16
int binary_search(int list[], int n, int key);	// 함수 원형 정의

int main()
{
	int key;
	int grade[SIZE] = { 2,6,11,14,18,20,22,27,29,30,34,38,41,42,45,47 };

	printf("탐색할 값을 입력하시오:");
	scanf("%d", &key);
	printf("탐색 결과 = %d", binary_search(grade, SIZE, key));
	return 0;
}
//배열 list[]에서 key를 찾아서 위치를 반환하는 함수이다. n은 배열의 크기이다.
int binary_search(int list[], int n, int key)	
{
	int low, high, middle;

	low = 0;
	high = n - 1;
	
	while (low <= high) {		// 아직 숫자들이 남아있으면
		printf("[%d %d]\n", low, high);	// 하한과 상한을 출력한다.
		middle = (low + high) / 2;	// 중간 위치를 계산한다.
		if (key == list[middle])	// 일치하면 탐색 성공
			return middle;
		else if (key > list[middle])	// 중간 원소보다 크다면
			low = middle + 1;		// 새로운 값으로 low 설정
		else
			high = middle - 1;		// 새로운 값으로 high 설정
	}
	return -1;		// 에러 발생시 -1 값을 반환
}

*2차원 배열

int s[3][5] = {
{ 0, 1, 2, 3, 4 },
{ 10, 11, 12, 13, 14 },
{ 20, 21, 22, 23, 24 }
};

- 선언과 동시에 초기화하는 경우, 행의 개수는 지정하지 않을 수 있다. 이 경우 컴파일러가 자동으로 행의 개수를 결정한다. 반면 열의 개수는 반드시 지정하여야 한다. (초기값을 지정하지 않고 배열이 전역 변수로 선언되어 있는 경우 원소 값을 0으로 초기화, 배열이 지역 변수로 선언되어 있는 경우에는 쓰레기 값이 들어감.)

 

*다차원 배열 인수

- 1차원과 달리 첫 번째 인덱스의 크기를 제외한 나머지 인덱스의 크기는 반드시 적어주어야 한다.

int sum(int list [][5]) 
{
 ...
}