공부 기록장 💻

OS 2장 문제 풀이 연습 문제 1. CPU의 구성에 대해 설명하시오. 산술 연산 장치(Arithmetic Logic Unit) - 산술(덧셈, 뺄셈, 곱셈 나눗셈 등)연산과 논리(AND, OR, XOR 등) 연산 수행 제어 장치(Controller) - 레지스터에 있는 데이터를 가져다가 명령어를 해석하소 실행을 지시 레지스터(Register) - 메모리의 데이터를 임시로 보관하는 장치 2. 폰노이만 구조의 가장 중요한 특징을 설명하시오. 하드웨어는 그대로 둔 채, 작업을 위한 프로그램만 교체하여 메모리에 올리는 형식으로, CPU는 메모리에 내장된 프로그램을 불러와 수행하는 폰 노이만 구조(=내장형 메모리 구조)를 사용한다. 3. 버스의 종류를 나열하시오. 제어 버스 데이터 버스 주소 버스 4. 다음에 ..

컴퓨터의 구조와 성능 향상 CPU와 메모리가 컴퓨터의 동작의 핵심이고, 운영체제를 이해하는데 가장 중요 1. 컴퓨터의 기본 구성 하드웨어의 구성 필수장치: 중앙처리장치(CPU), 메모리(메인메모리) 주변장치: 입출력장치, 저장장치(보조저장장치) CPU: 명령어를 해석하여 실행하는 연산장치 메모리 작업에 필요한 프로그램과 데이터를 저장하는 장소 바이트 단위로 분할되어 있으며 분할 공간마다 주소(address)로 구분 저장장치 메모리(RAM)보다는 느리지만 저렴하고 용량이 큼(SSD, SD카드) 전원의 On/Off와 상관없이 데이터를 영구적으로 저장 메인 보드 CPU와 메모리 등 다양한 부품을 연결하는 커다란 판 전력이 공급되면 버스로 연결된 부품이 작동 그래픽 카드, 사운드카드, 랜 카드 등이 기본적으로 ..

연습 문제 1. 사용자에게 편리한 인터페이스 환경을 제공하고 컴퓨터 시스템 자원을 효율적으로 관리하는 소프트웨어는 무엇인가? 운영체제(OS, Operating System) 2. 가전제품과 같이 CPU의 성능이 낮고 메모리 크기도 작은 시스템에 내장하도록 만든 운영체제를 무엇이라고 하는가? 임베디드 운영체제(임베디드 시스템) 3. 사용자가 원하는 기능을 수행하기 위해 컴퓨터 자원을 사용하는 소프트웨어는 무엇인가? 응용 프로그램 4. 운영체제가 없는 컴퓨터에서는 어떤 문제가 발생하는지 설명하시오. 만들 당시에 구현한 기능 외에 다른 기능을 추가하거나 성능을 향상할 수 꾀할 수 없다. 새로운 기능을 구현하려면 매번 전선 회로를 변경해야 하고 복잡한 기능은 구현하기 어렵다. 5. 기계와 사용자 사이에 명령을 ..

01 운영체제의 개요 운영체제의 필요성 프로그래밍이 가능한(programmable) 기계: 새로운 기능의 추가나 성능의 변경이 가능 자원 관리(resource management) 컴퓨터 자원(키보드, CPU, 메모리, 주변장치-하드디스크, 마우스, 사운드카드, 그래픽카드, 네트워크카드, 터치패드)에 사용자가 직접 접근하는 것을 막음으로써 자원을 보호하고 관리 하드디스크의 특정 위치에 데이터를 저장할 수 없음 운영체제가 다양한 인터페이스를 제공함으로써 컴퓨터 자원을 관리하고 보호 응용 프로그램(워드 프로세서, 웹 브라우저, 채팅, 음악 재생 SW)에게 컴퓨터 자원을 골고루 배분하고 및 회수하고, 응용 프로그램이 활동할 수 있는 환경을 제공 운영체제의 정의 운영체제: 사용자에게 편리한 인터페이스 환경을 제..

