스택과 시간복잡도

Stack 구조 
= LIFO 구조(= Last In First Out)
= 후입선출 구조 
=> 가장 마지막에 저장된 데이터를 먼저 처리(삭제)한다.
=> 저장된 순의 역순으로 데이터를 처리한다.
=> 입력 커서, 인터넷 뒤로가기, CPU 의 연산, 함수의 호출, RAM 메모리의 STACK 구조, 괄호 연산(괄호의 짝꿍 인식) 등

< Stack 구조 관련 용어 >
1. pop : 데이터를 꺼내는 행위
2. push : 데이터를 저장하는 행위
3. top : 가장 마지막으로 저장된 데이터를 가리키는 역할

============================================================
< 시간 복잡도와 공간 복잡도 >
1) 시간복잡도(Time Complexity) 
: 시간이 얼마나 걸리느냐 

2) 공간복잡도(Space Complexity) 
: 메모리가 얼마나 사용되느냐

1 ~ 1000 중 11과 13의 공배수를 출력 
for(i = 1; i <= 1000; ++i){
if(i % 11 == 0 && i % 13 == 0){
printf("%d", i);
}
}

f(n) = n
n : 데이터의 개수
============================================================
for(i = 143; i <= 1000; i += 143){
printf("%d", i);
}

f(n) = n / 143
============================================================


int a = 1;
f(n) = 1
============================================================

for(i = 1; i <= n; ++i){

}
f(n) = n
============================================================

for(i = 1; i <= n; ++i){
for(j = 1; j <= n; ++j){

}
}
f(n) = n^2
============================================================


for(i = 1; i <= n; ++i){
for(j = 1; j <= n; ++j){

}
}
printf("%d", n);
f(n) = n^2 + 1
============================================================
< 빅-오(Big-O) 표기법 >
시간/공간복잡도의 최대차수만 표기하는 방식 
f(n) = 3n^3 + 5n + 10
==> O(n^3)

O(1) : 1회 수행 
O(N) : N회 수행 (1차원 반복문) 
O(N^2) : 2차원 반복문
O(N^3) : 3차원 반복문
O(logN) : 이진 탐색
O(NlogN) 

 O(N^2) + O(N^3) + O(logN) => O(N^2+ N^3+ logN) (X)
      O(N^3) (O)

#include <stdio.h>
#include <Windows.h>

#define MAX 10

int top = -1;   // 가장 마지막 원소의 위치
int arr[MAX] = {0};

void push(int data){
	// 1. arr[] 이 다 차있니?
	//		==> Stack Overflow!! 출력 후 return
	if(top == MAX - 1){
		printf("Stack Overflow!! \n");
		return;
	}
	// 2. 0 이 들어있는 가장 앞 칸을 찾아서 
	//		그 칸에 data를 저장
	//		==> top을 1 증가, 
	//		==> top번 칸에 data 저장
	arr[++top] = data;

}
void pop(){
	// 1. arr[] 에 원소가 아무것도 없니?
	//		==> Stack Underflow!! 출력 후 return 
	if (top == -1){
		printf("Stack Underflow!! \n");
		return;
	}
	// 2. top 번 칸에 0 저장
	//	  top 을 1 감소
	arr[top--] = 0;
}
void peek(){ 
	// 배열(저장소)에 아무 영향도 주지 않고, 그저 처리할 데이터가 무엇인지 보여주는 역할
	printf("%d가 처리될 차례..\n", arr[top]);
}
void print_all(){
	int i;
	for(i = 0; i < MAX; ++i){
		printf("%d ", arr[i]);
	}
	printf("\n");
}
void main(){
	int data;
	int select;
	while(1){
		print_all();
		printf("1. push() \n");
		printf("2. pop() \n");
		printf("3. peek() \n");
		printf("0. exit \n");
		printf("입력 : "); 
		scanf_s("%d", &select);
		switch(select){
		case 1:
			printf("추가할 정수 : "); scanf_s("%d", &data);
			push(data);
			break;
		case 2:
			pop();
			break;
		case 3:
			peek();
			break;
		case 0:
			exit(0);
		}
		system("pause");
		system("cls");
	} // while
} // main()