새싹교실/2014/다빈치인재반/6회차

계획

• 하노이의 탑
• N-Queen
• 괄호 짝맞춤.
• Queue

후기

• queue와 stack을 왜 배우는지 알게 되었고 개념을 확실하게 알 수 있었습니다. 막판에 queue 구현을 같이 했는데 하기는 열심히 했으나 버그 투성이여서ㅋㅋ새싹 끝나고도 계속 완성시키려고 했으나 자꾸 실패하여 머리가 녹아내리는 줄 알았습니다. 사실 포인터에 대해서는 개념만 알고 간단한 예제 프로그래밍 정도만 해봤을 뿐 써본 적이 많질 않았는데 큐를 구현하면서 '포인터는 수많은 버그를 양산한다'는 윤성우씨의 말씀을 실감하게 되었습니다. - 이지수

숙제

이지수

• 하노이의 탑

이번주 기초프로그래밍 과제가 하노이 탑이더군요. 그래서 가장 먼저 하게 되었습니다. 분명 저번에 영기선배님이 하노이탑 코드를 보여주셔서 해석하느라 뚫어지게 쳐다봤었는데도 정작 과제를 하려니 내가 코드를 쳐다봤다는 사실밖에는 기억이 나지 않았습니다;; 재귀함수 안에 재귀호출을 두 번 한다는 정도??밖에 기억이 안나더군요. 그래서 하노이 탑의 알고리즘을 알고자 하노이 탑 플래시 게임을 계속 해보았습니다. 게임을 하다보니 새싹 때 보았던 기둥을 바꾸는 알고리즘이 이해가 되더군요. 암튼 그렇게 간간히 종이에 끼적이면서 생각하다가 프로그램을 완성하였습니다.

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

int first_stick = 1, second_stick = 2, third_stick = 3;

void hanoi(int start, int middle, int goal, int num){

	if (num == 1)
		printf("%d -> %d\n", start, goal);
	else{
		hanoi(start, goal, middle, num - 1);
		printf("%d -> %d\n", start, goal);
		hanoi(middle, start, goal, num - 1);
	}
	
}

int main()
{
	int n;
	printf("고리의 갯수를 입력하세요 : ");
	scanf("%d", &n);

	hanoi(first_stick, second_stick, third_stick, n);

	printf("\t20141718 이지수\n");
	system("pause");
	return 0;
}

• 큐 구현

동적할당을 이용해서 순환 큐를 만들었습니다. 처음에 예외처리를 if-else 때려넣으면서 무식하게 하다가 수많은 버그를 양산해서 머리가 폭발하는 줄 알았습니다. 그래서 당분간 큐를 버리고ㅋㅋ하노이탑에 집중을 하다가 오늘 정신이 비교적 맑아서 도전했고 3시간 걸려서 다 풀었습니다. 좋은 알고리즘이란 예외를 최대한 적게 만드는 것이라는 사실을 요즘들어 깨닫고 있습니다. 맨 처음에 프로그램을 작성했을 때는 큐 크기가 2 이상일 때는 되고 1일 때는 아예 안 되길래 큐 크기를 1로 입력받을 때를 대비한 예외함수까지 만들었었는데ㅋㅋ오늘 작성한 프로그램은 큐 크기를 1로 입력받을 때도 잘 처리해주거든요. 어쨌든 덕분에 포인터에 대해 더 잘 이해하게 된 것 같습니다. 그리고 반복문을 for문을 주로 썼는데 for문은 안에 있는 내용을 1번은 꼭 수행하기 때문에 예상치 못한 버그를 만들 수 있다는 것을 깨달았네요. while도 사랑해주어야겠습니다.

#include <stdlib.h>

int front_count = 0, rear_count = 0, Qsize, n;
int *front, *rear, *queue;

int *push(int* push_ptr){

	 printf("enter a value to push : ");
	 scanf("%d", push_ptr);

	 if(rear_count%Qsize == 0)
		 return queue;
	 else
		 return ++push_ptr;

}

int *pop(int* pop_ptr){

	 if(front_count%Qsize == 0)
		 return queue;
	 else
		 return ++pop_ptr;
}

void print_queue(){

	 int a, b, c, i, j;

	 if(rear_count - front_count == Qsize){

		  for(i = 0; i < Qsize ; i++)
		   printf(" %d ", *(queue + i));
	 }
	 else if(rear_count == front_count){

		  for(j = 0; j < Qsize ; j++)
		   printf(" _ ");
	 }
	 else{
		   int rear_num = rear_count%Qsize;
		   int front_num = front_count%Qsize;

		  if(rear < front){

			   a = 0, b = rear_num, c = front_num;

				   while( a != rear_num ){
					printf(" %d ", *(queue + a));
					a++;
				   }
				   while( b != front_num ){
					printf(" _ ");
					b++;
				   }
				   while( c != Qsize ){
					printf(" %d ", *(queue + c));
					c++;
				   }
			}
		  else{

		           a = 0, b = front_num, c = rear_num;

				   while( a != front_num ){
					printf(" _ ");
					a++;
				   }
				   while( b != rear_num ){
					printf(" %d ", *(queue + b));
					b++;
				   }
				   while( c != Qsize){
					printf(" _ ");
					c++;
					}
			}	

	 }

 printf("\n");
}

