분류 전체보기 90
[운영체제] 5. Process-Scheduling / MLFQ(Multi-level Feedback Queue)

Reference - Operating Systems: Three Easy Pieces https://pages.cs.wisc.edu/~remzi/OSTEP/ Operating Systems: Three Easy Pieces Blog: Why Textbooks Should Be Free Quick: Free Book Chapters - Hardcover - Softcover (Lulu) - Softcover (Amazon) - Buy PDF - EU (Lulu) - Buy in India - Buy Stuff - Donate - For Teachers - Homework - Projects - News - Acknowledgements - Other Books Welcome pages.cs.wisc.ed..
CS/운영체제 2023.10.03

[운영체제] 1. CPU의 원리

실리콘 원소의 구조, 전자와 양공의 이동 CPU에 필수적인 트랜지스터라는 반도체는 실리콘으로 이루어짐. 실리콘은 최외각 전자가 4개로, 4중 결합으로 순수한 실리콘은 전자가 이동하지 않아 다른 원소를 추가해 전류가 흐르게 만들어줌. 전자가 부족한 원소를 추가하면 전자가 부족한 공간으로 이동하면서 그 역방향인 구멍이 생기는 방향으로 전류가 발생. 양전하를 띈 것처럼 행동하므로 양공이라고 함. 전자가 한개 많은 원소를 추가하면 남는 전자가 자유롭게 이동하면서 전류가 흐름. P형 반도체, N형 반도체 접합 및 전자와 양공의 이동 이 때 전자가 한개 적은 원소를 첨가한 반도체는 p형(positive), 많은 원소를 첨가한 반도체는 n형(negative) 반도체라 함. P와 N을 결합하면 +에서 -로 전기장이 생..
CS/운영체제 2023.09.12

[자료구조] B-tree란? / B-tree의 연산 / B*tree, B+tree / B+tree 구현

B-tree란? B-tree는 Self-balanced Tree 중 가장 유명한 자료구조입니다. Balanced-tree를 의미하며, 이진트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조입니다. 즉, 하나의 노드에 하나의 데이터를 저장하는 다른 Self-Balanced Tree와 달리, 하나의 노드에 여러개의 데이터를 저장하는 방식으로 Tree의 height를 줄여 탐색 시간을 더 획기적으로 줄이도록 고안된 트리입니다. (B-tree와 B+tree, B*tree가 있지만 일반적으로 B tree라 함은 B-tree를 의미합니다.) 이렇게 고안된 트리를 유지하기 위한 몇가지 규칙이 있습니다. 1. 노드 안에 k개의 데이터가 있다면 자식 노드 수는 k+1개여야 한다. 첫..
CS/Data structure 2023.06.01

[자료구조] Red-Black tree란? / Red-Black tree의 원리 및 활용

Red-Black tree란? Red-Black tree(R-B tree)는 AVL tree, Splay tree와 같은 Self-balanced Binary Search Tree입니다. Red-Black tree는 말그대로 모든 노드가 빨간색과 검정색으로 표현됩니다. 이러한 R-B tree는 균형을 유지하기 위해 아래 다섯가지 조건을 만족해야 합니다. 1. 모든 노드는 빨간색 혹은 검은색이어야 합니다. 2. 루트 노드는 검은색이다. 3. 모든 NIL은 검은색이다. (NIL : null leaf, 자료를 갖지 않고 트리의 끝을 나타내는 리프 노드) 4. 빨간색 노드의 자식은 반드시 검은색이다. 5. NIL에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다. Red-Black tree의 원..
CS/Data structure 2023.05.29

[자료구조] Splay tree란? / Splay tree의 원리 및 활용

Splay tree란? Splay tree는 이진검색트리(Binary Search Tree)의 한 종류로, 다른 BST(AVL tree, R-B tree 등)보다 구현이 쉽고, 연산을 amortized O(logn)의 시간복잡도로 수행할 수 있습니다. amortized O notation은 일반적으로 사용되는 big-O notation과 달리, 시간 복잡도를 실행 시간의 상한 점근이 아닌, 최악의 경우에 대한 해당 연산의 평균 시간복잡도를 나타냅니다. 따라서 최악의 경우에서 연산 시간복잡도가 O(logn)임을 보장한다는 의미라고 생각하시면 됩니다. Splay tree는 삽입, 삭제, 검색의 연산을 수행한 뒤, splay를 통해 최근에 접근한 노드를 루트에 위치시켜 트리를 재구성합니다. 즉, 자주 탐색하는..
CS/Data structure 2023.05.25

[자료구조] AVL tree란? / AVL tree의 연산 방법 및 활용

AVL Tree란? AVL 트리란 자가 균형 이진 탐색 트리(Self-Balanced Binary Search Tree)의 한 유형입니다. Adelson-Velsky와 Landis가 1962년에 발명하였으며, 이들의 앞글자를 따서 이름을 붙였습니다. AVL 트리는 각 노드의 서브트리 높이 차이가 최대 1을 유지하도록 스스로 균형을 유지하는 트리인데, 이 서브트리의 높이 차이를 균형 계수(Balance Factor, BF)라 합니다. 그렇기에 삽입과 삭제 연산을 수행할 때마다 트리의 균형 계수를 체크하고, 균형 계수가 1보다 커질 때 회전(Rotation) 연산을 통해 균형을 유지합니다. Binary Search Tree는 불균형할 때 탐색 성능이 O(logn)에서 O(n)으로 떨어지는 문제가 있었는데, ..
CS/Data structure 2023.05.23
1 ··· 3 4 5 6 7 8 9
더보기
loading

티스토리툴바