목표가 생기면 무작정 달려들어야지. 실패를 두려워 할 여유같은 건 없을 때니까

[순회 종류] ■ 그림(중위, 후위, 전위) 1. 중위 순회: 루트 노드의 왼쪽 자식 노드를 먼저 방문 후에 루트 노드를 중간에 방문하는 방식2. 후위 순회: 루트 노드의 왼쪽 자식, 오른쪽 자식을 방문 후 루트 노드를 마지막에 방문하는 방식3. 전위 순회: 루트 노드를 먼저 방문 후 왼쪽 자식, 오른쪽 자식을 방문하는 방식 [순회의 재귀] ■ 그림(중위 순회 재귀) ■ 이진 트리를 대상으로 중위 순회를 할 경우의 순회 순서1단계: 왼쪽 서브 트리의 순회2단계: 루트 노드의 방문3단계: 오른쪽 서브 트리의 순회 ※ 공집합(NULL) 값을 가진 노드를 방문하기 전까지 하위 단계로 순회를 반복 [소스 코딩] ※ 이전에 사용한 '이진 트리 구현(BinaryTree.h, BinaryTree.c)' 소스를 업데이..

[배열 기반과 연결 리스트 기반] ■ 그림(배열 기반 트리) - 트리가 완성 된 이후부터는 그 트리를 대상으로 매우 빈번한 탐색이 이뤄지기 때문에 연결 리스트보다 탐색이 빠른 이점이 있음- 노드에 번호가 부여됨 ※ 인덱스 '0'은 사용해도 문제없으나 인덱스 번호와 노드 번호 매치를 위해 편의상 사용하지 않음 ■ 그림(연결 리스트 기반 트리) - 연결 리스트 구성 형태와 트리 형태와 일치한다는 점 ※ 우선 연결 리스트 기반으로 구현. 배열 기반은 '완전 이진 트리의 구조를 갖는 '힙(heap)'이라는 자료구조 구현 시 활용할 예정 [이진 트리의 ADT] BTreeNode * MakeBTreeNode(void);- 이진 트리 노드를 생성하여 그 주소 값을 반환 int GetData(BTreeNode * bt..

[트리의 개념]- 트리는 계층적 관계(Hierarchical Relationship)를 표현하는 자료구조 ■ 그림(트리의 계층 개념) ■ 중요 포인트- 데이터의 저장, 검색 및 삭제 등의 기능의 정의보다, 무엇인가를 표현하기에 적절히 정의되었는지가 더 중요 [트리 관련 용어] ■ 그림(트리 표현) ■ 관계- 노드간에는 '부모(Parent), 자식(Child), 형제(Sibling)'의 관계가 성립되어 있음- 노드 'A'는 노드 'B, C, D'의 부모 노드- 노드 'B, C, D'는 노드 'A'의 자식 노드- 노드 'B, C, D'는 부모 노드가 같으므로, 서로가 서로에게 형제 노드 1. 노드(Node)- 트리의 구성요소에 해당하는 'A, B, C, D, E, F'와 같은 요소 2. 간선(Edge)- 노..

