공부 기록장 💻

#include #include typedef struct { int id;// 기계의 번호 int avail;// 기계가 사용 가능하게 되는 종료 시간 (키값) }element; #define MAX_ELEMENT 20 typedef struct {// 히프 구조체 element heap[MAX_ELEMENT]; int heap_size; }HeapType; // 히프 구조체 동적 할당 HeapType* create() { return (HeapType*)malloc(sizeof(HeapType)); } // 히프의 사이즈 초기화 void init(HeapType* h) { h->heap_size = 0; } // 최소 히프 구현하는 삽입 함수 (작업 할당 후 기계를 다시 삽입) void insert_..

우선순위 큐(priority queue)는 각 요소들이 우선 순위값을 가지고 있으며, 우선 순위가 높은 데이터가 먼저 나가게 되는 구조이다. 우선순위 큐에는 가장 우선 순위가 낮은 요소를 먼저 삭제하는 최소 우선순위 큐, 그리고 반대로 우선 순위가 높은 요소가 먼저 삭제되는 최대 우선순위 큐가 있다. 히프(heap)는 우선순위 큐를 구현하는 가장 효율적인 구조이다. 히프는 완전 이진 트리의 일종으로, 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내는 경우에 매우 유리한 자료 구조이다. 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진 트리로 구현된 것을 최대 히프(max heap),0 반대로 노드의 키 값이 자식 노드의 것보다 항상 작은 히프를 최소 히프(min heap)라..

이진 탐색 트리(Binary Search Tree)는 이진 트리 기반의 탐색을 위한 자료구조이다. 이진 탐색 트리의 정의 모든 원소의 키는 유일한 키를 가진다. 왼쪽 서브 트리 키들은 루트 키보다 작다. 오른쪽 서브 트리의 키들은 루트의 키보다 크다. 왼쪽, 오른쪽 서브 트리 모두 이진 탐색 트리이다. 위의 이진 탐색 트리에서, 15의 값을 가진 노드의 왼쪽 서브트리에 있는 값들(5,7,10)은 루트 노드인 15보다 모두 작고, 오른쪽 서브트리에 있는 값들(16, 18, 19, 20)은 모두 15보다 큰 값들이다. 이진 탐색 트리를 중위 순회 방법으로 순회하면, 5 -> 7 -> 10 -> 15 -> 16 -> 18 -> 19 -> 20 -> 22 -> 36 -> 45 ->60 으로 숫자들의 크기 순이다..

이진 트리 순회는 순환 호출을 사용하지만, 함수를 반복해서 호출해야 한다는 점에서 비효율적이다. 노드의 개수가 많아지고 트리의 높이가 커지게 되는 경우 프로그램 실행 시간의 측면에서 상당히 비효율적이다. 따라서 순회를 스택을 이용한 순환 호출이 아닌, 링크에 저장되어 있는 주소를 이용하여 다음 노드로 이동하는 반복 구조의 스레드 이진 트리를 고려해볼 수 있다. 이진 트리의 노드에는 많은 NULL링크들이 존재한다. 트리의 노드 개수를 n개라고 하면, 총 링크의 개수는 2n개이고, 이들 링크 중 n-1개의 링크들이 루트노드를 제외한 n-1개의 다른 노드를 가리킨다. 따라서, 2n개 중에서 n+1개의 링크는 NULL임을 알 수 있고, 이들 null 링크를 활용하여 순환 호출 없이 트리의 노드들을 순회할 수 있..

전체 노드의 개수 루트 노드 + 왼쪽 서브 트리의 노드들 + 오른쪽 서브 트리의 노드들 // 전체 노드의 개수 (루트 노드 + 왼쪽 서브 트리 + 오른쪽 서브트리) int get_node_count(TreeNode* node) { int count = 0; if (node != NULL) count = 1 + get_node_count(node->left) + get_node_count(node->right); return count; } 단말 노드의 개수 노드의 왼쪽/오른쪽 서브 노드가 없는 경우 count값 증가 // 단말 노드 개수 (왼쪽/오른쪽 자식이 동시에 0인 경우) int get_leaf_count(TreeNode* node) { int count = 0; if (node != NULL) i..

