SYDev

자료구조 큐에 우선순위를 적용한 우선순위 큐를 이해하고, 힙을 이용해 우선순위 큐를 구현해보자. 우선순위 큐 우선순위 큐(Priority Queue): 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 규칙이 적용된 큐를 의미한다. 우선순위 큐의 구현 방법 배열 기반으로 구현하는 방법 연결 리스트를 기반으로 구현하는 방법 힙(heap)을 이용하는 방법 >> 배열과 연결리스트를 기반으로 하는 방법은 우선순위를 비교할 때, 모든 노드를 대상으로 비교를 진행하기 때문에, 노드의 수가 많아질수록 성능이 저하된다. 따라서, 일반적으로 우선순위 큐는 힙을 이용하여 구현한다. 힙 힙(heap): 완전 이진 트리의 일종으로, 우선순위 큐의 구현을 위해 만들어진 자료구조이다. 자식 노드와 부모 노드의 관계가 ..

계층적 관계(Hierarchical Relationship)를 표현하는 자료구조인 트리(Tree)를 이해하고, 트리를 대표하는 이진트리를 이용해 수식 트리를 구현해보자. 트리 트리(Tree): 트리는 계층적 관계(Hierarchical Relationship)를 표현하는 자료구조이다. 노드(node): 트리의 구성요소에 해당하는 A, B, C, D, E, F와 같은 요소 간선(edge): 노드와 노드를 연결하는 연결선 루트 노드(root node): 트리 구조에서 최상위에 존재하는 A와 같은 노드 단말 노드(terminal node): 아래로 또 다른 노드가 연결되어 있지 않은 E, F, C, D와 같은 노드 내부 노드(internal node): 단말 노드를 제외한 모든 노드로 A, B와 같은 노드 레..

FIFO구조를 가지는 자료구조인 queue에 대해 이해하고, 추가적으로 queue와 비슷한 deque을 구현해보자. 큐 큐은 가장 처음에 들어간 데이터가 가장 먼저 나오는 선입선출, 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)..

LIFO구조를 가지는 자료구조인 stack에 대해 이해하고, 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(Stac..

단순 연결 리스트의 개념을 확장한 원형, 양방향 연결 리스트를 구현해보자. 자료구조를 구현할 때, 먼저 그림으로 그려보고 구조를 파악하는 것이 상당히 도움이 되었다. 원형 연결 리스트(Circular Linked List) 원형 연결 리스트의 기본 구조와 내부 함수는 다음과 같이 도식화할 수 있다. 파일명: CLinkedList.h #ifndef __C_LINKED_LIST_H__ #define __C_LINKED_LIST_H__ #define TRUE 1 #define FALSE 0 typedef int Data; typedef struct _node { Data data; struct _node * next; } Node; typedef struct _CLL { Node * tail; Node * c..

'연결'을 기반으로 하는 리스트의 기본을 이해하고, 구현해보자. 연결 리스트의 개념적인 이해 아래와 같이 메모리가 정적인 배열을 이용해 데이터를 저장하면, 메모리의 길이를 변경하는 것이 불가능하다는 단점이 있다. #include int main(void) { int arr[10]; int readCount = 0; int readData; int i; while(1) { printf("자연수 입력: "); scanf("%d", &readData); if(readData next = NULL; if(head == NULL) head = newNode; else ..

자료구조에서의 추상 자료형(ADT)을 이해하고, 배열 기반 리스트를 구현해보자. 추상 자료형(ADT; Abstract Data Type) ADT: 구체적인 기능의 완성과정을 언급하지 않고, 순수하게 기능이 무엇인지를 나열한 것을 의미한다. 예를 들어 Wallet이라는 구조체가 있을 때, 이 구조체에 돈을 넣을 수도 있고 꺼낼 수도 있다. 이를 ADT로 변환하면 다음과 같다. Wallet의 ADT int TakeOutMoney(Wallet * pw, int coinNum, int billNum) - 첫 번째 인자로 전달된 주소의 지갑에서 돈을 꺼낸다. - 두, 세 번째 인자로 꺼낼 동전의 수와 지폐의 수를 전달한다. - 꺼내고자 하는 돈의 총액이 반환된다. 그리고 그만큼 돈은 차감된다. void PutMo..

구조체 구조체: 하나 이상의 변수들을 그룹화하여 만든 새로운 자료형 구조체 선언 struct computer { int monitor; //멤버 선언 int keyboard; int ram; }; int main() { struct computer c1; //구조체 변수 c1 선언 return 0; } 구조체 초기화 struct computer { int monitor; int keyboard; int ram; }; int main() { struct computer c1 = { 30, 1, 16 }; } 구조체 멤버 접근 c1.monitor = 30;//구조체변수이름.멤버이름 -> 해당 형태로 접근 가능 c1.keyboard = 10; c1.ram = 4; printf("c1의 monitor: %d\n..