[C++] Data Structure & Algorithm/A* & Heap4 [A* & Heap] Chapter 04. A* 길찾기 알고리즘 GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/b09c4e2a981618692e07cbbad085fe32267f16d9 A* 길찾기 알고리즘 · developeSHG/Data_Structure-Algorithm@b09c4e2 developeSHG committed Aug 10, 2023 github.com 그럼 이전까지 학습한걸로 예전에 진행했던 Maze(미로)에서 길찾기 알고리즘을 좀 더 최적화해보자. 다익스트라와 BFS를 생각해보면 시작점의 개념은 있었지만, 뚜렷하게 목적지란 개념은 없었다. 물론 탐색과정에서 목적지를 발견하면 멈추라는 명령을 내리긴 했지만, 그건 어디까지나 중간에 탐색하다 멈추는 개념이었지 처음부터 목.. 2023. 8. 8. [A* & Heap] Chapter 03. 우선순위 큐 구현 GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/f9452fae763d2a5c6f359a528f94a64bcebf502c 우선순위 큐 구현 · developeSHG/Data_Structure-Algorithm@f9452fa developeSHG committed Aug 10, 2023 github.com 우선순위 큐에 push와 pop을 할 때, 시간복잡도는 O(log n)이다. 우선순위 큐는 힙 tree 구조로 이루어져 있기 때문에, 데이터를 삽입하거나 뺐을 때, 비교 연산이 최대 tree의 높이까지 발생하기 때문이다. #include #include #include #include #include using namespa.. 2023. 8. 8. [A* & Heap] Chapter 02. 힙 이론 우선순위 큐는 힙 트리 구조로 이뤄졌다. 힙트리도 이진트리의 일종이다. - 이진 트리의 개념 각 노드가 최대 두 개의 자식 노드를 가지는 트리 - 이진 검색 트리 특징 1) 왼쪽을 타고 가면 현재 값보다 작다 2) 오른쪽을 타고 가면 현재 값보다 크다 - 이진 검색 트리 문제 그냥 무식하게 추가하면, 한쪽으로 기울어져서 균형이 깨진다 트리 재배치를 통해 균형을 유지하는 것이 과제 (AVL, Red-Black) - 힙 트리 특징 1. [부모 노드]가 가진 값은 항상 [자식 노드]가 가진 값보다 크다. 2. 노드 개수를 알면, 트리 구조는 무조건 확정할 수 있다. - 힙 트리 구현 배열을 이용해서 힙 구조를 바로 표현할 수 있다. 1) i번 노드의 왼쪽 자식은 [(2 * i) + 1] 번 2) i번 노드의 .. 2023. 8. 8. [A* & Heap] Chapter 01. 트리 GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/ac4f9cf68e09fad3391232e069649d597289e58c Tree · developeSHG/Data_Structure-Algorithm@ac4f9cf developeSHG committed Aug 8, 2023 github.com 트리의 개념 계층적 구조를 갖는 데이터를 표현하기 위한 자료구조 노드(Node) : 데이터를 표현 간선(Edge) : 노드의 계층 구조를 표현하기 위해 사용 위의 Tree 구조를 코드로 표현해보자. #include #include #include #include #include using namespace std; using NodeR.. 2023. 8. 8. 이전 1 다음
