-
(C언어) 이진탐색트리(BST, Binary Search Tree) 구현
이진 트리 이진 트리에는 완전 이진 트리, 포화 이진 트리 등 다양한 종류의 트리가 있다. 하지만 이진 트리의 기본적인 속성으로는 왼쪽 자식 노드의 값이 부모 노드보다 더 작은 값을 가지고, 오른쪽 자식 노드의 값이 부모 노드보다 더 큰 값을 가지는 트리 를 말한다. 탐색 트리의 루트 노드 부터 순회하며 탐색...
-
(Java) 허프만 코드(Huffman Coding) 개념 및 구현
허프만 코드(Huffman Coding) 란? 주어진 문자열을 트리를 이용해 2진수로 압축하는 알고리즘 중 하나이다. 최소 힙을 이용한다. 절차 허프만 트리 제작 빈도 수와 문자 하나 저장할 수 있는 Node 클래스를 정의한다. 문자의 출현 빈도수를 센 후, 해당 문자와 출현 빈도 수를 Node로 만들어 최소 힙에 저장한다. 최소 힙에서 Node 두 개를...
-
(C++) 합병 정렬(Merge Sort) 구현
#include <iostream> using namespace std; int arr[] = {3,1,4,2,5,6,9,7,8}; int len = sizeof(arr)/sizeof(int); int *b = new int[len]; //합병을 위한 임시 배열 void Merge(int low, int mid, int high) { int h = low, j = mid+1; int i = low; // 하나씩 비교하며 작은 것 순서대로 b배열에 넣어줍니다. while(...
-
스케줄링 - FIFO, SJF 개념
스케줄링에 대한 전반적인 개론을 보고 싶다면 이 링크를 먼저 보고 오는 것을 추천합니다. FIFO(First In First Out) FCFS(First Come First Serve)라고도 불린다. 말 그대로 먼저 들어온 프로세스를 먼저 스케줄 하겠다는 뜻입니다. 비선점형(Non-preemptive) 스케줄링입니다. 예를 들어, 아래 표와 같이 동시에 A, B, C 프로세스가 순서대로 도착했다고 가정해봅시다.(즉, Ready Queue에 A, B,...
-
운영체제(Operating System) 핵심 개념 정리 (4) - Scheduling(Overview)
Scheduling 이란(Process Scheduling) 여러 프로세스가 있고, 이 프로세스들이 자원(CPU 등)을 동시에 요구하는데 자원이 제한되어있다. 그러면 제한된 자원들을 어떻게(순서를 할당하는 등) 나눠줄 것인지에 대한 정책 CPU Scheduling CPU 하나는 동시에 여러개의 프로세스를 처리할 수 없기 때문에, 한 순간에 어떤 프로세스가 CPU를 사용할 수 있게 하는지 결정하는 정책 Workload(부하) 행해져야 할 일의...