#자료구조와 함께 배우는 알고리즘 입문 C언어편 - 6

5장 재귀 알고리즘

 

05-1 재귀의 기본

재귀란?

어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때

 

05-2 재귀 알고리즘 분석

하향식 분석 : 가장 위쪽에 위치한 상자의 함수 호출부터 시작해 계단식으로 자세히 조사해 가는 분석 기법

상향식 분석 : 아래쪽부터 쌓아 올리며 조사해 가는 분석 기법

 

05-3 하노이의 탑

작은 원반이 위에, 큰 원반이 아래에 위치할 수 있도록 원반을 3개의 기둥 사이에서 옮기는 문제

void move(int no, int x, int y)
{
	if (no > 1)
	{
		move(no - 1, x, 6 - x - y); // 바닥 원반을 제외한 그룹을 시작 기둥에서 중간 기둥으로 옮김
	}
	printf("원반[%d]를(을) %d 기둥에서 %d 기둥으로 옮김.\n", no, x, y);
	if (no > 1)
	{
		move(no - 1, 6 - x - y, y); // 바닥 원반을 제외한 그룹을 중간 기둥에서 목표 기둥으로 옮김
	}
}

int main(void)
{
	int n;
	printf("하노이의 탑\n원반의 개수 : ");
	scanf_s("%d", &n);

	move(n, 1, 3);
	return 0;
}

 

05-4 8퀸 문제

서로 공격하여 잡을 수 없도록 8개의 퀸을 8 x 8 체스판에 놓는 문제

int flag_a[8]; // 각 행에 퀸을 배치했는지 체크하는 배열
int flag_b[15]; // 대각선 /에 퀸을 배치했는지 체크하는 배열
int flag_c[15]; // 대각선 \에 퀸을 배치했는지 체크하는 배열
int pos[8]; // 각 열에서 퀸의 위치

void Print(void)
{
	int i;
	for (i = 0; i < 8; i++)
	{
		printf("%2d", pos[i]);
	}
	putchar('\n');
}

void set(int i) // i열에서 알맞은 위치에 퀸을 배치
{
	int j;
	for (j = 0; j < 8; j++)
	{
		if (!flag_a[j] && !flag_b[i + j] && !flag_c[i - j + 7])
		{
			pos[i] = j;
			if (i == 7) // 모든 열에 배치를 마침
			{
				Print();
			}
			else
			{
				flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = 1;
				set(i + 1);
				flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = 0;
			}
		}
	}
}

int main(void)
{
	int i;
	for (i = 0; i < 8; i++)
	{
		flag_a[i] = 0;
	}
	for (i = 0; i < 15; i++)
	{
		flag_b[i] = flag_c[i] = 0;
	}
	set(0);

	return 0;
}

 

6장 정렬

 

06-1 정렬

정렬이란?

핵심 항목(key)의 대소관계에 따라 데이터 집합을 일정한 순서로 줄지어 늘어서도록 바꾸는 작업

오름차순 정렬 : 키 값이 작은 데이터가 앞쪽에 있을 경우

내림차순 정렬 : 키 값이 큰 데이터가 앞쪽에 있을 경우

내부 정렬 : 정렬할 모든 대이터를 하나의 배열에 저장할 수 있는 경우 사용하는 알고리즘

외부 정렬 : 정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없는 경우 사용하는 알고리즘

 

정렬 알고리즘의 핵심 요소

교환, 선택, 삽입

 

06-2 버블 정렬

이웃한 두 요소의 대소 관계를 비교하여 교환을 반복

#define swap(x, y) do { int t = x; x = y; y = t;} while(0)

void bubble(int a[], int n)
{
	int i, j;
	for (i = 0; i < n - 1; i++)
	{
		for (j = n - 1; j > i; j--)
		{
			if (a[j - 1] > a[j])
			{
				swap(a[j - 1], a[j]);
			}
		}
	}
}

int main(void)
{
	int i, nx;
	int* x;
	puts("버블 정렬");
	printf("요소 개수 : ");
	scanf_s("%d", &nx);
	x = (int*)calloc(nx, sizeof(int)); // 요소의 개수가 nx인 int형 배열 생성

	for (i = 0; i < nx; i++)
	{
		printf("x[%d] : ", i);
		scanf_s("%d", &x[i]);
	}

	bubble(x, nx);

	puts("오름차순으로 정렬합니다.");
	for (i = 0; i < nx; i++)
	{
		printf("x[%d] = %d\n", i, x[i]);
	}

	free(x);

	return 0;
}

// 교환 횟수에 따라 정렬 작업을 멈춤
void bubble(int a[], int n)
{
	int i, j;
	for (i = 0; i < n - 1; i++)
	{
		int exchg = 0; // 패스에서 시도한 교환 횟수
		for (j = n - 1; j > i; j--)
		{
			if (a[j - 1] > a[j])
			{
				swap(a[j - 1], a[j]);
				exchg++;
			}
			if (exchg == 0) break;
		}
	}
}

// 스캔 범위를 제한
void bubble(int a[], int n)
{
	int i, j;
	int k = 0;
	while (k < n - 1)
	{
		int j;
		int last = n - 1; // 마지막으로 교환을 수행한 위치를 저장
		for (j = n - 1; j > k; j--)
		{
			if (a[j - 1] > a[j])
			{
				swap(a[j - 1], a[j]);
				last = j;
			}
			k = last;
		}
	}
}