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

페이지 교체 알고리즘이란? 메모리에 필요한 페이지가 부재할 경우, 새로운 페이지를 할당해야 하는데 이때 현재 메모리에 존재하는 페이지 중 어떤 페이지를 교체할지 결정하는 알고리즘이다. 가상 메모리는 요구 페이지 기법을 통해 필요한 페이지만 메모리에 적재하고 사용하지 않는 부분은 그대로 둔다. 만약 메모리가 가득 차면, 추가로 페이지를 가져올 때 사용하지 않는 페이지를 꺼내고, 필요한 페이지를 그 페이지가 있던 공간에 넣어야 한다. 이때 기왕이면 수정이 되지 않는 페이지를 선택해야 좋다. 만약 수정이 된 페이지를 꺼내게 되면 하드디스크에 기록을 해야 하므로 오버헤드가 크다. 페이지 교체 알고리즘 종류 FIFO 알고리즘 First-in-First-out으로 메모리에 먼저 올라온 페이지를 먼저 내보내는 알고리..

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(..