차근차근 기록장

Queue 와 Priority Queue 의 특징에 대해 정리하고자 한다. 그리고 이와 관련된 Heap 구현에 대한 개념까지 같이 서술한다. 1. Queue - 시간 순서상 먼저 집어 넣은 데이터가 먼저 나오는 선입선출 FIFO (First In First Out) 구조로 저장하는 형식 - 시간 복잡도는 enqueue 시 O(1), dequeue 시 역시 O(1) 2. Priority Queue - 들어간 순서에 상관 없이 우선 순위가 높은 데이터가 먼저 나옴 - 시간 복잡도는 push 시 O(logn), pop 시 O(logn) - Heap 자료구조를 바탕으로 한 구현 방식 - Heap 은 완전 이진 트리 구조이며, 조건은 다음의 경우가 있다. - 1) 각 Node 에 저장된 값은 Child Node ..

Array 와 LinkedList 간의 개념 비교를 카테고리 별로 하고자 한다. 1. 메모리 저장 - 1) Array - 연속성을 유지하기 위해 물리적 메모리 상에서 순차적으로 저장 - 2) LinkedList - 물리적인 메모리 상에서는 비연속적으로 저장이 되지만 Linked List 를 구성하는 각각의 Node가 다음 Node의 Address를 가리킴으로써 논리적인 연속성을 가진 자료구조 - Node 라는 구조체로 이루어져 있는데, Node는 데이터 값과 다음 Node의 address를 저장함 - 물리적 메모리 상에서 연속성을 유지하지 않아도 되기 때문에 메모리 사용이 비교적 자유로운 대신, Next Address를 추가적으로 저장해야 하기 때문에 데이터 하나당 차지하는 메모리가 더 커짐 - 데이터가..