[덱의 개념] - 스택과 큐의 특성의 조합한 형태로서 데이터를 앞으로도 뒤로도 넣을 수 있고, 앞으로도 뒤로 뺄 수 있는 자료구조 [덱의 ADT] void DequeInit(Deque * pdeq);- 덱의 초기화를 진행- 덱 생성 후 제일 먼저 호출되어야 하는 함수 int DQIsEmpty(Deque * pdeq);- 덱이 빈 경우 TRUE(1)을 반환, 그렇지 않은 경우 FALSE(0)을 반환 void DQAddFirst(Deque * pdeq, int data);- 덱의 '머리'에 데이터를 저장. data로 전달된 값을 저장 void DQAddLast(Deque * pdeq, int data);- 덱의 '꼬리'에 데이터를 저장. data로 전달된 값을 저장 int DQRemoveFirst(Deque..

[주제] - 주문한 음식이 포장되어 나오기를 기다리는 고객을 위한 대기실을 만드려고 함 [조건] - 운영 시간은 1시간- 고객의 첫 주문 이후 15초당 다음 1명씩 주문- 고객은 총 3가지 햄버거 중 무작위로 1개만 주문가능- 햄버거 조리 시간(치즈버거 12초, 불고기버거 15초, 더블버거 24초)- 한 번에 하나의 햄버거만 조리가능- 조리가 끝나기 전까지 다음 주문을 받지 않음- 주문 처리가 된 고객은 대기실에서 나옴 [목표] - 1시간 동안 여러 종류의 햄버거를 요리하는 상황에서 고객을 대기시킬 수 있는 대기실의 크기를 산출하기 위하여 크기에 따라 얼마나 안정적으로 수용할 수 있는지 확률적으로 나타내기 ※ 예) 수용인원이 30명인 공간: 안정적으로 고객을 수용할 확률은 50%(시뮬 10회 시도 시 5..

[연결 리스트 기반 스택과 큐의 차이점] - 스택은 'push'와 'pop'이 같은 위치에서 처리가 되는 반면, 큐는 'enqueue'와 'dequeue'가 다른 위치에서 처리가 됨 [소스 코딩] ■ ListBaseQueue.h #ifndef LISTBASEQUEUE_H_#define LISTBASEQUEUE_H_ #define TRUE 1#define FALSE 0 typedef struct _node{ int data; struct _node * next;} Node; typedef struct _lQueue{ Node * front; // 삭제할 노드를 가리키는 용도 Node * rear; // 생성된 노드를 가리키는 용도} LQueue; typedef LQueue Queue; void QueueI..

[소스 코딩] ■ CircularQueue.h #ifndef CIRCULARQUEUE_H_#define CIRCULARQUEUE_H_ #define TRUE 1#define FALSE 0 #define QUE_LEN 100 typedef struct _cQueue{ int front; // 삭제할 데이터의 위치를 가리키는 변수 int rear; // 삽입할 데이터의 위치를 가리키는 변수 int queArr[QUE_LEN]; // QUE_LEN 길이를 갖는 큐 배열} CQueue; typedef CQueue Queue; void QueueInit(Queue * pq); // 큐 초기화 함수int QIsEmpty(Queue * pq); // 큐에 데이터가 존재하는지 확인하는 함수 void Enqueue(Qu..

[enqueue의 연산방식] ※ F(Front): 큐의 앞(출구)을 가리키는 포인터 변수※ R(Rear): 큐의 뒤(입구)를 가리키는 포인터 변수 - enqueue 연산 시 R이 배열의 다음 칸을 가리키고 그 자리에 새로 입력된 데이터를 저장- 첫 데이터가 저장될 때는 F와 R이 같은 위치를 가리킴 [dequeue] ■ 보편적인 배열의 삭제방식 - dequeue 연산 시 반환할 데이터를 배열의 맨 앞부분으로 이동 시키는 방식- F의 위치는 고정된 채로 데이터가 이동하기 때문에 F가 불필요- dequeue 연산 시마다 저장된 데이터를 한 칸씩 이동시켜야 하는 단점이 존재 ★ ■ 일반적인 방식 - F를 R처럼 한 칸씩 오른쪽으로 이동하면서 데이터를 삭제- 데이터의 위치를 옮길 필요없음 ■ 문제가 되는 상황 ..

[큐의 개념]- 먼저 저장된 데이터가 먼저 나오는 선입선출(FIFO. First-In, First-Out) 구조의 자료구조 [큐의 ADT]void QueueInit(Queue * pq);- 큐의 초기화를 진행- 큐 생성 후 제일 먼저 호출되어야 하는 함수 int QIsEmpty(Queue * pq);- 큐가 빈 경우 TRUE(1)을, 그렇지 않은 경우 FALSE(0)을 반환 void Enqueue(Queue * pq, Data data);- 큐에 데이터를 저장. 매개변수 data로 전달된 값을 저장 Data Dequeue(Queue * pq);- 저장순서가 가장 앞선 데이터를 삭제- 삭제된 데이터는 반환- 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 함 Data QPeek(Queue..

[계산기 처리 과정] - 중위표기법 수식 → ConvToRPNExp 함수(후위표기법으로 변환) → EvalRPNExp 함수(후위표기법 계산) → 연산 결과 [소스 코딩] ※ 스택은 이전에 '연결 리스트 기반으로 구현된 스택' 소스를 활용※ 후위표기법으로 변환 처리는 이전에 'InfixToPostfix' 소스를 활용※ 후위표기법 계산 처리는 이전에 'PostCalculator' 소스를 활용 ■ ListBaseStack.h #ifndef __LB_STACK_H__#define __LB_STACK_H__ #define TRUE 1#define FALSE 0 typedef int Data; // 사용자 정의 int형 Data 선언 typedef struct _node // 사용자 정의 구조체 'Node' 정의{..

[소스 코딩]※ 스택은 이전에 '연결 리스트 기반으로 구현된 스택' 소스를 활용 ■ ListBaseStack.h #ifndef __LB_STACK_H__#define __LB_STACK_H__ #define TRUE 1#define FALSE 0 typedef int Data; // 사용자 정의 int형 Data 선언 typedef struct _node // 사용자 정의 구조체 'Node' 정의{ Data data; // 입력 받은 데이터를 저장할 data 선언 struct _node * next; // 다음 노드를 가리킬 노드 포인터 next 선언} Node; typedef struct _listStack // 사용자 정의 구조체 'ListStack' 정의{ Node * head; // ListSta..

[구현 원칙]- 피연산자는 무조건 스택으로 옮김- 수식 조회 시 연산자를 만나면 스택에서 2개의 피연산자를 꺼내어 계산 처리- 계산결과는 다시 스택에 저장 [계산 시 중요 포인트]- 스택에서 먼저 꺼낸 피연산자가 두 번째 피연산자가 됨(오른쪽)- 나중에 꺼낸 피연산자가 첫 번째 피연산자가 됨(왼쪽) [후위표기법 계산 과정] - 중위표기법에서 후위표기법으로 변환된 상태- 변환된 수식에서 맨 왼쪽부터 하나씩 처리 - 피연산자는 무조건 스택에 저장 - 피연산자는 스택에 저장 - 피연산자는 스택에 저장 - 연산자는 계산 수식으로 이동 - 연산자가 조회되면 스택에서 2개의 피연산자를 꺼냄- 처음 꺼낸 피연산자는 계산 수식의 연산자 '오른쪽'으로 이동- 다음 꺼낸 피연산자는 계산 수식의 연산자 '왼쪽'으로 이동 -..

[소스 코딩]※ 스택은 이전에 '연결 리스트 기반으로 구현된 스택' 소스를 활용 ■ ListBaseStack.h #ifndef __LB_STACK_H__#define __LB_STACK_H__ #define TRUE 1#define FALSE 0 typedef int Data; // 사용자 정의 int형 Data 선언 typedef struct _node // 사용자 정의 구조체 'Node' 정의{ Data data; // 입력 받은 데이터를 저장할 data 선언 struct _node * next; // 다음 노드를 가리킬 노드 포인터 next 선언} Node; typedef struct _listStack // 사용자 정의 구조체 'ListStack' 정의{ Node * head; // ListSta..

[구현하는 계산기 기능]- '후위 표기법 변환 알고리즘'을 사용하여 구현└ 중위 표기법 수식 방식으로 사용자에게 입력 받음 → 프로그램에서 후위 표기법 수식으로 변경 → 계산 및 출력 ※ 이유: 연산자의 우선순위를 신경쓰지 않아도 되고, 소괄호도 처리할 필요가 없기 때문 [구현 시 중요한 부분]- 소괄호를 파악하여 그 부분을 먼저 연산- 연산자의 우선순위를 근거로 연산의 순위를 결정 [구현 시 제한사항]- 수식을 이루는 피연산자는 한자리 숫자(0~9)로만 이뤄진다고 가정 [수식의 표기법] ※ 예) 5 + 2 / 7 1. 중위 표기법(infix notation): 5 + 2 / 7- 피연산자 사이에 연산자가 존재하는 일반적인 표기법 2. 전위 표기법(prefix notation): + 5 / 2 7- 각 ..

[소스 코딩]■ ListBaseStack.h#ifndef __LB_STACK_H__#define __LB_STACK_H__ #define TRUE 1#define FALSE 0 typedef int Data; // 사용자 정의 int형 Data 선언 typedef struct _node // 사용자 정의 구조체 'Node' 정의{ Data data; // 입력 받은 데이터를 저장할 data 선언 struct _node * next; // 다음 노드를 가리킬 노드 포인터 next 선언} Node; typedef struct _listStack // 사용자 정의 구조체 'ListStack' 정의{ Node * head; // ListStack에 노드 포인터 'head' 선언} ListStack; typede..

[소스 코딩] ■ ArrayBaseStack.h12345678910111213141516171819202122232425#ifndef __AB_STACK_H__#define __AB_STACK_H__ #define TRUE 1#define FALSE 0#define STACK_LEN 100 typedef int Data; // 사용자 정의 int형 Data 선언 typedef struct _arrayStack // 사용자 정의 구조체 'ArrayStack' 정의{ Data stackArr[STACK_LEN]; // 100의 배열 구조를 갖는 스택 선언 int topIndex; // 가장 위(마지막 데이터)를 가리키는 topIndex 선언} ArrayStack; typedef ArrayStack Stack..

[스택의 개념] - 나중에 저장된 데이터가 먼저 나오는 후입선출(LIFO. Last-In, First-Out) 구조의 자료구조 [스택의 ADT] void StackInit(Stack * pstack) - 스택의 초기화를 진행 - 스택 생성 후 제일 먼저 호출되어야 하는 함수 int SIsEmpty(Stack * pstack) - 스택이 빈 경우 TRUE(1)을, 그렇지 않은 경우 FALSE(0)을 반환 void SPush(Stack * pstack, Data data) - 스택에 데이터를 저장. 매개변수 data를 전달된 값을 저장 Data SPop(Stack * pstack) - 마지막에 저장된 요소를 삭제 ★ - 삭제된 데이터는 반환 - 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어..