1. 예정

  • 시간복잡도
    • 정렬
      - 삽입 정렬
    • 피보나치 수
      - 재귀적 방법
      - 순차적 방법
    • 시간이 남아서 분할 정복.
      - 피보나치 수
      - n개의 점이 주어졌을 때, 가장 짧은 거리의 선분 구하기.
    • 시간이 남아서 동적 프로그래밍.
      - 피보나치 수
  • 스택

2. 참여자

강사 권영기 O
새싹 금강현 O
권준혁 O
이지수 O

3. 참고 자료

  • 정렬(http://mirror.enha.kr/wiki/%EC%A0%95%EB%A0%AC)

4. 숙제

  • 삽입 정렬 구현.
  • 피보나치 수 재귀적 방법으로 구현.
  • 스택 혼자서 구현해보기.
  • 어차피 시험 기간이어서 못할수도 있으니 시험 공부하다가 질리면 하던가 바쁘면 안해도 됨.

5. 후기

  • 항상 예상보다 빨리 진행이 되서 걱정입니다. 앞으로는 숙제를 내야겠습니다. 시험들 잘보세요. - 권영기
  • 정렬과 스택을 배우고 divide&conquer도 살짝 배웠습니다. 이제부터는 전혀 모르는 내용이라 새롭고 재미있었습니다. 권영기 선배님이 알기 쉽게 잘 가르쳐주셔서 이해하는 데에는 별로 어렵지 않았습니다. 하지만 스스로 프로그래밍해보면 어려울 듯 합니다ㅠㅠ 어쨌든 이렇게 도전적인 내용을 배울 수 있어서 좋습니다. 선배님 ppt도 올려주세요!! 바쁘신데 늘 감사합니다ㅠㅠ - 이지수
  • 시간 쪼개서 해주시는데 항상 늦게 가서 죄송할 따름입니다. 성실한 수업태도와 착실하게 숙제를 함으로 보답하겠습니다. 이제부터 슬슬 머리굴리는게 나오는 것 같습니다. 기대됩니다 ㅎ 권준혁

6. 다음 수업

  • 중간고사가 금요일에 끝나서 새싹을 진행할 수 있을 것 같으면, 4월 25일에 진행.
  • 4월 25일에 불가능할 것 같다면, 5월 2일.

7. 숙제

7.1. 권준혁

  1. 피보나치 구현

#pragma warning(disable:4996)
#include<stdio.h>
int pibo(int num);

int main(){
	int input = 0;
	
	printf("피보나치수 몇번째수를 출력할깝쇼? : ");
	scanf("%d", &input);
	printf("\n이거에요 : %d", pibo(input));

}

int pibo(int num){
	if (num == 1 || num == 2) return 1;
	int temp = pibo(num - 1) + pibo(num - 2);
	return temp;

}
  • 삽입정렬 구현

n,k를 입력받아서 1부터 k범위의 숫자를 임의로 n개 받아서 저장하는걸 동적할당을 이용해서 구현해봤습니다
#pragma warning(disable:4996)
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
int random_num(int range); //1부터 range까지의 랜덤한 숫자 하나를 가져옴
void insert_sort(int* start_p, int range);
void swap(int* a, int* b);

int main(){
	int number, range;
	int i, j, temp;
	int *start_p;
	srand(time(NULL));
	printf("몇개의 숫자를 정렬할것입니까? : ");
	scanf("%d", &number);
	printf("숫자의 범위는요? : ");
	scanf("%d", &range);
	start_p = (int*)malloc(sizeof(int) * (number+1));
	*start_p = 0;
	start_p = start_p + 1;//삽입정렬을 위해 앞의 한 공간을 비워둠


	for (i = 0; i < number; i++) //임의의 값을 넣어줌
	{
		*(start_p + i) = random_num(range);
	}
	printf("임의로 배열된 숫자들입니다.\n");
	for (i = 0; i < number; i++) //출력해주자
	{
		printf("%d ", *(start_p + i));
	}
	insert_sort(start_p, number);

	printf("\n삽입정렬 되었습니다.\n");

	for (i = 0; i < number; i++) //출력해주자
	{
		printf("%d ", *(start_p + i));
	}
	printf("끝");
}


int random_num(int range){
	return (rand() % range) + 1;
}

void insert_sort(int* start_p, int range) //start_p의 앞 한자리는 0으로 되있다는 전제이다
{
	int i, j, temp; 
	for (i = 0; i < range; i++)
	{
		for (j = i; j >= 0; j--)//-1까지는 j가 내려갈 수 있다
		{
			if (*(start_p + j) < *(start_p + j - 1)) swap((start_p + j), (start_p + j - 1));
			else break;
		}
	}
}

void swap(int* a, int* b){
	int temp = *a;
	*a = *b;
	*b = temp;
}
  • 스택 구현

#pragma warning(disable:4996)
#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이면 실패(스택에 아무것도 없는 경우겠져? ^^) 
{
	
	if (top_of_stack == 0) return 0;
	int temp;
	temp = *(start_p + top_of_stack);
	*(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 = top_of_stack; i > 0; i--) //top of stack 이 n이면 1부터 n까지 출력해야한다.
	{
		printf("| %5d |\n", *(start_p + i));
	}
	printf("└______┘\n");
}

7.2. 이지수


1. 재귀함수로 피보나치 수열 구현
#pragma warning(disable:4996)
#include <stdio.h>
#include <stdlib.h>

int fibo(int x){
	if (x == 1 || x == 2)
		return 1;
	else
		return fibo(x - 1) + fibo(x - 2);
}
	int main()
	{
		int n, i;
		printf("출력하고 싶은 수열의 항 개수를 입력하세요 : ");
		scanf("%d", &n);
		for (i = 1; i <= n; i++)
			printf("%d ", fibo(i));
		system("pause");
		return 0;
	}

2. 삽입 정렬 구현
#pragma warning(disable:4996)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
	int *align;
	int align_n, sort_n, i = 0;

	printf("정렬할 숫자의 개수를 입력하세요 : ");
	scanf("%d", &align_n);
	align = (int *)malloc(sizeof(int)*align_n);
	printf("정렬할 수열을 입력해 주세요(정수 %d개) : ", align_n);
	for (i=0; i < align_n; i++)
		scanf("%d", align+i);

	
	for (int j = 1; j < align_n ; j++){
		for (sort_n = j; sort_n > 0; sort_n--){
			int temp;
			if (*(align + sort_n) < *(align + sort_n - 1)){
				temp = *(align + sort_n - 1);
				*(align + sort_n - 1) = *(align + sort_n);
				*(align + sort_n) = temp;
			}
			else
				break;
			}
		}
	
	puts("삽입정렬 되었습니다.");
	for (int n=0; n < align_n; n++)
	printf("%d ", *(align+n));

	printf("\n");
        free(align);

	system("pause");
	return 0;
}

