//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 컴퓨터 시스템 구조, Mode bit, Timer, Device Controller, 입출력(I/O)의 수행, 시스템 콜(System Call), 인터럽트(Interrupt), DMA(Direct Memory Access) Controller 컴퓨터 시스템에서 하드웨어가 어떻게 동작하는지 프로그램들이 하드웨어 위에서 어떻게 돌아가는지 1. 컴퓨터 시스템 구조 컴퓨터 시스템의 구조는 컴퓨터 내부장치인 CPU, 메모리와 컴퓨터 외부 장치인 디스크 , 키보드, 마우스, 모니터, 네트워크 장치 등으로 구성된다. 컴퓨터는 외부장치에서 내부장치로 데이터를 읽어와 각종 연산을 수행한 후, 그 결과를 외부장치로 다시 내보내는 방식으..

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 1. 운영체제란 무엇인가? 컴퓨터 하드웨어 바로 위에 설치되어 사용자 및 다른 모든 소프트웨어와 하드웨어를 연결하는 소프트웨어 계층 좁은 의미의 운영체제 - 커널 운영체제의 핵심 부분으로 컴퓨터를 부팅한 이후 항상 메모리에 상주하는 부분 운영체제처럼 규모가 큰 프로그램이 모두 메모리에 올라간다면 한정된 메모리 공간에 낭비가 심할 것이기 때문 넓은 의미의 운영체제 커널뿐 아니라 각종 주변 시스템 유틸리티를 포함한 개념 메모리에 상주하지 않는 별도의 독립적인 프로그램이지만 운영체제의 범주에는 포함 2. 운영체제의 목적 컴퓨터 시스템의 자원을 효율적으로 관리 - 하드웨어를 위한 역할 프로세서, 기억장치, 입출력 장치(= H..

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 1. 강의 목표 운영체제는 컴퓨터 하드웨어 바로 위에 설치되는 소프트웨어 계층으로서 모든 컴퓨터 시스템의 필수적인 부분이다. 운영체제의 개념과 역할, 운영체제를 구성하는 각 요소 및 그 알고리즘의 핵심적인 부분에 대해 기초부터 학습한다. 2. 강의 내용 운영체제 개요 컴퓨터 시스템의 구조 프로세스 관리 CPU 스케줄링 병행 제어 데드락 메모리 관리 가상 메모리 파일 시스템 입출력 시스템 디스크 관리 3. 운영체제(Operating System, OS)란 무엇인가? 컴퓨터 하드웨어 바로 위에 설치되는 사용자 및 다른 모든 소프트웨어와 하드웨어를 연결하는 소프트웨어 계층 컴퓨터 하드웨어 바로 위에 운영체제가 설치되어 → ..

[C로 배우는 자료구조 및 여러가지 예제 실습 - 권오흠 교수님] 자료구조 강의 목록 http://alg.pknu.ac.kr/t/topic/482 [2017년 가을학기] 자료구조 및 실습 제1장 C언어 리뷰 강의자료 강의 소개 제1장 강의 슬라이드 제1주 (101분반 9/4, 9/7, 102분반 9/5. 9/8) 동영상 강의 01: 포인터, 배열과 포인터, 포인터 연산 동영상 강의 02-1: 동적메모리 할당 동영상 강 alg.pknu.ac.kr 자료구조 강의 후기 - 포인터, 배열, 연결 리스트, 스택, 큐의 개념뿐만 아니라 동작 원리와 코드를 개념을 따라 이해할 수 있게 되었다. - 함께 코딩하면서 개념을 복기하기 때문에 응용이 가능하다. - 가장 기초적이면서 기본적인 단계부터 강의하시기 때문에 초심자..

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 1. 정렬된 두 배열 합치기 1-1. 하나의 배열 복사 후 다른 배열 insert 정렬된 두 배열 a와 b에 저장된 m개와 n개의 데이터를 배열 c에 정렬된 상태로 저장하는 것 void merge_sorted_arrays(int m, int a[], int n, int b[], int c[]){ for(int i=0; iitem; i--) data[i+1] = data[i]; data[i+1] = item; } 첫 번째 for문에서 m 시간 소요 두 번째 for문에서 (m+1) + (m+2) + … + (m + n-1) 시간 소요 = m + nm + n(n-1)/2 = O(nm) 시간 복잡도(최악의 경우) 1-2. t..

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 1. Stack - push and pop 1-1. 배열로 구현한 경우 void push(Stack s, Item i){ if(is_full(s)) //스택에 저장된 데이터 개수를 n이라고 하면 reallocate 함수의 시간 복잡도는 O(n) reallocate(s); //reallocate를 제외한 나머지 부분의 시간 복잡도는 O(1) s->top ++; s->contents[s->top] = i; } reallocate를 제외한 나머지 연산은 스택 안의 데이터의 개수와 무관하기 때문에 → O(1)의 시간 복잡도 일반적으로 함수의 시간 복잡도에서 reallocate는 제외 ~ 애초에 스택의 크기를 크게 잡으면 되기..

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 1. 검색 검색: 원하는 데이터가 있는지 없는지를 찾고, 있으면 어디 있는지를 찾는 것 1차원 list로 한정할 때 순차 검색(sequential Search) 는 순차적으로 하나 하나 비교하며 검색하는 것으로 O(n)의 시간 복잡도를 가진다. 배열과 연결리스트 모두에서 사용할 수 있다. 이진 검색(Binary Search) 2. 이진 검색 배열만 사용할 수 있다. 2. 이진 검색(Binary Search) 배열에 데이터들이 내림/오름차순으로 정렬되어 있어야 한다. first, last, middle=(first+last/2)로 중간값과 target의 값을 비교하여 검색 범위를 좁혀 나간다. 중앙값 < target →..

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 1. 알고리즘의 분석 구조화, 모듈화가 얼마나 잘 되었는지에 따라 프로그램의 재사용성과 리팩토링이 달라질 수 있다. 호환성 역시 마찬가지다. 하지만 이러한 기준은 정량화 되어 있지 않기 때문에 이 장에서는 정량화된 기준으로 분석을 한다. 알고리즘의 자원(resource) 사용량을 분석 실행 시간: 똑같은 시간 동안 얼마나 많은 일을 하는지 메모리: 얼마나 많은 메모리를 사용해서 일을 하는지, 과거에는 중요했지만 기술의 발전으로 중요도가 낮아짐 저장장치, 통신 등 2. 시간 복잡도(time complexity) 실행 시간은 실행환경(하드웨어, 운영체제, 언어, 컴파일러 등)에 따라 달라진다. 범용으로 실행 시간을 측정하..

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 1. 스택과 큐의 비교 2. 연결 리스트로 구현한 자료구조 2-1. 스택 연결 리스트의 맨 앞이 노드를 삽입/삭제하기에 편하다→ 맨 앞을 스택의 top으로 한다. typedef int Item; typedef struct stack_type *Stack; struct node{ Item data; struct node *next; } struct stack_type{ struct node *top; } //스택의 생성 Stack create(){ Stack s = malloc(sizeof(struct stack_type)); s->top = NULL; return s; } //삽입 void push(Stack s, I..

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 1. 미로 찾기 DFS(Depth First Search: 깊이 우선 탐색) - recursion, stack 더 이상 갈 곳이 없을 때까지 갔다가 다시 되돌아 나와서 진행 BFS(Breath First Search: 너비 우선 탐색) - queue 출발점에서 한 칸 떨어진 지점을 탐색 출발점에서 두 칸 떨어진 지점을 탐색 … 출발점에서 n 칸 떨어진 지점을 탐색 ~ 동심원 형태로 1-1. 너비 우선 탐색으로 미로 찾기 (1) 하나의 큐를 만든다. (2) 위치(0, 0)는 이미 방문한 위치임을 표시하고, 큐에 위치 (0,0)을 넣는다. (3) 큐가 빌 때까지 반복 (4) 큐에서 하나의 위치 p를 꺼낸다. (5) p에서..

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 1. 환형(circular) 배열 배열은 개수가 정해져 있기 때문에 인덱스가 배열의 범위를 벗어나게 되면 어떻게 되는지 배열로 구현한 큐는 front부터 rear까지 꽉 차 있어야 한다. 배열의 범위를 벗어난다고 해서 reallocate를 할 수 없는 이유 → ②처럼 빈 공간이 남아 있기 때문 ⇒ 환형 배열을 이용해서 큐를 구현할 수 있다. 2. 환형 배열을 이용한 큐 구현 queueADT_array.c // queueADT_array.c #include #include #include "queueuADT.h" #define INIT_CAPACITY 100 struct queue_type{ Item *contents;..

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 1. 큐(Queue) 큐는 일종의 리스트 일반 리스트: 아무 곳에서나 삽입/삭제 가능 스택: 삽입과 삭제가 한쪽 끝에서만 이루어짐 큐: 삽입은 한 쪽 끝에서, 삭제는 반대쪽 끝에서 일어남 삽입이 일어나는 쪽을rear, 삭제가 일어나는 쪽을 front라고 부름 FIFO(First-In, First-Out): 가장 먼저 들어간 애가 가장 먼저 나옴 2. 큐가 지원하는 연산 큐는 스택처럼 연산을 하나의 통일된 이름으로 부르지 않고, 다양한 이름으로 부른다. enqueue: 큐의 rear에 새로운 원소를 삽입하는 연산 insert, offer, push dequeue: 큐의 front에 있는 원소를 큐로부터 삭제하고 반환하는..