CS
-
[자료구조] 레드-블랙 트리(Red-Black Tree)Computer Science/Data Structure 2023. 2. 27. 16:47
Red-Black Tree 자가 균형 이진 탐색 트리(self-balancing binary search tree) 로서, 대표적으로 연관 배열 등을 구현하는 데 쓰이는 자료구조입니다. 트리에 N개의 원소가 있을 때 O(log N)의 시간 복잡도를 삽입, 삭제, 검색을 할 수 있습니다. 레드-블랙 트리는 복잡한 자료구조이지만, 실 사용에서 효율적이고, 최악의 경우에도 일정한 실행 시간을 보장하여 실시간 처리와 같은 실행 시간이 중요한 경우에 유용하게 사용됩니다. 특성 Red-Black Tree는 각각의 노드가 Red, Black 두가지의 색상 속성을 가지고 있는 이진 탐색 트리입니다. 각 구성 원소는 in-order traversal(중위순회) 연산을 수행합니다. - in-order traversal(중..
-
[자료구조] Linked list (연결리스트)Computer Science/Data Structure 2022. 9. 23. 21:11
Linked List 란? node라는 객체로 이루어져 있다. 여러개의 node를 연결함으로써 데이터 표현 가능 시작(주소) - 연결(link) - 끝(null pointer or circular) 코드로 아래와 같이 구현할 수 있다. typedef struct Node{ int data; Node *next; }Node; Linked list 장점 동적으로 메모리 사용가능 메모리 효율적 사용 데이터 재구성 용이 대용량 데이터 처리 적합 Linked list 단점 특정 위치 데이터 검색 느림 메모리를 추가적으로 사용해야 함 Singly Linked list Circularly Linked list : 마지막 노드가 다시 처음 노드를 가리킴.
-
[CS] 운영체제(OS, Operating System)Computer Science/CS 2022. 5. 10. 18:28
1. 운영체제(OS, Operating System) 이란? 컴퓨터 시스템의 자원들을 효율적으로 관리하며, 사용자가 컴퓨터를 편리하고, 효과적으로 사용할 수 있도록 환경을 제공하는 여러 프로그램의 모임이다. 컴퓨터 사용자와 컴퓨터 하드웨어 간의 인터페이스로써 동작하는 시스템 소프트웨어의 일종으로, 다른 응용프로그램이 유용한 작업을 할 수 있도록 환경을 제공한다. 2. 운영체제 기능 운영체제의 기능은 크게 자원관리, 시스템관리로 분류된다. (1) 자원관리 : 메모리 관리(메인 메모리, 보조기억장치), 프로세스 관리, 주변장치 관리, 파일(데이터) 관리 (2) 시스템 관리 : 시스템 보호(사용자 권한 부여), 네트워크(통신), command interpreter 등의 기능을 지원한다. 3. 부팅(Bootin..