CS

List, Set, Map 각각의 특성

List 순서가 있고 중복을 허용하는 자료구조. 인덱스로 원소 접근, 원소 삽입, 원소 삭제가 가능하다. 크기가 가변적이고, 이에 따라 비어있는 공간이 없다. 원하는 데이터를 찾을 때 최악의 경우 O(n) 시간이 걸릴 수 있다. Set 순서가 없고 중복을 허용하지 않는 자료구조. 인덱스가 존재하지 않아서 반복자를 사용한다. 탐색이 빠르다. 정렬 되어 있을 시 O(log n) Map 순서가 없는 {Key, Value} 쌍으로 이루어진 자료구조. Key는 중복을 허용하지 않지만 Value는 중복이 가능하다. 인덱스가 존재하지 않아서 반복자를 사용한다. 탐색이 빠르다. 정렬 되어 있을 시 O(log n)

[자료구조]3. 큐

Queue ADT, 큐 추상자료형 큐는 FIFO(First In, First Out), 선입선출 구조이다. 먼저 들어온 원소가 먼저 나간다. 원소의 삽입은 큐의 뒤에서 이루어지고, 원소의 삭제는 큐의 앞에서 이루어진다. 큐의 주요 기능은 다음과 같다. enqueue(obj) : 큐의 뒤(rear)에 원소를 삽입한다. dequeue(obj) : 큐의 앞(front)에 있는 원소를 꺼낸다. 큐의 추가적인 기능은 다음과 같다. front/top : 꺼내지 않고 큐의 맨 앞의 원소를 확인한다. size : 큐에 저장된 원소의 수를 return한다. empty : 큐가 비어있는지 확인한다. 예외처리는 QueueEmpty로 큐가 빈 상태인지 확인한다. 큐의 구현으로는 배열 혹은 링크드 리스트를 사용할 수 있다. 큐..

[OS] OS의 시스템 구조

OS가 제공하는 서비스 OS가 유저에게 제공하는 서비스 유저 인터페이스를 제공한다. 프로그램 수행을 제어한다. 하드웨어 자원을 관리한다. (CPU, 메모리, 저장공간, I/O 장치) 파일 시스템을 관리한다. (생성, 삭제, 탐색) 프로세스들 간의 communication이 일어나도록 해준다. (shared memory, message passing) 에러를 탐지한다. OS는 효율성을 위해서 프로세스들에게 적절하게 자원을 할당한다. 하드웨어 사용 통계 자료를 제공한다. (Accounting) 하드웨어 보호 기능이 있다. (커널 모드와 유저 모드) 보안 기능이 있다. (로그인 시, password 입력) 시스템 콜 커널 모드(Privileged Instruction)로 진입하는 방법은 두 가지가 있다. 하드..

[자료구조]2. 스택

STACK ADT, 스택 추상자료형 스택 추상자료형은 필요한 타입에 맞는 정보를 저장한다. 삽입과 삭제가 후입선출 구조로 이루어진다. 스택의 주요 기능은 다음과 같다. push(object) : element를 삽입한다. pop() : 마지막으로 push된 element를 꺼낸다(return하고 삭제한다). 스택의 추가적인 기능은 다음과 같다. top() : 마지막으로 push된 element를 보여준다. size() : 저장된 elements의 수를 알려준다. empty() : 스택이 비어있는지 확인한다. 예외 처리에서는 pop()과 top() 메서드를 사용할 때 Stack Empty 예외처리를 사용한다. Stack을 사용한 프로그램 예시에는 다음이 있다. 웹 브라우저 방문 기록 텍스트 편집기 되돌리기..

[DB]Intro 및 DB의 전반적인 기초개념

DB가 등장하게 된 이유 file system에서의 문제가 많았다. Data의 중복과 불일치 새로운 작업을 하기 위해선 새 프로그램을 만들어야 했다. -> 접근이 어려웠다. Integrity Problem : 제약조건을 걸기가 어려웠다. Atomicity of update : 만일 A, B에 수행되는 일이 있을 때, A와 B 모두 수행되거나 수행되지 않아야 함. file system에서는 이것을 만족하기 어려웠다. 여러 사용자가 동시에 접근할 때 문제 발생. 보안 이슈 -> DataBase System은 위 문제들을 모두 해결해 준다. DB는 추상적인 것을 제공해준다. Physical Level : 레코드가 어떻게 저장되는지 묘사함. Logical Level : 실제 데이터 베이스에서 데이터가 어떻게 저..

[OS]Operating System의 전반적인 개념

OS의 정의 OS는 일반적으로 정의하기 어렵다. 따라서 공통적인 역할로 정의한다. 하드웨어(리소스)를 관리한다. -> I/O 장치 접근, 파일 접근, Accounting(하드웨어 사용 통계), 에러 탐지 응용 프로그램의 수행을 제어한다. -> 스케줄링, 에러 리포팅 OS는 하드웨어 접근을 제한해야 하므로 응용 프로그램과 하드웨어 사이에 위치한다. OS는 세 가지 목표가 있다. 응용 프로그램 쉽게 사용 컴퓨터 시스템 편하게 사용 하드웨어의 효율적 관리 OS는 또한 Kernel이라고도 불린다. (Android OS는 Linux Kernel을 포함하고, Linux OS보다는 Linux Kernel이라고 많이 부른다.) DMA / Interrupt 컴퓨터에서 CPU와 장치들은 메모리를 차지하기 위해 경쟁한다. ..

[자료구조]1. 단일 링크드 리스트, 단일 연결 리스트

자료구조란 쉽게 말해, 데이터를 저장하고 사용하기 위해 만드는 것이다. 세 가지 기본기능으로는 탐색(Search), 삽입(Insert), 삭제(Delete)가 있다. 자료구조는 구현방법과 성능분석이 중요하다. 링크드 리스트의 특징 (배열과 비교) 배열은 주소가 연속적이지만, 링크드 리스트는 주소가 연속적이지 않다. 배열은 크기가 고정이므로 공간이 부족하거나 낭비될 수 있지만, 링크드 리스트는 크기가 가변적이므로 부족, 낭비가 없다. 배열에 비해 접근이 느리고 구현도 어렵다. 단일 링크드 리스트 단일 링크드 리스트는 node가 순차적으로 이루어져 있다. 각 노드는 값을 나타내는 element 부분과 다음 node를 가리키는 주소(포인터)로 구성된다. 맨 앞 노드를 Head라고 가리키고 맨 뒤 노드를 Tai..