자료구조9 [C++] 스택계산기(중위표기>후위표기 변환) 보호되어 있는 글 입니다. 2023. 11. 2. BehaviorTree_Sample 보호되어 있는 글 입니다. 2023. 9. 6. [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. 이전 1 2 다음