#include #include typedef struct { int id;// 기계의 번호 int avail;// 기계가 사용 가능하게 되는 종료 시간 (키값) }element; #define MAX_ELEMENT 20 typedef struct {// 히프 구조체 element heap[MAX_ELEMENT]; int heap_size; }HeapType; // 히프 구조체 동적 할당 HeapType* create() { return (HeapType*)malloc(sizeof(HeapType)); } // 히프의 사이즈 초기화 void init(HeapType* h) { h->heap_size = 0; } // 최소 히프 구현하는 삽입 함수 (작업 할당 후 기계를 다시 삽입) void insert_..

우선순위 큐(priority queue)는 각 요소들이 우선 순위값을 가지고 있으며, 우선 순위가 높은 데이터가 먼저 나가게 되는 구조이다. 우선순위 큐에는 가장 우선 순위가 낮은 요소를 먼저 삭제하는 최소 우선순위 큐, 그리고 반대로 우선 순위가 높은 요소가 먼저 삭제되는 최대 우선순위 큐가 있다. 히프(heap)는 우선순위 큐를 구현하는 가장 효율적인 구조이다. 히프는 완전 이진 트리의 일종으로, 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내는 경우에 매우 유리한 자료 구조이다. 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진 트리로 구현된 것을 최대 히프(max heap),0 반대로 노드의 키 값이 자식 노드의 것보다 항상 작은 히프를 최소 히프(min heap)라..

이진 탐색 트리(Binary Search Tree)는 이진 트리 기반의 탐색을 위한 자료구조이다. 이진 탐색 트리의 정의 모든 원소의 키는 유일한 키를 가진다. 왼쪽 서브 트리 키들은 루트 키보다 작다. 오른쪽 서브 트리의 키들은 루트의 키보다 크다. 왼쪽, 오른쪽 서브 트리 모두 이진 탐색 트리이다. 위의 이진 탐색 트리에서, 15의 값을 가진 노드의 왼쪽 서브트리에 있는 값들(5,7,10)은 루트 노드인 15보다 모두 작고, 오른쪽 서브트리에 있는 값들(16, 18, 19, 20)은 모두 15보다 큰 값들이다. 이진 탐색 트리를 중위 순회 방법으로 순회하면, 5 -> 7 -> 10 -> 15 -> 16 -> 18 -> 19 -> 20 -> 22 -> 36 -> 45 ->60 으로 숫자들의 크기 순이다..

이진 트리 순회는 순환 호출을 사용하지만, 함수를 반복해서 호출해야 한다는 점에서 비효율적이다. 노드의 개수가 많아지고 트리의 높이가 커지게 되는 경우 프로그램 실행 시간의 측면에서 상당히 비효율적이다. 따라서 순회를 스택을 이용한 순환 호출이 아닌, 링크에 저장되어 있는 주소를 이용하여 다음 노드로 이동하는 반복 구조의 스레드 이진 트리를 고려해볼 수 있다. 이진 트리의 노드에는 많은 NULL링크들이 존재한다. 트리의 노드 개수를 n개라고 하면, 총 링크의 개수는 2n개이고, 이들 링크 중 n-1개의 링크들이 루트노드를 제외한 n-1개의 다른 노드를 가리킨다. 따라서, 2n개 중에서 n+1개의 링크는 NULL임을 알 수 있고, 이들 null 링크를 활용하여 순환 호출 없이 트리의 노드들을 순회할 수 있..

전체 노드의 개수 루트 노드 + 왼쪽 서브 트리의 노드들 + 오른쪽 서브 트리의 노드들 // 전체 노드의 개수 (루트 노드 + 왼쪽 서브 트리 + 오른쪽 서브트리) int get_node_count(TreeNode* node) { int count = 0; if (node != NULL) count = 1 + get_node_count(node->left) + get_node_count(node->right); return count; } 단말 노드의 개수 노드의 왼쪽/오른쪽 서브 노드가 없는 경우 count값 증가 // 단말 노드 개수 (왼쪽/오른쪽 자식이 동시에 0인 경우) int get_leaf_count(TreeNode* node) { int count = 0; if (node != NULL) i..