이진 트리는 수식 트리(expression tree)를 처리하는데 사용될 수 있다. 수식 트리는 기본적으로 연산자(+, -, *, / 등)와 피연산자(정수, 실수 등)으로 만들어진다. 피연산자들은 단말노드가 되며 연산자는 비단말 노드가 된다. 스택을 이용한 후위 표기 수식을 떠올려보자. 피연산자이면 스택에 삽입하고, 연산자이면 스택에서 필요한 수만큼의 피연산자를 꺼내 연산을 실행하고, 그 연산 결과를 다시 스택에 넣는 방법이었다. 이번에는 후위 표기 수식이 아닌, '수식 트리'의 구조로 수식이 표현된다. 수식 트리의 루트 노드는 연산자이고, 연산자의 피연산자인 자식 노드들을 계산하여 전체 수식을 계산해보자. 루트 노드보다 자식 노드들을 먼저 방문하는 후위 순회 방법을 사용하여 계산을 진행해보자. /* *..

레벨 순회(level_order)는 각 노드를 레벨 순으로 검사하는 순회 방법이다. 레벨 1인 루트 노드부터 시작하여, 아래로 내려갈 수록 증가되는 각 레벨을 좌에서 우로 방문한다. 레벨 순회는 큐 구조를 사용하여 구현한다. 레벨 순회는 큐에 하나란도 노드가 있으면, 계속 반복하는 코드로 이루어져 있다. 먼저 큐에 있는 노드를 꺼내어 방문한 다음, 그 노드의 자식 노드를 큐에 삽입하는 것으로 한번의 반복을 끝낸다. #include #include typedef struct TreeNode { int data; struct TreeNode* left, * right; }TreeNode; #define MAX_QUEUE_SIZE 100 typedef TreeNode* element; typedef struc..

순환을 이용한 이진 트리 중위, 전위, 후위 순회 #include #include // 이진 트리 노드 구조체 typedef struct TreeNode { int data; struct TreeNode* left, * right; }TreeNode; // 15 // 4 20 // 1 16 25 TreeNode n1 = { 1, NULL, NULL }; TreeNode n2 = { 4, &n1, NULL }; TreeNode n3 = { 16, NULL, NULL }; TreeNode n4 = { 25, NULL, NULL }; TreeNode n5 = { 20, &n3, &n4 }; TreeNode n6 = { 15, &n2, &n5 }; TreeNode* root = &n6; // 중위 순회 void..

스택의 개념, 구조와 구현 스택을 이용한 괄호 검사 프로그램 스택 - 후위 표기 수식 계산과 중위에서 후위 표기로의 변환 스택 - 두 자리 이상의 숫자에 대한 후위 표기 수식 연산 프로그램 스택 - 미로 탐색 프로그램 연결리스트로 표현한 스택 구조 큐의 개념과 구조, 구현 / 선형, 원형 큐 원형 큐 응용 - 오름차순으로 큐에 데이터 삽입 덱의 개념과 구조, 구현 단순 연결 리스트 간단한 예제들 단순 연결 리스트 실습 + 역순 연산, 버블 정렬 연결 리스트 - 메타 구조체 (정렬, 역순, 탐색, 최대/최소) 연결 리스트 - 특정 위치에 데이터 삽입/삭제 (선행 노드의 포인터) 원형 연결 리스트의 개념, 구조와 구현 연결 리스트로 표현한 다항식의 연산 (tail,..

#include #include #include typedef char* element; typedef struct DListNode { struct DListNode* llink; struct DListNode* rlink; element data; }DListNode; DListNode* current; // 현재 위치(현재 play되는 곡) void init(DListNode* head) { head->rlink = head; head->llink = head; } void dinsert(DListNode* prev, element data) { DListNode* new_node = (DListNode*)malloc(sizeof(DListNode)); new_node->data = (char*)m..

특정 위치에 새로운 데이터(노드)를 삽입하고, 삭제할 수 있는 연결 리스트 프로그램이다. data.txt 20074241 마바사 50 90 95 20074242 가나다 80 95 85 20074243 라마바 70 60 95 20074244 사아자 50 30 65 add_last() 함수를 이용 #include #include #include #define TRUE 1 #define FALSE 0 typedef struct element { int nId; char* name; int nKor, nEng, nMath, nSum; double dAvg; }element; typedef struct ListNode{ element data; struct ListNode* link; }ListNode; type..

data.txt 30 50 10 40 20 // 원형큐 응용 - 큐의 데이터를 오름차순으로 정렬하고 출력하기 // 숫자가 낮은 순서대로 저장 #include #define MAX_QUEUE_SIZE 100 typedef struct { int nPriority; // 큐의 요소 값 (낮은 순대로 저장하기 위함) }QueueObject; QueueObject queue[MAX_QUEUE_SIZE]; // 원형 큐를 배열리스트로 선언 int front, rear; // initialize void init_queue() { front = rear = 0; } // isEmpty int isEmpty() { return(front == rear); } // isFull int isFull() { return ..

덱은, 기존의 원형 큐에서 일부 기능이 추가된, 전단과 후단 양쪽 모두에서 삽입과 삭제의 입출력과 반환이 가능한 원형 큐이다. 원형 큐의 구조와 구현 https://dream-and-develop.tistory.com/102 덱(DEQUE : Double-Ended Queue) 덱(Deque) 은 큐의 전단(front)과 후단(rear) 에서 모두 입출력(삽입/삭제)가 가능한 큐이다. 덱의 추상 자료형은 다음과 같다. - create(MAX) : 구조체 DequeType을 구현하여 구조체 변수를 선언하는 것과 동일하다. - init(dq) : 덱을 초기화한다. 덱의 rear, front 멤버 변수를 각각 0으로 설정한다. - is_empty(dq) : 큐가 공백 상태인지 체크한다. 기존의 원형 큐와 동일..

원형 연결 리스트의 구조 - 마지막 노드가 첫번째 노드를 가리키게 하여 리스트의 구조를 원형으로 만든 연결 리스트 => 마지막 노드의 링크필드가 NULL 이 아닌, 첫번째 노드의 주소이다. 장점 - 하나의 노드에서 다른 모든 노드로의 접근이 가능 - 하나의 노드에서 링크를 계속 따라가면 결국 모든 노드를 거쳐 자기 자신으로 되돌아오는 것이 가능 - 노드의 삽입과 삭제가 단순 연결 리스트보다는 용이함 - 특히, 리스트의 끝에 노드를 삽입하는 연산이 단순 연결리스트보다 효율적 -> 헤드 포인터에서 시작하여 모든 노드를 거쳐 마지막에 삽입하는 것이 아니라, 헤드포인터가 마지막 노드를 가리키도록 구성하면 리스트의 처음과 끝에 노드를 삽입할 수 있다. 원형 연결 리스트의 구현 헤드포인터 head는 항상 마지막 노..

삽입과 삭제가 한 곳(top)에서만 이루어는 후입선출(LIFO)의 입출력 구조를 가졌던 스택(Stack)과 달리, 배열의 양 끝에서 입력과 출력이 이루어지는 큐(Queue)에 대해서 알아보자! 큐(Queue) 큐(Queue) 는 리스트의 앞 부분에서는 삭제가, 뒷 부분에서는 삽입이 이루어지는, 먼저 삽입된 자료가 먼저 삭제되는 선입선출(FIFO)의 입출력 구조로 운영된다. 다음과 같은 전단(front)과 후단(rear)이 리스트의 양 끝을 가리키게 된다. - 전단(front) : 데이터의 삭제 연산 (가장 먼저 들왔던 데이터가 쌓여있는 쪽) -> dequeue() 연산 - 후단(rear) : 데이터의 삽입 연산 (가장 나중에, 최근에 삽입된 데이터가 쌓여있는 쪽) -> enqueue() 연산 큐의 ADT..

#include #include #define MAX_STACK_SIZE 100// 스택의 크기 #define MAZE_SIZE 6// 6*6 미로 // 좌표(x,y)로 구성된 스택 typedef struct StackObjectRec { short r;// row short c;// column }StackObject; StackObject stack[MAX_STACK_SIZE];// x,y 좌표로 구성된 스택 선언 int top = -1; // top 값 초기화 StackObject here = { 1,0 };// 미로 탐색하며 이동하는 현재 위치값 StackObject entry = { 1,0 };// 미로의 시작 위치 // 미로 - 이동 가능한 경로는 '0'으로 표시, 출구는'x'로 표시 char..

연결리스트에서 head가 가리키는 값에 새로운 노드를 추가하는 구조와 스택 구조는 매우 유사하다. 첫 부분에 노드를 추가하는 (insert_first) 연결 리스트와 구조가 유사하며 top을 가리키는 포인터가 있다는 것만 조금 다르다. // 연결리스트를 이용한 스택 구조 #include #include typedef int StackObject; // Object에 대한 structure과 object를 담은 스택 typedef struct StackRec { StackObject item; // 데이터필드 struct StackRec* link; // 링크필드 : next item의 주소를 담은 포인터 }StackRec; // link 포인터를 따라가며 가장 마지막에 삽ㅇ비한 StackRec의 Obje..

y = a * (b-c) + d/c 수식(expression)은 연산자, 피연산자, 괄호로 이루어져 있다. 연산자들은 우선순위가 있어 우선순위가 높은 연산자가 먼저 계산된다. 위의 수식에서는 괄호 내의 식이 가장 우선순위가 높기 때문에, 괄호 안의 뺄셈이 가장 먼저 계산되고, 이어서 곱셈, 나눗셈, 덧셈 순으로 계산된다. 중위표기 수식 : y=a*(b-c)+d/c 후위표기 수식(postfix notation) : y=abc-*dc/+ 프로그래머가 수식을 연산자가 피연산자 사이에 위치한 중위표기법으로 작성하면, 컴파일러는 이것을 연산자가 피연산자 뒤에 위치하는 후위표기법으로 변환한 후에 스택을 이용해 계산한다. 후위 표기법을 사용하는 이유는? 1. 괄호가 필요 없다. 괄호를 쓰지 않고도 우선 계산하여야 할..

data.txt {A[(i+1)]=0} {B[100-(i+5)]*5} {C/(5/5*(5-4)} (10+5)-(30-20) 전체 코드 : #include #include #define MAX_STACK_SIZE 100 typedef char element; typedef struct{ element data[MAX_STACK_SIZE]; int top; }StackType; void init_stack(StackType* s) { s->top = -1; } int is_empty(StackType* s) { return (s->top == -1); } int is_full(StackType* s) { return (s->top == (MAX_STACK_SIZE - 1)); } void push(Stack..

스택이란? 스마트폰, 컴퓨터에서 '뒤로 가기'(undo 기능 - Ctrl+z)와 같은 기능, 혹은 일상생활에서 볼 수 있는 책상 위에 쌓여있는 책 등과 같이 자료가 차곡차곡 쌓여있는 구조를 스택 형태의 예라 할 수 있다. 순환 호출 시, 함수가 호출될 때마다 복귀 주소가 저장되는 활성 레코드가 운영체제가 사용하는 시스템 스택에 쌓이는 것 또한 컴퓨터 내의 스택의 사용 예이다. 최근에 들어온 자료가 가장 위에 있게 되고, 먼저 나가게 되는 구조가 바로 스택이고, 이러한 입출력 형태를 후입선출(LIFO: Last-In First-Out)이라고 한다. 스택에 저장되는 데이터를 요소(element)라 부른다. 스택에서 요소에 대한 입출력이 이루어지는 부분을 스택 상단(stack top)이라 하고, 반대쪽 바닥 ..