자료구조10 [C++/자료구조] 우선순위 큐(Priority Queue) 우선순위 큐 ? C++의 표준 라이브러리(Library)에서 제공되는 priority_queue 는 우선순위 큐 자료구조를 구현한 클래스 입니다. 우선순위 큐는 데이터를 삽입과 동시에 자동으로 정렬이되고 정해진 기준에서 가장 높은 우선순위를 가진 요소가 항상 상단에 위치하도록 유지 합니다. priority_queue 를 사용하기 위해서는 헤더 파일의 선언이 필요합니다. 1. 우선순위 큐의 기본 동작 및 특성 1. 정렬 순서는 기본 내림 차순으로 가장 큰 값이 상단에 위치합니다. 2. 요소의 삽입, 삭제가 이루어 질때마다 자동으로 정렬을 실행합니다. 3. 힙(heap) 자료구조를 기반으로 구현되어 효율적으로 작동합니다. *힙(heap) 자료구조 복습하기(아래 접은글) 더보기 힙(heap) 힙은 특정한 규칙.. 2023. 8. 9. [C++/자료구조] 힙(Heap) Heap : 힙 - 특징 1) 완전 이진 트리 형태 2) 부모 노드와 자식 노드 간의 대소관계가 정해진 완전 이진 트리 구조 3) 루트 노드는 항상 최솟값 또는 최대값을 가진다 4) 최소 힙 또는 최대 힙이 있다. - 최소 힙 : 부모 노드의 값이 자식 노드의 값보다 작은 경우 - 최대 힙 : 부모 노드의 값이 자식 노드의 값보다 큰 경우 - 장점 1) 최소값 또는 최대값을 상수시간 O(1)에 찾을 수있다. 2) 정렬, 우선순위 큐 등에서 유용하게 사용 3) 이진 탐색 트리보다 간단하고 빠르게 구현할 수 있다. - 단점 1) 중복된 값의 처리가 어렵다. 2) 삽입, 삭제, 연산에 시간 복잡도가 O(log n)이 소모된다. Heap.h #pragma once void DoHeap(); class Heap .. 2023. 7. 15. [자료구조] 자료구조별 게임의 기능 구현 예시 자료 구조를 공부하며 실제로 게임개발에 어떠한 기능들을 구현할 수 있는지 알아보고자 합니다. 많은 자료구조가 있지만 이번 게임의 기능 구현 예시에는 7가지 자료구조의 예시를 정리 합니다. 1. 연결 리스트[Linked List] 2. 양방향 연결 리스트[Double Linked List] 3. 스택[Stack] 4. 큐[Queue] 5. 이진 트리[Binary Tree] 6. 힙[Heap] 7. 그래프[Graph] 1. 연결 리스트[Linked List] 1.객체 관리 게임에서 수많은 객체를 생성하고 관리해야할때에 효율적인 자료구조 입니다. 예를 들자면 게임 내의 캐릭터, 아이템, 몬스터(적) 등등을 관리할 수 있습니다. Linked List를 사용한다면 객체를 동적으로 추가하거나 제거할 수 있기때문에 .. 2023. 7. 14. [C++/자료구조] 이진트리(Binary Tree) Tree : 트리 - 특징 1) 루트 노드를 제외한 모든 노드는 부모 노드가 있다 2) 하나의 루트 노드를 가진다 3) 노드는 0개 이상의 자식 노드를 가진다 4) 순환 구조를 가지지 않는다 - 장점 1) 계층적인 구조를 표현할 수 있으며, 검색과 삽입, 삭제가 용이하다 - 단점 1) 불균형한 트리는 탐색 시간이 느려진다 Complete Binary Tree : 완전 이진 트리 - 특징 1) 모든 노드가 꽉 찬 이진 트리 2) 마지막 레벨을 제외한 모든 레벨이 꽉 차있어야 한다 3) 마지막 레벨은 왼쪽부터 차레로 채워진다 4) 모든 노드는 왼쪽에서 오른쪽으로 채워져야 한다 - 장점 1) 배열로 구현할 때 간단하게 구현할 수 있다 - i번째 노드의 왼쪽 자식 노드는 2i 번째 노드 - i번째 노드의 오른쪽.. 2023. 7. 8. [C++/자료구조] 큐(Queue) Queue : 큐 - 특징 1) 선입선출(FIFO) 구조를 가지는 자료구조 2) 삽입은 enqueue, 삭제는 dequeue 연산을 사용 - 장점 1) 구현이 간단하다 2) 작업 처리 대기열, 메세지 전달 등에서 유용하다 - 단점 1) 큐의 크기가 고정되어 있을 때, 큐가 가득 차면 더 이상 데이터를 추가할 수 없다 Queue.h #pragma once void DoQueue(); class Queue { public: Queue(); bool Empty(); bool Full(); int GetSize(); void Enqueue(DataType data); void Dequeue(); DataType GetFront(); private: int Front; int Rear; int Size; Data.. 2023. 7. 8. [C++/자료구조] 스택(Linked List) Stack : 스택 - 특징 1) 후입선출(LIFO) 구조를 가지는 자료구조 2) 삽입은 Push, 삭제는 Pop 연산을 사용 - 장점 1) 구현이 간단하다 2) 함수 호출의 역추적, 수식 계산, 문자열 역순 등에서 유용하다 - 단점 1) 중간 원소에 접근하기 어렵다 Stack.h #pragma once void DoStack(); class Stack { public: Stack(); bool IsEmpty(); bool IsFull(); void Push(DataType data); DataType Pop(); DataType Peek(); private: int Top; DataType Data[MAX_SIZE]; }; Stack.cpp #include "../../stdafx.h" #include.. 2023. 7. 8. 이전 1 2 다음
