후기 ¶
- queue와 stack을 왜 배우는지 알게 되었고 개념을 확실하게 알 수 있었습니다. 막판에 queue 구현을 같이 했는데 하기는 열심히 했으나 버그 투성이여서ㅋㅋ새싹 끝나고도 계속 완성시키려고 했으나 자꾸 실패하여 머리가 녹아내리는 줄 알았습니다. 사실 포인터에 대해서는 개념만 알고 간단한 예제 프로그래밍 정도만 해봤을 뿐 써본 적이 많질 않았는데 큐를 구현하면서 '포인터는 수많은 버그를 양산한다'는 윤성우씨의 말씀을 실감하게 되었습니다. - 이지수
이지수 ¶
* 하노이의 탑
이번주 기초프로그래밍 과제가 하노이 탑이더군요. 그래서 가장 먼저 하게 되었습니다.
분명 저번에 영기선배님이 하노이탑 코드를 보여주셔서 해석하느라 뚫어지게 쳐다봤었는데도 정작 과제를 하려니 내가 코드를 쳐다봤다는 사실밖에는 기억이 나지 않았습니다;; 재귀함수 안에 재귀호출을 두 번 한다는 정도??밖에 기억이 안나더군요.
그래서 하노이 탑의 알고리즘을 알고자 하노이 탑 플래시 게임을 계속 해보았습니다. 게임을 하다보니 새싹 때 보았던 기둥을 바꾸는 알고리즘이 이해가 되더군요. 암튼 그렇게 간간히 종이에 끼적이면서 생각하다가 프로그램을 완성하였습니다.
이번주 기초프로그래밍 과제가 하노이 탑이더군요. 그래서 가장 먼저 하게 되었습니다.
분명 저번에 영기선배님이 하노이탑 코드를 보여주셔서 해석하느라 뚫어지게 쳐다봤었는데도 정작 과제를 하려니 내가 코드를 쳐다봤다는 사실밖에는 기억이 나지 않았습니다;; 재귀함수 안에 재귀호출을 두 번 한다는 정도??밖에 기억이 안나더군요.
그래서 하노이 탑의 알고리즘을 알고자 하노이 탑 플래시 게임을 계속 해보았습니다. 게임을 하다보니 새싹 때 보았던 기둥을 바꾸는 알고리즘이 이해가 되더군요. 암튼 그렇게 간간히 종이에 끼적이면서 생각하다가 프로그램을 완성하였습니다.
#pragma warning(disable:4996)
#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도 사랑해주어야겠습니다.
동적할당을 이용해서 순환 큐를 만들었습니다.
처음에 예외처리를 if-else 때려넣으면서 무식하게 하다가 수많은 버그를 양산해서 머리가 폭발하는 줄 알았습니다.
그래서 당분간 큐를 버리고ㅋㅋ하노이탑에 집중을 하다가 오늘 정신이 비교적 맑아서 도전했고 3시간 걸려서 다 풀었습니다.
좋은 알고리즘이란 예외를 최대한 적게 만드는 것이라는 사실을 요즘들어 깨닫고 있습니다.
맨 처음에 프로그램을 작성했을 때는 큐 크기가 2 이상일 때는 되고 1일 때는 아예 안 되길래 큐 크기를 1로 입력받을 때를 대비한 예외함수까지 만들었었는데ㅋㅋ오늘 작성한 프로그램은 큐 크기를 1로 입력받을 때도 잘 처리해주거든요.
어쨌든 덕분에 포인터에 대해 더 잘 이해하게 된 것 같습니다. 그리고 반복문을 for문을 주로 썼는데 for문은 안에 있는 내용을 1번은 꼭 수행하기 때문에 예상치 못한 버그를 만들 수 있다는 것을 깨달았네요. while도 사랑해주어야겠습니다.
#include <stdio.h>
#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"stdio.h"
#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");
}
