본문 바로가기
728x90
반응형

전체 글318

[자료구조] 큐 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.
Array & Dynamic Array & Linked List 란? 차이점 Array이란? Array는 연관된 Data를 메모리상에 연속적이며 순차적으로 미리 할당된 크기만큼 저장하는 자료구조이다. Array의 특징 고정된 저장 공간(fixed-size) 순차적인 데이터 저장(order) Array의 장점은 lookup과 append가 빠르다는 것이다. 즉, 조회를 자주 해야되는 작업에서는 Array 자료구조를 많이 쓴다. Array 시간복잡도 Array access O(1) append O(1) 마지막 원소 delete O(1) insertion O(n) deletion O(n) search O(n) 예상한 Array의 size보다 더 많은 수의 data를 저장하게 될 때, 해결 방법은? 기존 size보다 더 큰 Array를 선언하여 데이터를 옮겨 할당한다. 모든 데이터를 옮.. 2023. 5. 22.
728x90
반응형

티스토리툴바