Computer Science
-
[OS] Process / ThreadComputer Science/Operation System 2020. 4. 9. 12:22
[OS] ✔️ 프로세스 ( process ) ◾ 프로세스는 CPU가 수행 중인 프로그램을 말한다. ◾ 운영체제로부터 자원을 할당 받는 자원 소유권의 단위이다. ◾ 운영체제로부터 code, data, stack, heap, PC, register 등의 자원을 할당받는다. ◾ 프로그램은 명령어 리스트를 지닌 실행 파일 클래스이고, 프로세스는 메모리에 적재되어 프로그램 카운터와 자원을 가진 인스턴스이다. 1️⃣ 프로세스의 문맥 ( Context ) ◾️ 프로그램은 실행이 되고 종료된다. 문맥이라는 것은 특정 시점에 프로세스가 어떤 상태인지 나타내기 위해서 사용되는 것이다. ◾️ 즉, 프로세스의 문맥을 통해 특정 시점에서 프로세스가 어디까지 수행을 했는지를 알 수 있다. ◾️ 프로세스의 현재 상태를 나타내는데 ..
-
[OS] Operating System IntroductionComputer Science/Operation System 2020. 4. 9. 12:21
✔️ OS(Operating System - 운영체제) ◾ 컴퓨터 하드웨어 바로 위에 설치되어 사용자 및 다른 모든 소프트웨어와 하드웨어를 연결하는 소프트웨어 계층 ✔️ OS의 목적 ◾ 컴퓨터 시스템의 자원을 효율적으로 관리하는 것 : CPU, 메모리, 입출력 장치, 프로세스, 파일, 메세지 등을 관리 ◾ 컴퓨터 시스템을 편리하게 사용할 수 있는 환경을 제공 : 여러 프로그램을 동시에 사용할 수 있게 해준다. ✔️ 커널 ◾ 운영체제의 핵심 부분으로 메모리에 상주하는 부분 ✔️운영체제의 분류 1️⃣ 일괄처리 (batch processing) ◾ 작업 요청의 일정량을 모아서 한꺼번에 처리하는 시스템 ◾ 작업이 완전 종료될 때까지 기다려야 한다. ◾ ex) 천공 카드 처리 시스템 2️⃣ 시분할 (time sh..
-
GraphComputer Science/Data Structure and Algorithm 2020. 4. 2. 10:25
✔️ 그래프 ◾그래프는 정점과 간선으로 이루어진 자료구조이다. ◾ 연결되어 있는 정점 간의 관계를 표현할 수 있다. ◾ 무방향 그래프 : 연결 관계에 있어서 방향성이 없는 그래프 ◾ 방향 그래프 : 간선에 방향정보가 포함된 그래프 ◾ 완전 그래프 : 각각의 정점에서 다른 모든 정점을 연결한 그래프 ◾ 가중치 그래프 : 간선에 가중치 정보가 있는 그래프 ✔️ 그래프를 구현하는 두 가지 방법 ◾ 인접 행렬(adjacent matrix) 기반 그래프 : 정방 행렬을 활용 ◾ 인접 리스트(adjacent list) 기반 그래프 : 연결 리스트를 활용 ✔️ 그래프의 탐색 1️⃣ 깊이 우선 탐색(Depts First Search, DFS) ◾ 깊이 우선 탐색은 탐색의 각 과정에서 가능한 한 그래프 안으로 '깊이' ..
-
Priority Queue, heap ( 우선순위큐, 힙 )Computer Science/Data Structure and Algorithm 2020. 4. 2. 10:24
✔️ Priority Queue(우선순위 큐) ◾ 우선순위 큐는 큐와 비슷하다. ◾ 큐는 연산의 결과로 "먼저 들어간 데이터가 먼저 나온다." 하지만 우선순위 큐의 연산 결과는 "들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다." ◾ 우선순위 큐는 배열, 연결리스트, 힙을 이용하여 구현할 수 있다. ◾ 배열기반으로 우선순위 큐를 구현하면, 데이터의 우선순위가 높을수록 배열의 앞쪽에 데이터를 위치시키면 된다. ◾ 하지만 삽입&삭제 연산에서의 shift 연산 오버헤드가 발생한다. 또한 적절한 삽입 위치를 찾기 위해 배열에 저장된 모든 데이터와 우선순위 비교를 진행해야할 수도 있다. ◾ 연결리스트 기반으로 우선순위 큐를 구현하면, 배열과 같이 shift 오버헤드는 발생하지 않지만 우선순위에 따른 ..
-
Tree, Binary Search Tree, AVL TreeComputer Science/Data Structure and Algorithm 2020. 4. 2. 10:23
✔️ Tree(트리) ◾ 트리는 계층적 관계를 표현하는 자료구조이다. ◾ 트리는 부모 노드와 자식 노드의 관계로 재귀적으로 구성된다. 부모 노드가 없는 노드를 루트노드라고 정의한다. ◾ 노드(node) : 트리의 구성요소 ◾ 간선(edge) : 노드와 노드를 연결하는 연결선 ◾ 루트 노드(root node) : 트리 구조에서 최상위에 존재하는 노드 ◾ 내부 노드(internal node) : 단말 노드를 제외한 모든 노드 ◾ 단말 노드(leaf node) : 아래로 또 다른 노드가 연결되어 있지 않는 노드 ◾ 노드 간에는 부모, 자식, 형제 관계가 성립된다. ✔️ Binary Tree(이진 트리) ◾ 이진트리는 각 노드가 최대 두 개의 자식 노드를 갖는 트리이다. ◾ 전위 순회(Pre oder trave..
-
Stack, Queue, Deque ( 스택, 큐, 덱 )Computer Science/Data Structure and Algorithm 2020. 4. 2. 10:20
✔️ Stack ( 스택 ) ◾ 먼저 들어간 데이터가 나중에 나오는 자료구조 ◾ LIFO ( Last-In, First-Out ) ◾ 후입선출 ( 後入先出 ) ⏱️ 시간복잡도 ◾ Push : O(1) ◾ Pop : O(1) 💾 소스 코드 더보기 #include #include #define STACK_SIZE 100 int stack[STACK_SIZE]; int top = -1; void push(int item) { if (top >= STACK_SIZE - 1) { printf("Stack is Full.\n"); return; } stack[++top] = item; } int pop() { if (top == -1) { printf("Stack is Empty.\n"); return 0; } r..
-
Array, Linked List ( 배열, 연결리스트 )Computer Science/Data Structure and Algorithm 2020. 4. 2. 10:19
✔️Array ( 배열 ) ◾ 논리적인 순서와 물리적인 순서가 같기 때문에 데이터에 엑세스 하기쉽다. (인덱스로 쉽게 탐색 가능) ◾ 삽입, 삭제 연산 후에 연속적인 물리적 순서를 유지하기 위해 나머지 원소들을 이동 시키는 오버헤드가 발생한다. ⏱️ 시간복잡도 ◾ 탐색 : index를 통해 O(1)에 해당 원소로 접근 가능 ◾ 삽입 : 원소를 삽입하려면 배열내의 원소를을 shift 해줘야한다. O(n) 시간 ◾ 삭제 : 삭제한 원소보다 큰 index를 갖는 배열내의 원소들을 shift 해줘야한다. O(n) 시간 💾 소스 코드 더보기 #include int main() { int arr[10] = { 0,1,2,3,4,5,6,7,8,9 }; for (int i = 0; i < 10; i++) { print..
-
Big-O (시간 복잡도, 공간 복잡도)Computer Science/Data Structure and Algorithm 2020. 4. 2. 10:17
✔️ 개요 ◾ 우리는 잘 동작하는 알고리즘은 물론이거니와 좋은 성능의 알고리즘을 설계 해야한다. 따라서 우리는 자료구조와 알고리즘을 분석하고 평가할 수 있어야 한다. ◾ 알고리즘을 평가하는 요소는 두 가지 요소는 '속도'와 '메모리 사용량'이다. ◾ '속도'에 해당하는 알고리즘의 수행시간 분석결과를 가리켜 '시간 복잡도(time complexity)라고 한다. ◾ '메모리 사용량'에 대한 분석결과를 가리켜 '공간 복잡도(space complexity)'라고 한다. ◾ 일반적으로는 알고리즘을 평가할 때 메모리 사용량보다 실행속도에 초점을 둔다. ◾ 우리는 '속도'를 측정하기 위해 알고리즘의 연산 횟수를 센다. 그리고 처리해야할 데이터의 수 n에 대한 연산횟수의 함수를 구성한다. ◾ Big-O는 '데이터 수..