본문 바로가기
728x90
반응형

분류 전체보기319

Hash table & BST(Binary Search Tree) 란? BST (Binary Search Tree) 란? 이진탐색트리(Binary Search Tree; BST)는 정렬된 tree이다. 어느 node를 선택하든 해당 node의 left subtree에는 그 node의 값보다 작은 값들을 지닌 node들로만 이루어져 있고, node의 right subtree에는 그 node의 값보다 큰 값들을 지닌 node들로만 이루어져 있는 binary tree이다. 검색과 저장, 삭제의 시간복잡도는 모두 O(logn)이고, worst case는 한쪽으로 치우친 tree가 됐을 때 O(n)이다. BST는 저장과 동시에 정렬을 하는 자료구조이다. 따라서 새로운 데이터를 저장할 때 일정한 규칙에 따라 저장을 하게된다. 작동 원리를 그림으로 설명할 수 있으면 좋다. 이진탐색트리가.. 2023. 5. 25.
[자료구조] 큐 Queue & 스택 Stack & 우선순위큐 priority queue & 힙 Heap 이란? Queue 큐 란? queue는 선입선출 FIFO(First In Frist Out)의 자료구조이다 시간복잡도는 enqueue O(1), dequeue O(1) 입니다. 활용 예시 Cache 구현, 프로세스 관리, 너비우선탐색(BFS) 등이 있습니다. FIFO (First In First Out) 이란? queue는 시간 순서상 먼저 집어 넣은 데이터가 먼저 나오는 선입선출 FIFO(First In First Out) 형식으로 데이터를 저장하는 자료구조이다. enqueue & dequeue queue에서 데이터를 추가하는 것을 enqueue라고 한다. queue에서 데이터를 추출하는 것을 dequeue라고 한다. enqueue의 경우 queue의 맨뒤에 데이터를 추가하면 완료되기 때문에 시간복잡도는 O(.. 2023. 5. 25.
Process & Thread 란? (multi process & multi thread & Deadlock 정리) Process 란? 실행파일(program)이 memory에 적재되어 CPU를 할당받아 실행되는 것을 process라고 한다. 운영체제를 관통하는 핵심적인 단어 하나를 뽑는다면 Process이다. 운영체제가 작동하는 다양한 원리들이 바로 Process를 위해 존재하는 것이다. 따라서 process의 정의를 잘 이해한다면 운영체제의 다른 내용들을 이해하기 편하다. process를 memory와 CPU관점으로 생각하기! Process 프로세스(process)란 실행중인 프로그램(program in execution)을 뜻한다. 즉, 실행파일 형태로 존재하던 program이 memory에 적재되어 CPU에 의해 실행(연산)되는것을 process라고 한다. ( + program은 단순히 명령어 리스트를 포함하는.. 2023. 5. 23.
동시성 (Concurrency)과 병렬성 (Parallelism) 동시성 (Concurrency) 하나의 코어에서 여러 스레드가 번갈아가며 실행 동시에 실행되는 것처럼 보임 싱글 코어, 멀티 코어에서 모두 구현 가능 논리적인 개념 동시성 프로그래밍은 동시에 여러 작업을 수행한다. 눈으로 보기에는 동시에 실행되는 것처럼 보이지만, 시분할(Interleaving) 기법을 활용하여 CPU가 작업마다 시간을 분할해서 적절하게 문맥 교환(context switching) 한다. 때문에, 동시에 실행되는 것처럼 보이는 것이다. 동시성은 구현하는 것도 디버그하는 것도 어렵다. 동시성의 핵심 목표는 유휴 시간(idle time)을 최소화하는 것이다. * 유휴 시간이란(idle time)? 컴퓨터가 작동 가능한데도 작업을 하지 않는 시간을 의미한다. Task 1 과 Task 2 를 쪼.. 2023. 5. 22.
728x90
반응형

티스토리툴바