공부할 책 : 자료구조와 함께 배우는 알고리즘 입문 - C언어 편

스택

스택은 데이터를 일시적으로 저장하기 위한 자료구조로, 가장 나중에 넣은 데이터를 가장 먼저 꺼낸다.

스택은 데이터를 일시적으로 저장하기 위해 사용하는 자료구조로, 데이터의 입력 순서는 후입선출(가장 나중에 넣은 데이터를 가장 먼저 꺼냄)이다.

푸시(push) : 스택에 데이터를 넣는 작업
팝(pop) : 스택에서 데이터를 꺼내는 작업

큐

큐는 스택과 마찬가지로 데이터를 일시적으로 쌓아 놓은 자료구조이다. 하지만 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출인 점이 스택과 다르다.

인큐(enqueue) : 큐에 데이터를 넣는 작업
디큐(dequeue) : 큐에 데이터를 꺼내는 작업

데이터를 꺼내는 쪽을 프런트(front)라 하고, 데이터를 넣는 쪽을 리어(rear)라고 한다.

인큐의 복잡도는 O(1)이고, 적은 비용으로 구현할 수 있다.
디큐의 복잡도는 O(n)이며, 첫번째 요소를 제거한 후 두 번째 이후의 요소를 모두 맨 앞으로 옮긴다. 데이터를 꺼낼 때마다 이런 처리를 하게 되면 효율이 떨어진다.

링 버퍼

배열 요소를 앞쪽으로 옮기지 않는 큐이다.

링 버퍼는 배열의 처음이 끝과 연결되었다고 보는 자료구조이다. 여기서 논리적으로 어떤 요소가 첫번째 요소이고 어떤 요소가 마지막 요소인지 식별하기 위한 변수가 프런트와 리어이다.

활용

링 버퍼는 오래된 데이터를 버리는 용도로 사용할 수 있다. 구체적인 예를 들면 요소의 개수가 n인 배열에 계속해서 데이터가 입력될 때 가장 최근에 들어온 데이터 n개만 저장하고 오래된 데이터는 버려지는 용도로 사용한다. 정수 입력(인큐)는 무한히 할 수 있지만 배열에 저장되는 데이터는 가장 최근에 입력한 10개의 데이터만 링 버퍼에 남아 있다.

실습 코드 :

#include <stdio.h>
#define N 10			/* 저장하는 데이터의 개수 */

int main()
{
	int i;
	int a[N];		/* 입력한 데이터를 저장 */
	int cnt = 0;	/* 입력한 데이터의 개수 */
	int retry;		/* 다시 한 번? */

	puts("정수를 입력하세요.");

	do {
		printf("%d번째 정수 : ", cnt + 1);
		scanf_s("%d", &a[cnt++ % N]);
		printf("계속할까요? (Yes … 1/No … 0) : ");
		scanf_s("%d", &retry);
	} while (retry == 1);
		i = cnt - N;
		if (i < 0) i = 0;
		
	for (; i < cnt; i++)
		printf("%2d번째 정수 = %d\n", i + 1, a[i % N]);
		
	return 0;
}

재귀 알고리즘

재귀 : 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적이라고 한다.

병합정렬, 퀵정렬, 이진검색트리 등에 사용되니 잘 알아둘것

순차곱셈 구하기

실습 예제 :

#include <stdio.h>

int factorial(int n) {
	if (n > 1) return n * factorial(n - 1);
	else return 1;
}

int main() {
	int x;
	printf("정수를 입력하세요 : ");
	scanf_s("%d", &x);
	printf("결과 : %d", factorial(x));
}

유클리드 호제법

실습 예제 :

int gcd(int x, int y) {
	if (y == 0) return x;
	else return gcd(y, x % y);
}

int main() {
	int x,y;
	printf("정수를 입력하세요 : ");
	scanf_s("%d %d", &x,&y);
	printf("결과 : %d", gcd(x,y));
}

재귀 알고리즘 분석

recur 함수를 통해 재귀에 대해 좀 더 자세히 알아보자.

#include <stdio.h>

void recur(int n) {
	if (n > 0) {
		recur(n - 1);
		printf("%d\n", n);
		recur(n - 2);
	}
}

int main() {
	int x;
	printf("정수 입력 : ");
	scanf_s("%d", &x);
	recur(x);
	return 0;
}

recur 함수는 factorial 함수나 gcd 함수와 달리 함수 안에서 재귀 호출을 2회 실행한다. 이처럼 재귀 호출을 여러 회 실행하는 함수를 순수하게 재귀적이라 한다.
매개변수로 4를 전달하면 '1231412'라고 출력한다.

하향식 분석

가장 위쪽에 위치한 상자의 함수 호출부터 시작해 계단식으로 자세히 조사해 가는 분석 기법
① recur(3)을 실행합니다.
② 4를 출력합니다.
③ recur(2)를 실행합니다.

상향식 분석

하향식 분석과 대조적으로 아래쪽부터 쌓아 올리며 분석하는 방법
① recur(0)을 실행합니다.
② 1을 출력합니다.
③ recur(-1)을 실행합니다.

하노이의 탑

쌓아 놓은 원반을 최소의 횟수로 옮기기 위한 알고리즘

실습 예제 :

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 x;
	printf("원반 개수를 입력하세요. : ");
	scanf_s("%d", &x);
	move(x, 1, 3);
	return 0;
}

8퀸 문제

분할 해결법 (devide and conquer)

문제를 세분하고 세분된 작은 문제의 풀이를 결합해 전체 문제를 풀이하는 기법

가지 뻗기

퀸을 배치하는 조합을 모두 나열하는 코드이다.

#include <stdio.h> 

int pos[8];

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

void set(int i) {
	int j;
	for (j = 0;j < 8;j++) {
		pos[i] = j;
		if (i == 7) print();
		else set(i + 1);
	}
}

int main() {
	set(0);
	return 0;
}

분기 한정법

'[규칙 2] 각 행에 퀸을 1개만 배치합니다.' 를 적용시킨 코드이다.

#include <stdio.h> 

int pos[8];
int flag[8];

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

void set(int i) {
	int j;
	for (j = 0;j < 8;j++) {
		if(!flag[j]){
			pos[i] = j;
			if (i == 7) print();
			else {
				flag[j] = 1;
				set(i + 1);
				flag[j] = 0;
			}
		}
	}
}

int main() {
	for (int i = 0;i < 8;i++) flag[i] = 0;
	set(0);
	return 0;
}

8퀸 문제 해결 알고리즘

대각선 체크 변수를 flag_b, flag_c 배열 변수로 설정해서 문제를 해결하는 코드이다.

#include <stdio.h>

int pos[8],flag_a[8];
int flag_b[16],flag_c[16];
int cnt = 0;

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

void set(int i) {
	for (int 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() {
	for (int i = 0;i < 8;i++) {
		pos[i] = flag_a[i] = 0;
	}
	for(int i=0;i<16;i++){
		flag_b[i] = flag_c[i] = 0;
	}
	set(0);
	printf("%d", cnt);
}