CS
-
[OS] Critical Section Problem S/W Solution - Peterson's SolutionCS/Operating System 2021. 12. 1. 19:53
앞의 Synchronization과 Critical-Section Problem에서 설명했던 critical section problem의 solution에 대해 알아보자! Critical section의 기본 조건 1. Mutual Exclusion 어떤 프로세스가 Critical section을 실행 중이라면, 다른 프로세스는 Critical section을 실행할 수 없다! 2. Progress 어떠한 프로세스도 critical section을 실행하지 않고, critical section을 실행하려는 프로세스가 있다면, 다음 critical section을 실행하는 프로세스가 무기한 연기되어선 안 된다! 👉 deadlock 방지 3. Bounded Waiting 각 프로세스는 유한한 횟수의 시도 ..
-
[OS] Synchronization과 Critical-Section ProblemCS/Operating System 2021. 12. 1. 18:50
🔍 Background process synchronization이 필요한 이유! ❗️ 다수의 프로세스/스레드가 공유 데이터에 동시(concurency -> single core), 병렬(parallel -> multicore) 접근으로 인한 데이터 불일치(inconsistency)가 발생할 수 있다. Example - Producer-Consumer problem Producer: 데이터 생성 스레드 Consumer: 데이터 소비 스레드 👉 이 두 스레드는 같은 데이터를 생산하고 소비하는 스레드이기 때문에 반드시 동기화되어야 한다!!! 두 thread가 각각 이러한 코드를 가지고 있다고 생각해보자. global variable로 선언되어 있는 counter 변수는 두 thread가 공유하는 변수이다. ..
-
[Data Structure] Minimum Spanning TreeCS/Data Structure 2021. 10. 8. 09:03
이 포스팅은 세미나를 위해 https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure를 참고하여 작성하였습니다. Spanning Tree 그래프 내의 모든 정점을 포함하는 트리 Spanning Tree는 그래프의 최소 연결 부분 그래프이다. n개의 정점을 가지는 그래프의 최소 간선의 수는 n-1개이고, n-1개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 된다. 이것이 Spanning Tree이다. Minimum Spanning Tree Spnning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리 MST 구현 방법 Kruskal Algorithm 각 단계에서 사이클을 이루지 않는 최소 비용 ..
-
[Data Structure] HashCS/Data Structure 2021. 10. 8. 08:39
이 포스팅은 세미나를 위해 https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure를 참고하여 작성하였습니다. Hash Table hash는 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도를 가진다. hash function을 사용하여 저장할 데이터과 연관된 고유한 숫자(hashcode)를 만들어 이를 인덱스로 사용한다. 특정 데이터가 저장되는 인덱스는 그 데이터만의 고유한 위치이기 때문에 삽입, 삭제 연산 시 shift 연산의 추가적인 비용이 없도록 만들어진 구조이다. Hash Function 저장되는 값들의 key 값을 hash function을 통해 작은 범위의 값들로 바꿔준다. ..
-
[Data Structure] Red-Black TreeCS/Data Structure 2021. 10. 8. 08:00
Red-Black Tree Red-Black Tree는 이진 탐색 트리(Binary Search Tree)기반 트리 형식의 자료구조이다. 이진 탐색 트리는 저장, 삭제, 탐색 시 O(logN)의 시간 복잡도를 갖지만, 한 쪽으로 편향될 경우(최악의 경우) 시간 복잡도가 O(N)이 될 수 있다. 👉 이러한 단점을 보완하기 위해 스스로 높이 균형을 유지하는 Red-Black Tree가 고안됨. 특징 탐색, 삽입, 삭제에 대해 Binary Search Tree의 특성을 사용한다. 각 노드는 Red or Black 색상이 할당된다. Rotation과 Recoloring을 통해 균형을 유지한다. 탐색, 삽입, 삭제 시 O(logn)의 시간복잡도를 가진다. 삽입, 삭제 시 Red-Black Tree의 5가지 조건을..
-
[Data Structure] AVL TreeCS/Data Structure 2021. 10. 7. 14:16
AVL Tree 이진 탐색 트리(Binary Search Tree)기반 트리 형식의 자료구조 이진 탐색 트리가 평균 저장, 삭제, 탐색 시간 복잡도가 평균 O(logN)을 갖지만, 한 쪽으로 편향될 경우(최악의 경우) 시간 복잡도가 O(N)이 될 수 있다. 이러한 단점을 보완하기 위해 스스로 높이 균형을 유지하는 AVL 트리가 고안됨. 특징 AVL 트리는 이진 탐색 트리의 속성을 가진다. 왼쪽, 오른쪽 서브 트리의 높이 차이(Banlance Factor)가 최대 1이다. Balance Factor가 1보다 커지면 회전(rotation)을 통해 균형을 잡는다. AVL 트리의 높이(h)는 logN을 유지하기 때문에 삽입, 검색, 삭제의 시간 복잡도는 O(logN)이다. 회전(Rotation) 삽입, 삭제 시..
-
[Data Structure] HeapCS/Data Structure 2021. 10. 7. 13:20
이 포스팅은 세미나를 위해 https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure를 참고하여 작성하였습니다. Heap 완전 이진 트리(Complete Binary Tree) 기반 자료구조로 반정렬 상태(느슨한 정렬 상태)를 유지한다. 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리 형제 또는 사촌 노드 간의 우선순위는 정해진 것이 없음 힙은 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않음) 종류 최대 힙(Max Heap) key(부모 노드) ≥ key(자식 노드) 최소 힙(Min Heap) key(부모 노드) ≤ key(자식 노드) 시간 복잡도 Max(Mi..
-
[Data Structure] Binary Search TreeCS/Data Structure 2021. 10. 7. 12:52
이 포스팅은 세미나를 위해 https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure를 참고하여 작성하였습니다. Tree 비선형, 계층적 재귀적 자료구조 정점의 갯수가 N이면 간선의 수는 N-1 종류 편향 트리(Skew Tree): 한쪽으로 기울어진 트리 이진 트리(Binary Tree): 트리의 차수가 2 이하인 트리, 레벨 N의 노드의 수는 최대 2^(n-1)개이다. 포화 이진 트리(Perfect Binary Tree): 모든 레벨이 꽉찬 이진 트리 완전 이진 트리(Complete Binary Tree): 위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 채워진 이진 트리 정 이진 트리(Full Binary ..