이진 트리는 수식 트리(expression tree)를 처리하는데 사용될 수 있다. 수식 트리는 기본적으로 연산자(+, -, *, / 등)와 피연산자(정수, 실수 등)으로 만들어진다. 피연산자들은 단말노드가 되며 연산자는 비단말 노드가 된다. 스택을 이용한 후위 표기 수식을 떠올려보자. 피연산자이면 스택에 삽입하고, 연산자이면 스택에서 필요한 수만큼의 피연산자를 꺼내 연산을 실행하고, 그 연산 결과를 다시 스택에 넣는 방법이었다. 이번에는 후위 표기 수식이 아닌, '수식 트리'의 구조로 수식이 표현된다. 수식 트리의 루트 노드는 연산자이고, 연산자의 피연산자인 자식 노드들을 계산하여 전체 수식을 계산해보자. 루트 노드보다 자식 노드들을 먼저 방문하는 후위 순회 방법을 사용하여 계산을 진행해보자. /* *..

레벨 순회(level_order)는 각 노드를 레벨 순으로 검사하는 순회 방법이다. 레벨 1인 루트 노드부터 시작하여, 아래로 내려갈 수록 증가되는 각 레벨을 좌에서 우로 방문한다. 레벨 순회는 큐 구조를 사용하여 구현한다. 레벨 순회는 큐에 하나란도 노드가 있으면, 계속 반복하는 코드로 이루어져 있다. 먼저 큐에 있는 노드를 꺼내어 방문한 다음, 그 노드의 자식 노드를 큐에 삽입하는 것으로 한번의 반복을 끝낸다. #include #include typedef struct TreeNode { int data; struct TreeNode* left, * right; }TreeNode; #define MAX_QUEUE_SIZE 100 typedef TreeNode* element; typedef struc..

순환을 이용한 이진 트리 중위, 전위, 후위 순회 #include #include // 이진 트리 노드 구조체 typedef struct TreeNode { int data; struct TreeNode* left, * right; }TreeNode; // 15 // 4 20 // 1 16 25 TreeNode n1 = { 1, NULL, NULL }; TreeNode n2 = { 4, &n1, NULL }; TreeNode n3 = { 16, NULL, NULL }; TreeNode n4 = { 25, NULL, NULL }; TreeNode n5 = { 20, &n3, &n4 }; TreeNode n6 = { 15, &n2, &n5 }; TreeNode* root = &n6; // 중위 순회 void..

스택의 개념, 구조와 구현 스택을 이용한 괄호 검사 프로그램 스택 - 후위 표기 수식 계산과 중위에서 후위 표기로의 변환 스택 - 두 자리 이상의 숫자에 대한 후위 표기 수식 연산 프로그램 스택 - 미로 탐색 프로그램 연결리스트로 표현한 스택 구조 큐의 개념과 구조, 구현 / 선형, 원형 큐 원형 큐 응용 - 오름차순으로 큐에 데이터 삽입 덱의 개념과 구조, 구현 단순 연결 리스트 간단한 예제들 단순 연결 리스트 실습 + 역순 연산, 버블 정렬 연결 리스트 - 메타 구조체 (정렬, 역순, 탐색, 최대/최소) 연결 리스트 - 특정 위치에 데이터 삽입/삭제 (선행 노드의 포인터) 원형 연결 리스트의 개념, 구조와 구현 연결 리스트로 표현한 다항식의 연산 (tail,..

#include #include #include typedef char* element; typedef struct DListNode { struct DListNode* llink; struct DListNode* rlink; element data; }DListNode; DListNode* current; // 현재 위치(현재 play되는 곡) void init(DListNode* head) { head->rlink = head; head->llink = head; } void dinsert(DListNode* prev, element data) { DListNode* new_node = (DListNode*)malloc(sizeof(DListNode)); new_node->data = (char*)m..

특정 위치에 새로운 데이터(노드)를 삽입하고, 삭제할 수 있는 연결 리스트 프로그램이다. data.txt 20074241 마바사 50 90 95 20074242 가나다 80 95 85 20074243 라마바 70 60 95 20074244 사아자 50 30 65 add_last() 함수를 이용 #include #include #include #define TRUE 1 #define FALSE 0 typedef struct element { int nId; char* name; int nKor, nEng, nMath, nSum; double dAvg; }element; typedef struct ListNode{ element data; struct ListNode* link; }ListNode; type..

data.txt 30 50 10 40 20 // 원형큐 응용 - 큐의 데이터를 오름차순으로 정렬하고 출력하기 // 숫자가 낮은 순서대로 저장 #include #define MAX_QUEUE_SIZE 100 typedef struct { int nPriority; // 큐의 요소 값 (낮은 순대로 저장하기 위함) }QueueObject; QueueObject queue[MAX_QUEUE_SIZE]; // 원형 큐를 배열리스트로 선언 int front, rear; // initialize void init_queue() { front = rear = 0; } // isEmpty int isEmpty() { return(front == rear); } // isFull int isFull() { return ..

시스템 버스(System Bus) 버스(Bus) - 컴퓨터 시스템의 구성 요소들(CPU, 기억장치, I/O 장치들) 을 상호 연결해주는 중심 통로 버스 대역폭(Bus Bandwidth) - 버스의 속도를 나타내는 척도 - 단위 시간당 전송할 수 있는 데이터 양 - 버스 클록 주기 * 버스폭(BYTE단위) 버스 클록의 주파수가 50MHz(클록주기 20ns), 데이터 버스 폭이 64비트(8바이트)인 경우, 버스 대역 폭은 8 *(50*10^6) = 400[Mbytes/sec] - 버스 클록의 주기에 의해 결정 기능에 따른 버스의 종류 1. 데이터 버스(Data bus) - 시스템 요소들 사이에 데이터(값)를 전송하는데 사용되는 선들의 집합 - 양방향 전송(Bidirectional Transfer) - 버스 ..

컴퓨터구조론(생능출판사) 4장 - 제어 유니트 제어 유니트의 기능 1. 명령어 코드의 해독 2. 명령어 실행에 필요한 제어 신호들 발생 - 마이크로명령어(micro instruction) : 명령어 사이클의 각 주기에서 실행되는 마이크로-연산들에 대응되는 비트들로 이루어진 단어 - 마이크로프로그램(microprogram) : 마이크로명령어들의 집합 - 루틴(routine) : CPU의 특정 기능을 수행하기 위한 마이크로명령어들의 그룹 제어 유니트의 구조 제어 유니트의 내부 구성도 - 명령어 레지스터 -> 명령어 해독기 -> 제어 주소 레지스터(CAR) ( -> SBR) -> 제어 기억 장치 -> 제어 버퍼 레지스터(CBR) ( -> 순서 제어 모듈 -> CAR) -> 해독기 명령어 해독기(instruct..

덱은, 기존의 원형 큐에서 일부 기능이 추가된, 전단과 후단 양쪽 모두에서 삽입과 삭제의 입출력과 반환이 가능한 원형 큐이다. 원형 큐의 구조와 구현 https://dream-and-develop.tistory.com/102 덱(DEQUE : Double-Ended Queue) 덱(Deque) 은 큐의 전단(front)과 후단(rear) 에서 모두 입출력(삽입/삭제)가 가능한 큐이다. 덱의 추상 자료형은 다음과 같다. - create(MAX) : 구조체 DequeType을 구현하여 구조체 변수를 선언하는 것과 동일하다. - init(dq) : 덱을 초기화한다. 덱의 rear, front 멤버 변수를 각각 0으로 설정한다. - is_empty(dq) : 큐가 공백 상태인지 체크한다. 기존의 원형 큐와 동일..

원형 연결 리스트의 구조 - 마지막 노드가 첫번째 노드를 가리키게 하여 리스트의 구조를 원형으로 만든 연결 리스트 => 마지막 노드의 링크필드가 NULL 이 아닌, 첫번째 노드의 주소이다. 장점 - 하나의 노드에서 다른 모든 노드로의 접근이 가능 - 하나의 노드에서 링크를 계속 따라가면 결국 모든 노드를 거쳐 자기 자신으로 되돌아오는 것이 가능 - 노드의 삽입과 삭제가 단순 연결 리스트보다는 용이함 - 특히, 리스트의 끝에 노드를 삽입하는 연산이 단순 연결리스트보다 효율적 -> 헤드 포인터에서 시작하여 모든 노드를 거쳐 마지막에 삽입하는 것이 아니라, 헤드포인터가 마지막 노드를 가리키도록 구성하면 리스트의 처음과 끝에 노드를 삽입할 수 있다. 원형 연결 리스트의 구현 헤드포인터 head는 항상 마지막 노..