int main(){

 printf("enter queue size : ");
 scanf("%d", &Qsize);

 queue = (int *)malloc(sizeof(int)*Qsize);

 front = queue;
 rear = queue;

 while(1){

	 printf("select (1.push 2.pop 3.print queue 4.end) : ");
	 scanf("%d", &n);

	  switch(n){

	  case 1:

		   if(rear_count - front_count == Qsize){
			puts("the queue is full");
			break;
		   }

		   rear_count++;
		   rear = push(rear);
		   break;

	  case 2:

		   if(rear_count == front_count){
			puts("the queue is empty");
			break;
		   }

		   front_count++;
		   front = pop(front);
		   break;

	  case 3:

		   print_queue();
		   break;

	  case 4:

		   puts("program is closed");
                   free(queue);
		   system("pause");
		   return 0;

	  default:

		   puts("please enter a valid number");

	  }
	 }

}

코드에 대해서 개선할 사항이 있으면 무엇이든 말씀해주세요! 저는 깔끔하고 가독성이 높은 코드를 작성하는데 익숙하질 않아서 코드가 좀 난잡한 듯 하네요.

김정민

• 큐 구현

모방은 창조의 어머니라는 말이 있지요. 권준혁 학우의 스택 코드를 ~~매우 조금~~ 고쳐서 큐를 구현해 봤습니다. 준혁이가 스택을 탄탄하게 잘 만들어놔서(가독성도 굿굿), 동적할당과 포인터에 대한 이해가 부족한 저도 쉽게 만들 수 있었네요. 이 자리를 빌어서 권준혁군에게 심심한 감사를 표합니다.
#include<time.h>
#include<stdlib.h>

int scale_of_stack; //큐의 크기
int top_of_stack;  //큐의 성분 갯수. 7이면 7개 있는거다

int Pop(int *start_p); //0이면 실패(큐에 아무것도 없는 경우겠져? ^^) start_p는 큐의 시작 주소
int Push(int *start_p, int input); //1이면 성공, 0이면 실패(큐가 꽉 찬 상태겠져? ^^)
void Print_Stack(int *start_p); //start_p부터 top_of_stack만큼 큐 요소를 출력한다

int main(){
	int i, j, temp = 0, input;
	int trigger;//분기 저장
	int* startp_of_stack;//큐 시작 주소
	printf("큐 놀이를 시작하기 전 큐의 크기를 정해주세요^^ 0으로 초기화됩니다 : ");
	scanf("%d", &scale_of_stack);
	startp_of_stack = (int*)calloc(scale_of_stack, sizeof(int));
	top_of_stack = 0;

	while (1)
	{
		printf("\n신나고, 재미나는 큐 놀이! 1=PUSH 2=POP 3=Show Stack 4=End");
		scanf("%d", &trigger);
		printf("\n");
		switch (trigger)
		{
		case 1:
			if (top_of_stack == scale_of_stack)
			{
				printf("큐가 꽉 차서 넣을수가 없네요 ㅎ");
				break;
			}
			printf("삽입하실 자료를 입력해주세요 : ");
			scanf("%d", &input);
			if (Push(startp_of_stack, input)) printf("입력 성공!");
			else printf("왠진 모르겠는데 실패했다.");
			break;
		case 2:
			if (top_of_stack == 0)
			{
				printf("큐가 텅 벼서 뺄 수가 없네요 ㅎㅎ");
				break;
			}
			printf("제일 왼쪽에 있는걸 뺍니다.\n");
			temp = Pop(startp_of_stack);
			if (temp != 0) printf("빼기 성공! 뺀 자료는 %d입니다.", temp);
			else printf("왠진 모르겠는데 실패했다.");
			break;
		case 3:
			Print_Stack(startp_of_stack);
			break;
		case 4:
			printf("\n바이바이\n");
			return 0;

		default:
			break;
		}
	}

}

int Pop(int *start_p) //0이면 실패(큐에 아무것도 없는 경우겠져? ^^) 
{
	int i;
	if (top_of_stack == 0) return 0;
	int temp;
	temp = *(start_p + 1);
	for (i = 0; i < top_of_stack; i++)
	{
		*(start_p + i) = *(start_p + i + 1);
	}
	*(start_p + top_of_stack) = 0;
	top_of_stack--;
	return temp;
}
int Push(int *start_p, int input)//1이면 성공, 0이면 실패(큐가 꽉 찬 상태겠져? ^^)
{
	if (top_of_stack == scale_of_stack)
		return 0;
	top_of_stack++;
	*(start_p + top_of_stack) = input;

	return 1;
}
void Print_Stack(int *start_p) //start_p부터 top_of_stack만큼 큐 요소를 출력한다
{
	for (int i = 1; i <= top_of_stack; i++) //top of stack 이 n이면 1부터 n까지 출력해야한다.
	{
		printf("| %5d |", *(start_p + i));
	}
	printf("\n");

}