3. 스택 구현
너무 늦었네요...ㅎㅎㅎ...

#pragma warning(disable:4996)
#include <stdio.h>
#include <stdlib.h>

int *push(int *topPtr);
int *pop(int *topPtr);
void print_stack(int sizeNum, int num);

int *stack, stackSize;

int main(){
	int n, k = 0;
	int *top;

	printf("Enter a stack size : ");
	scanf("%d", &stackSize);
	stack = (int *)malloc(sizeof(int)*stackSize);

	top = stack;

	while (1){

		printf("Choose an option(1. push 2. pop 3. print stack 4. end program). : ");
		scanf("%d", &n);

		switch (n){

		case 1:

			if (k == stackSize){
				puts("Stack is already full");
				break;
			}

			top = push(top); k++;
			break;

		case 2:

			if (k == 0){
				puts("Stack is empty");
				break;
			}

			top = pop(top); k--;
			break;

		case 3:

			print_stack(stackSize, k);
			break;

		case 4:
			return 0;

		default:
			puts("You have entered a wrong number");

		}
	}

}

void print_stack(int sizeNum, int num){

	int i = sizeNum - 1;

	while (i != num - 1){
		printf("\n\t|%6C|", 32);
		i--;
	}

	while(num - 1 != -1){
		printf("\n\t|%6d|", *(stack + num - 1));
		num--;
	}


	printf("\n\t+------+\n");

}

int *push(int *topPtr){

	int pushNum;

	printf("push할 값을 입력하세요. : ");
	scanf("%d", &pushNum);

	*topPtr = pushNum;
	if (topPtr == stack + stackSize - 1)
		return topPtr;
	return ++topPtr;

}

int *pop(int *topPtr){

	if (topPtr == stack)
		return topPtr;
	return --topPtr;
}

큐를 먼저 했더니 어떻게 할지 금세 감을 잡을 수 있었습니다.

7.3. 권영기

  • 삽입 정렬

#include<stdio.h>
#include<stdlib.h>
const int INF = 0x7FFFFFFF;
int main(void)
{
	int n;
	int *number;
	int i, j;
	scanf("%d", &n);
	number = (int *)malloc(sizeof(int) * (n + 10));
	number[0] = -INF;
	for(i = 1; i<=n; i++){
		scanf("%d", number + i);
	}
	for(i = 1; i<=n; i++){
		int temp = number[i];
		for(j = i - 1; j>=0 && number[j] > temp; j--){
			number[j + 1] = number[j];
		}
		number[j + 1] = temp;
	}
	for(i = 1; i<=n; i++){
		printf("%4d", number[i]);
	}
	return 0;
}
  • 피보나치

#include<stdio.h>
int fibo(int n){
	if(n <= 2)return 1;
	return fibo(n - 1) + fibo(n - 2);
}
int main(void)
{
	int n;
	scanf("%d", &n);
	printf("%d", fibo(n));
	return 0;
}
  • 스택

#include<iostream>
#include<vector>
using namespace std;
template <typename T>
class Stack{
private:
	vector <T> dataVector;
	int top_pointer;
public:
	Stack(){
		top_pointer = -1;
		dataVector.resize(20);
	}
	~Stack(){

	}
	
	void push(T element){
		if(top_pointer == dataVector.size() - 1){
			dataVector.resize(dataVector.size() * 2);
		}
		dataVector[++top_pointer] = element;
	}
	T pop(){
		if(top_pointer < 0){
		}
		return dataVector[top_pointer--];
	}
	T top(){
		return dataVector[top_pointer];
	}
};

int main(void){
	Stack<int> s = Stack<int>();
	Stack<char> sc = Stack<char>();
	for(int i = 0; i<=100; i++){
		s.push(i);
		sc.push(char(i));
	}
	for(int i = 0; i<=100; i++){
		printf("%d\n", s.pop());
		printf("%c\n", sc.pop());
	}
	
}
Retrieved from http://wiki.zeropage.org/wiki.php/새싹교실/2014/다빈치인재반/4회차
last modified 2021-02-07 05:29:50