크래프톤 정글 5기/공부(20)
-
Malloc-lab (realloc 개선)
1. Next block이 Free block, 충분한 크기를 가질 때 if (!GET_ALLOC(HDRP(NEXT_BLKP(oldptr))) && (size + DSIZE 메모리 공간 및 시간적 이득을 얻을 수 있음 { PUT(HDRP(oldptr), PACK(next_size, 1)); // 현재 블록의 Header Block에, (현재 블록 사이즈 + 다음 블록 사이즈) 크기와 Allocated 상태 기입 PUT(FTRP(oldptr), PACK(next_size, 1)); // 현재 블록의 Footer Block에, (현재 블록 사이즈 + 다음 블록 사이즈) 크기와 Allocated 상태 기입 lastp = oldptr; ..
2024.04.30 -
Heap Sort
Definition : '부모의 값이 자식의 값보다 항상 크거나 작은' 힙의 특성을 이용하여 정렬하는 알고리즘Properties :1) Heap order property- 각 노드의 값은 자신의 자식노드가 가진 값보다 크거나 같다 (MAX Heap)- 각 노드의 값은 자신의 자식노드가 가진 값보다 작거나 같다 (MIN Heap) 2) Heap shape property- 트리의 모양은 완전이진트리- 리프 노드는 모두 왼쪽에 쏠려 있다 3) 부분 순서 트리- 부모 : 자식 간의 관계는 일정하지만, 형제 노드 사이의 대소 관계는 일정하지 않다완전이진트리: 마지막 레벨을 제외한 모든 레벨에서 노드들이 꽉 채워진 이진트리 한 노드는 최대 두 개의 자식 노드를 가진다. 1차원 배열로 표현이 가능하며, 부..
2024.04.29 -
Malloc Lab
묵시적 가용 리스트 + First_fit 묵시적 가용 리스트 + Next_fit 묵시적 가용 리스트 + Best_fit 전체 코드 (Github) 1. Macro #define WSIZE 4 // word & header/footer size 4 bytes#define DSIZE 8 // double word size 8 bytes#define CHUNKSIZE (1 (y) ? (x) : (y))#define PACK(size, alloc) ((size) | (alloc)) // pack a size and allocated bit into a word #define GET(p) (*(unsigned int *)(p)) // read a word at address p#define PUT(p, va..
2024.04.28 -
분할정복, Divde / Conquer / Combine
정의 : - 주어진 문제를 2개 이상의 유사한 하위 문제로 분할하여, 각 하위 문제에 대한 해결 이후, 해결들을 합쳐 처음 문제를 해결하는 방법 특징 : - 하위 문제로 나뉘어진 각 문제들은, 서로에게 독립적이며 중복되지 않는다. - 주어진 문제와 이를 나눈 하위 문제들은, 해결 방법이 동일하다. 장점 : - 빠르고 간편하다. 분할 이후 해결 방법이 동일하기 때문에, 코드 구현 시 하나의 해결 방법만 제시하면 된다. - 하위 문제가 독립적이기 때문에 병렬적으로 문제를 처리할 수 있으므로, 시간을 효율적으로 처리할 수 있다. 단점 : - 분할과 하위 문제 해결에 재귀적인 함수 호출이 일어나게 되어, 메모리 사용량이 증가한다. - 스택 과다 사용으로 인한 높은 메모리 사용이 발생할 수 있다. Dynamic ..
2024.04.06 -
B-Tree, Balanced Tree
정의 : - 2개 이상의 자식 노드를 가질 수 있고, 노드에 2개 이상의 key를 넣을 수 있는 트리구조 특징 : - 다른 트리 구조와는 다르게, 1개의 노드에 2개 이상의 key를 입력할 수 있다. - M차 B-Tree 구조라면, 최대 M개의 자식 노드를 가진다. - Root node, Leaf node를 제외한 각 노드는 최소 ⌈M/2⌉ 개의 자식 노드를 가진다. (나눈 후 반올림) - 각 노드의 최대 key 개수는 M-1개이다. - 각 노드의 key는 정렬 상태이다. - 모든 Leaf node는 같은 높이에 위치한다. - Leaf node는 linked list로 연결되어 있다. - 부모 노드의 값보다 작은 자식노드는 왼쪽, 큰 자식노드는 오른쪽, 중간 값의 자식노드는 중앙에 위치한다. 장점 : -..
2024.04.06 -
MST, Minimum Spanning Tree
Minimum Spanning Tree는 최소 신장 트리이다. Spanning 이 무슨 뜻인지가 잘 와닿지 않았는데, 그래프에 존재하는 '모든 (Vertex=Node=)정점'을 탐색한 트리이다. Tree, Graph, Forest와 같은 다른 개념들이 선행되어야 이해하기 편하기 때문에 차근차근 내가 이해한 걸 작성해보겠다. [Tree] Graph는 Directed/Undirected, Cyclic/Acyclic 구분 없이 Vertex와 Edge로 구성된 하나의 집합체를 의미한다. Tree는 Graph의 하위 개념으로, Undirected + Acyclic 구조를 가진 그래프를 말한다. 1. Vertex마다 개별적인 Edge로 연결되어 있고 (Acyclic) 2. Edge에 특정 방향으로만 가게 하는 방향..
2024.03.29