새싹교실/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");

	  }
	 }

}

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