1의 보수 각 자릿수의 값이 모두 1인 수에서 주어진 2진수를 빼면 1의 보수를 얻을 수 있다. 2진수 1010의 1의 보수 : 1111-1010 = 0101 ​2의 보수 1의 보수에 1을 더한 값과 같다. 0101 + 0001 = 0110 https://st-lab.tistory.com/189

CPU 스케줄링이란? 여러 프로세스가 실행되고 있는 경우 CPU를 효율적으로 사용하기 위해 프로세스를 잘 배정하도록 하는 것 오버헤드는 줄이고, 사용률은 늘리고 기아 현상은 발생하지 않도록 하는 것 Batch System : 가능하면 많은 일을 수행, 처리량이 중요하다. Interactive System : 빠른 응답시간 == 적은 대기 시간 Real-time System : 데드라인 맞추기 선점과 비선점 스케줄링 선점 스케줄링 : OS가 CPU의 사용권을 프로세스에게 뺏을 수 있는 경우 비선점 스케줄링 : 프로세스가 종료되거나 I/O가 발생하는 경우를 제외하고는 실행 보장 CPU 스케줄링의 종류 비선점 스케줄링 : FCFS (Fist Come First Served) FIFO(First In First..

트리란? 그래프의 한 종류이다. 트리는 노드로 이루어진 자료 구조이며 다음과 같은 특성을 가지고 있다. 트리는 하나의 루트 노드를 갖는다. 루트 노드는 0개 이상의 자식 노드를 가지고 있으며 그 자식들도 모두 마찬가지이다. 노드들과 노드들을 연결하는 엣지들로 구성되어 있으며 이 연결된 엣지들은 절대로 사이클이 존재하지 않는다. 사이클이 존재하지 않기 때문에 간선수는 무조건 노드의 수 - 1 을 만족한다. 루트 노드를 제외한 모든 노드들은 단 하나의 부모노드를 가진다. 루트에서 어떤 노드로 가는 경로는 Unique하다. 트리와 관련된 용어 depth : 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 엣지의 수를 말한다. height : 루트노드에서 잎새노드에 이르는 가장 긴 경로의 엣지 수를 의미한다. ..

힙 힙정렬을 이해하기 전에 힙에 대한 이해가 필요하다. 힙을 이해하기 위해선 다음 포스트를 확인해보자. https://ybdeveloper.tistory.com/132 힙 정렬이란? Max Heap, Min Heap을 구성해 정렬하는 방법이다. 내림차순 정렬을 위해서는 Max Heap, 오름차순 정렬을 위해서는 Min Heap을 구성하면 된다. 즉, 데이터들을 Max Heap이나 Min Heap 형태로 유지한 채 루트 노드의 데이터를 뽑아내 정렬을 하는 방식이다. 힙 정렬 구현 (내림차순) 1. n개의 데이터에 대해 반복한다. O(n) 1-1. 배열에 데이터를 삽입하며 Max-Heap 특성을 만족하도록 조정한다. O(lgn) 2. Max-Heap에 데이터가 존재하지 않을 때 까지 데이터를 뽑아낸다. O(..

우선순위 큐란? 우선순위의 개념을 큐에 도입한 자료 구조 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나간다. 우선순위 큐는 배열, 연결리스트, 힙 으로 구현이 가능하다. 이 중에서 힙(heap)으로 구현하는 것이 가장 효율적이다. 힙이란? 완전이진트리 구조 최댓값과 최솟값을 뽑아낼 때 사용하기 좋은 자료구조이다. 힙은 완전히 정렬된 상태를 유지하는 것이 아닌 Level에 따른 정렬만 이루어져 느슨한 정렬상태를 유지한다. (Max Heap인 경우 부모가 자식보다 큰 값을 가지고 있고, Min Heap인 경우 부모가 자식보다 작은 값을 가지고 있어야 함) 힙의 종류 Max Heap 루트 노드에는 항상 가장 큰 값이 위치하고 있으며, 부모 노드가 자식 노드들보다 무조건 값이 커야한다. M..