chapter 1 : Base Concept(선택 정렬, 순열, Magic Matrix)

Selction sort (선택 정렬)

배열이 있으면 맨 앞에 인덱스를 기준으로 배열 끝까지 돌면서 맨앞에 인덱스와 비교해 가장 작은 수와

바꿔주면 됩니다.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
#define SWAP(x,y,t) ((t)=(x), (x)=(y), (y)=(t))
void sort(int list[], int n);
int main() {
	int arr[5] = { 5,2,1,4,3 };
	sort(arr, 5);
	for (int i = 0; i < 5; i++) {
		printf("%d ", arr[i]);
	}
	return 0;
}
void sort(int list[], int n) {
	int i, j, min, temp;
	for (i = 0; i < n - 1; i++) {
		min = i;
		for (j = i + 1; j < n; j++) 
			if (list[j] < list[min])
				min = j;
		SWAP(list[i], list[min], temp);
	}
}

변수 min은 가장 작은 수의 인덱스 입니다.

temp는 SWAP 함수를 쓰기 위한 임시 저장소 입니다.

---

Permutation<Recursion> (순열<재귀>)

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
#define SWAP(x,y,t) ((t)=(x), (x)=(y), (y)=(t))
void perm(char list[], int i, int n);
int main() {
	char list[100] = {"abc"};
	perm(list, 0, 2);
	return 0;
}
void perm(char list[], int i, int n) {
	int j, temp;
	if (i == n) {
		for (j = 0; j <= n; j++)
			printf("%c", list[j]);
		printf(" ");
	}
	else {
		for (j = i; j <= n;j++) {
			SWAP(list[i], list[j], temp);
			perm(list, i + 1, n);
			SWAP(list[i], list[j], temp);
		}
	}
}

변수 i와 n은 문자열의 시작 인덱스와 마지막 인덱스 입니다.

else 문을 보면 첫번째 SWAP에서 문자열의 순서를 바꿔주고

마지막 SWAP에서 다시 되돌려 줍니다.

---

Magic Matrix (마방진)

마방진이란 행, 열, 대각선 모두 각각의 합이 셋다 같은 행렬을 의미합니다.

여러가지 마방진이 있지만 m * m 행렬중 m이 홀수인 행렬을 알아보겠습니다.

        int square[MAX_SIZE][MAX_SIZE];
	int i, j, row, column;
	int count;
	int size;
	printf("Enter the size of the square: ");
	scanf("%d", &size);

	if (size<1 || size>MAX_SIZE + 1) { 
		fprintf(stderr, "Error! Size is out of range\n");
		exit(1);
	}
	if (!(size % 2)) { //size가 짝수라면
		fprintf(stderr, "Error! Size is even\n");
		exit(1);
	}
	for (i = 0; i < size; i++)
		for (j = 0; j < size; j++)
			square[i][j] = 0; //모든 행렬을 0으로 초기화

변수 count는 행렬의 값을 의미합니다. 

처음에는 모든 행렬의 값을 0으로 초기화 해줍니다.

        square[0][(size - 1) / 2] = 1; //첫번째 행의 중간을 1로 초기화
	i = 0;
	j = (size - 1) / 2; //i와 j는 현재 위치
	for (count = 2; count <= size * size; count++) {
		row = (i - 1 < 0) ? (size - 1) : (i - 1); //up
		column = (j - 1 < 0) ? (size - 1) : (j - 1); //left
		if (square[row][column]) //down
			i = (++i) % size;
		else { //square[row][col]이 0일때
			i = row;
			j = column;
		}
		square[i][j] = count;
	}

행렬의 맨 위의 행중 가운데 열을 1로 초기화 해줍니다.

i, j는 현재 행렬의 현재 위치를 나타냅니다. 

for문에서는 i, j가 값이 바뀌면서 해당하는 위치에 count값을 넣어 줍니다. 

       printf("Magic Square of the size %d: \n\n", size);
	for (i = 0; i < size; i++) {
		for (j = 0; j < size; j++)
			printf("%5d", square[i][j]);
		printf("\n");
	}

출력 함수입니다.

---

전체 코드입니다.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
#define MAX_SIZE 15
int main() {
	int square[MAX_SIZE][MAX_SIZE];
	int i, j, row, column;
	int count;
	int size;
	printf("Enter the size of the square: ");
	scanf("%d", &size);

	if (size<1 || size>MAX_SIZE + 1) { 
		fprintf(stderr, "Error! Size is out of range\n");
		exit(1);
	}
	if (!(size % 2)) { //size가 짝수라면
		fprintf(stderr, "Error! Size is even\n");
		exit(1);
	}
	for (i = 0; i < size; i++)
		for (j = 0; j < size; j++)
			square[i][j] = 0; //모든 행렬을 0으로 초기화
	square[0][(size - 1) / 2] = 1; //첫번째 행의 중간을 1로 초기화
	i = 0;
	j = (size - 1) / 2; //i와 j는 현재 위치
	for (count = 2; count <= size * size; count++) {
		row = (i - 1 < 0) ? (size - 1) : (i - 1); //up
		column = (j - 1 < 0) ? (size - 1) : (j - 1); //left
		if (square[row][column]) //down
			i = (++i) % size;
		else { //square[row][col]이 0일때
			i = row;
			j = column;
		}
		square[i][j] = count;
	}
	printf("Magic Square of the size %d: \n\n", size);
	for (i = 0; i < size; i++) {
		for (j = 0; j < size; j++)
			printf("%5d", square[i][j]);
		printf("\n");
	}
	return 0;
}