CS 공부/자료구조11 힙(Heap)이란? 특징 - 완전이진트리의 일종이다. - 여러 값들 중 최댓값 혹은 최솟값을 빠르게 찾아내기 위한 자료구조이다. - 중복된 값을 허용한다. - Max Heap은 가장 큰 값을 빠르게 찾기 위한 것이고, Min Heap은 가장 작은 값을 빠르게 찾기 위한 것이다. ※ 완전 이진 트리란? 여러 종류의 트리(Tree) 정리 (이진 트리, 전 이진 트리, 완전 이진 트리, 포화 이진 트리, 이진 탐 트리의 개념 - 노드로 이루어진 자료구조로 스택이나 큐 같은 선형 구조가 아닌 비선형 자료구조임. - 계층적 관계를 표현하는 자료구조임. 트리의 특성 - 하나의 루트 노드를 갖음. - 루트 노드 hyolls100.tistory.com Map Heap - Max Heap은 부모 노드의 키 값이 자식 노드의 키 값보다 크거.. 2023. 8. 9. 원형큐(Circular Queue)란? 탄생계기 rear이 가르키는 포인터가 배열의 마지막 인덱스를 가르키고 있을 때 앞쪽에서 Dequeue로 발생한 배열의 빈 공간을 활용할 수 없다는 선형 큐의 문제점을 보완하기 위한 자료구조이다. 기본 동작 - 포인터 증가 방식이 (rear+1)%arraysize 형식으로 변환하기 때문에 배열의 첫 인덱스부터 다시 데이터의 삽입이 가능해진다. Enqueue - rear+1이 배열의 끝이고 포화상태가 아니라면 데이터 삽입을 진행한다. - (rear+1)%arraysize == front 라면 배열이 포화상태이다. (포화상태 여부를 판단하기 위해 배열의 1칸은 비워둠) Dequeue - front+1의 위치의 데이터를 배열에서 가지고온다. - 배열이 공백상태가 아니라면 데이터 삭제를 진행한다. - rear==.. 2023. 8. 7. Queue & Stack Queue란? 특징 - Queue의 사전적 의미는 줄, 혹은 줄을 서서 기다리는 것을 의미한다. - 선입선출(FIFO - First In First Out) 의 자료구조이다. → 먼저 넣은 데이터가 먼저 나온다. - 그러므로, 순서대로 처리해야할 때 사용한다. - 데이터를 추가하는 Enqueue / 데이터를 추출하는 Dequeue 연산이 있다. Enqueue - 맨 뒤에 데이터를 추가하면 되기 때문에 O(1)이다. (rear포인터 이용) Dequeue - 맨 앞의 데이터를 삭제하면 되기 때문에 O(1)이다. (front포인터 이용) 큐의 가장 첫번째 데이터를 front / 가장 마지막 데이터를 rear로 가리킨다. 접근방법은 front/rear로만 가능하다. - 활용 예시로는 하나의 자원을 공유하는 프린.. 2023. 6. 24. Dynamic Array란? 배경 ※ Static Array의 한계점을 보안하기 위해.. Array의 경우 size가 고정되었기 때문에 선언시에 설정한 size보다 많은 데이터를 저장할 수 없다. (Static Array의 한계점) 이를 보안하기 위해 저장공간이 가득 차게되면 resize하여 유동적으로 array의 size를 조절할 수 있는 자료구조가 나왔다. 이를 Dynamic Array라 한다. Resize란? 데이터를 계속 추가하다가 기존에 할당된 메모리를 초과하였다. size를 늘린 배열을 선언한다. 그곳으로 모든 데이터를 옮긴다. 늘어난 크기의 size를 가진 배열이 된다. 이로써 새로운 데이터를 저장할 수 있게 된다. -> 데이터를 추가하다가 한계가 도달하는 시점에 더 큰 배열을 선언하여 모든 데이터를 그곳으로 옮긴다. .. 2023. 6. 24. Array vs Linked List Array란? 특징 연관된 데이터를 메모리상에서 연속적이며 순차적으로 미리 할당된 크기만큼 저장하는 자료구조이다. 고정된 저장 공간 (fixed-size) 순차적인 데이터 저장 (order) 장점 - 접근(lookup)과 마지막 원소 추가/삭제가 O(1)로 빠르다. 단점 - 선언시에 크기를 미리 할당해야해서 메모리 낭비나 추가적인 오버헤드가 발생할 수 있다. ※ 미리 예상한 크기보다 더 많은 개수의 데이터를 저장하기 위한 해결방법은? => Dynamic Array 이용 기존의 size 보다 더 큰 array를 선언하여 데이터를 옮겨 할당한다. 모든 데이터를 옮겼다면 기존 array는 메모리에서 삭제한다. 이런식으로 동적으로 배열의 크기를 조절하는 자료구조를 Dynamic Array라고 한다. => Lin.. 2023. 6. 24. 이전 1 2 다음
