분류 전체보기 (291) 썸네일형 리스트형 Memory allocation using explicit free block tracking and first-fit method Memory allocation using explicit free block tracking and first-fit method LIFO 방식 + first fit 🔎 explicit memory 요소 저장하기 명시적으로 메모리 공간 할당 이용 자료구조 : Array(주소할당시 사용), Linked List(연결 리스트) 새로운 가용블록 LIFO 순으로 유지. 지금 구현한 first fit의 반환은 선형시간에 수행된다. 갸용블록이 분산되어 있지 않고 최근에 해제된 블록이 자주 재할당 될 때 적합. 장점 검색속도가 빠르고 메모리 할당, 해제 쉬움 최근에 해제된 블록이 다시 할당될 가능성이 높기 때문에 메모리를 더 잘 활용할 수 있다. 단점 내부단편화 발생 가용 블록을 검색할 때 매전 전체 리스트를 순회.. Memory allocation using implicit free block tracking and best-fit method Memory allocation using implicit free block tracking and best-fit method ✏️ Best Fit이란? heap의 처음부터 끝까지 모든 block 리스트를 탐색하면서 가장 padding이 적은 block를 찾아 그 곳에 data할당하는 방식 장점 최대한 남는 공간이 적게 memory를 할당하므로 외부단편화를 줄일 수 있다. 작은 메모리 블록이 많이 사용될 때 first fit보다 효율적이다. 단점 블록을 찾는 과정에서 시간이 많이 소요된다. 할당 가능한 블록을 찾는 과정이 복잡하고 비용이 많이 발생할 수 있다. 대부분의 경우 first fit보다 느리고 성능이 안좋다. best fit이 남긴 작은 내부 단편화는 시간이 지날 수록 증가한다. Best f.. Memory allocation using implicit free block tracking and next-fit method Memory allocation using implicit free block tracking and next-fit method ✏️Next fit 이란? 검색을 시작하는 위치를 이전에 할당한 메모리 블록의 다음 블록으로 설정해 검색 시간을 최적화 할 수 있다. 장점 : first fit 이후 block만 탐색하면 되니 탐색 범위가 줄어들어 first fit보다 성증이 더 좋을 가능성이 높다. 단점 : 탐색 범위가 너무 작아 제한된 경우, 이전 블록과 연결된 빈공간을 발견하지 못해 fragmentation(단편화) 문제가 발생할 확률이 높다. 즉, 최적의 메모리 사용이 아닐 수 있다. next fit은 할당 요청이 빈벌할 경우 성능이 저하되는 문제가 있다. 2023.04.10 - [CS(Computer.. Memory allocation using implicit free block tracking and first-fit method Memory allocation using implicit free block tracking and first-fit method 2023.04.12 - [CS(ComputerScience)] - 묵시적 가용 리스트 Implicit Free List✏️ First Fit 이란?리스트의 처음부터 검색해 크기가 맞는 첫번째 가용 블록을 선택 장점 리스트의 마지막에 가장 큰 가용블록을 남겨두는 경향이 있다. 단점 리스트의 앞부분에 작은 가용블록들을 남겨두는 경향이 있어서 큰 블록을 찾는 경우 검색시간이 늘어난다. block size & alloc/* Paxk a size and allocated bit into a word */ // size는 블록의 크기 정보를 저장 // alloc은 블록의 할당 여부(0.. 자료구조, RBtree 구현 자료구조, RBtree 구현 2023.04.04 - [알고리즘] - 자료구조, AVL 📌 RBtree란? AVL 자가균형트리의 한 종류로, 가장 많이 사용되는 균형 이진탐색트리이다. 다음과 같은 속성을 지닌다. 1. 모든노드는 red 혹은 black 2. 루트 노드는 black 3. 모든 nil(leaf)노드는 black 4. red의 자녀들은 black(red가 연속적으로 존재할 수 없다) 5. 임의의 노드에서 자손 nil노드들까지 가는 black 수는 같다(자기자신제외) 자가균형트리 AVL에서는 양쪽 부트리 높이가 중요하다. 그러므로 5번 속성이 굉장히 중요하다. 📌 이러한 자료 구조가 필요한 이유? 중간값 자료가 필요할 때! 다른 말로, 최솟값 & 최댓값이 필요한 경우(sort)가 아닐때. 데이터 .. 자료구조, rbtree delete 자료구조, rbtree delete 삭제 역시, 해당 노드를 삭제했을 때, 트리의 균형이 깨지는지 여부가 중요하다. 트리 균형에 위반되지 않는 조건 1. 삭제 노드의 컬러가 Red인 경우 2. 삭제 노드의 컬러가 Black이고 자식이 1개일 경우(유일한 자식) 이 외의 케이스는 모두 트리 균형이 깨질 수 있다. 📌 RB-Transplant 기존 노드의 부모 노드(u.p)를 새로운 노드의 부모(v.p)로 설정해주므로써 노드를 교체하는 함수이다. 📄 rbtree.c void rbtree_transplant(rbtree *t, node_t *u, node_t *v){ if(u->parent == t->nil){ t->root = v; } else if (u == u->parent->left){ u->paren.. 자료구조, rbtree insert 자료구조, rbtree insert📌 RB-Insert 삽입노드는 항상 RED 왜? 삽입 후 모든 경로에 Black Height 영향을 주지 않기 때문.root부터 시작해 트리를 순회하면서 z노드(삽입노드)의 부모 위치를 찾아줍니다. 부모 위치(y)를 찾은 뒤 z노드의 부모를 y노드를 가리키도록 포인터로 설정해주고 z노드의 자식들은 모두 nil노드로, 컬러는 빨간색으로 설정해줍니다. 그런 다음, RB트리의 균형을 맞춰주는 함수로 이동! 📄 rbtree.cnode_t *rbtree_insert(rbtree *t, const key_t key) { // TODO: implement insert node_t *y = t->nil; // y will be parent of z node_t *x = t->root.. 자료구조, AVL Left-Rotate & Right-Rotate 구현 자료구조, AVL Left-Rotate & Right-Rotate 구현 2023.04.02 - [알고리즘] - 자료 구조, Linked List 2023.04.02 - [알고리즘] - 자료구조, Binary Search Tree 저번에 Linked List와 BST를 공부하면서 AVL을 가볍게 공부해봤다. 오늘은 AVL에 대해서 공부한 내용을 정리해 보려고 한다. 📌 AVL이란? Adelson-Velsky, Landis 사람 이름(소련, 1964년) 약자로 자가균형트리를 의미한다. 모든 노드에 대해서 왼쪽부트리와 오른쪽 부트리의 높이차가 1이하인 BST를 의미한다. BST AVL 차이가 보이는가? BST는 루트 노드에서 오른쪽 부트리와 왼쪽 부트리의 높이차가 2로, 1이하가 아니므로 AVL이 아니다. 반.. 자료구조, Binary Search Tree 자료구조, Binary Search Tree Binary Search Tree 📌 BST란? 트리 자료구조의 한 종류 부모노드보다 작은 값은 왼쪽 자식 노드에, 부모노드보다 큰 값은 오른쪽 자식 노드에 저장하는 방식으로 데이터 저장 📌 장점 탐색, 삽입, 삭제 연산 시 시간복잡도 O(log n) 최대 2개의 자식 노드를 가지므로 이진 탐색 트리에서 데이터를 탐색할 때 절반 이하의 노드를 탐색한다. 데이터가 정렬된 상태를 유지하므로 중위순회(왼쪽서브노드 → 루트 → 오른쪽서브노드)하면 오름차순으로 정렬된 값을 얻을 수 있다. 📌 단점 이상적인 BST 모양이 아닐 경우(균형잡힌 이진 탐색트리) 경우, 시간 복잡도가 O(n)에 수렴한다. 이러한 최악의 경우를 피하기 위해, 데이터를 삽입할 때마다 트리의 균형을.. 자료 구조, Linked List 자료 구조, Linked List📌 Array 와 Linked ListArrayLinked List데이터 검색(index 접근)데이터 삽입 / 삭제(pointer접근)정적메모리동적메모리(Heap 영역)✏️ 자기 참조 구조체 // 자기 참조 구조체 // 포인터(주소)로 연결하는 데이터. 데이터 적재문제 해결? struct node { // data1, data2는 구조체에 담을 수 있는 데이터 예시 // 각각의 노드에 서로다른 유형의 여러 개 데이터를 저장할 수 있음 int data1; char data2; struct node * link; // 포인터부 }; data부와 포인터부로 나누어져 있는 노드 구조체를 만든다. 일종의 붕어빵틀! 붕어빵틀을 이용해 여러 노드들(붕어빵)을 만들 수 있다. data부.. 이전 1 ··· 6 7 8 9 10 11 12 ··· 30 다음 목록 더보기
