분류 전체보기539 [Search Tree] Chapter 03. 레드-블랙 트리 GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/b5eba29eefefc411fce715e65633360368555e3e 레드-블랙 트리 구현 · developeSHG/Data_Structure-Algorithm@b5eba29 developeSHG committed Aug 11, 2023 github.com 이전 이진 탐색 트리에서 만약 한 쪽으로 데이터가 몰려 tree의 균형이 무너질 경우, 사실상 BST를 사용할 의미가 없다고 학습했다. (균형이 무너지면 그저 List랑 다를바가 없다.) 그래서 트리의 균형을 맞춰주는 알고리즘이 필요한데, 찾아보면 많은 알고리즘들(AVL)이 있지만 레드-블랙 트리도 균형을 맞춰주는 대표적.. 2023. 8. 11. [Search Tree] Chapter 02. 이진 탐색 트리 GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/cff5f751dce52f7b671a3deb49a42d9c50664c94 이진 탐색 트리 · developeSHG/Data_Structure-Algorithm@cff5f75 developeSHG committed Aug 11, 2023 github.com 이전 이진 탐색 게시글에서 학습했듯, 데이터가 고정되어 있지 않고 빈번하게 삭제와 삽입을 한다면 이진 탐색은 배열을 이용하기 때문에 결국 최적화된 방법이 아니다. 그래서 Node 기반으로 데이터가 유동적으로 변화하는 Tree 구조인 이진 탐색 트리가 있다. 다른 부분은 딱히 어렵지 않지만, 꽤 고려해야 할 부분은 Delete .. 2023. 8. 11. [Search Tree] Chapter 01. 이진 탐색 GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/c90552896ea75286f9c389bc80a25660530dfb8e 이진 탐색 · developeSHG/Data_Structure-Algorithm@c905528 developeSHG committed Aug 11, 2023 github.com 이진 탐색(binary search) 상황) 배열에 데이터가 정렬되어 있다 [1][8][15][23][32][44][56][63][81][91] Q) 82라는 숫자가 배열에 있습니까? 과정) 중간값을 기준으로 절반씩 나누어 범위를 좁혀나가면서 해당값을 찾는다. O(Log N) - 정렬된 배열을 이용해서 이진 탐색 가능 (number.. 2023. 8. 11. [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. [Graph] Chapter 05. 다익스트라(Dijkstra) 알고리즘 GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/ed3f5772f67f98efb67841c1795909f85c76211f 다익스트라(Dijkstra) 알고리즘 구현 · developeSHG/Data_Structure-Algorithm@ed3f577 developeSHG committed Aug 8, 2023 github.com 시작점에서 목적지까지 가는 정점의 간선에 비용이 있다고 가정해보면 적용할 수 있는게 다익스트라 알고리즘이다. 내가 먼저 발견한 순서대로 방문을 하는게 BFS라면, 다익스트라는 인접한 정점을 인지한 후, 방문할 수 있도록 등록은 한다. 근데 각 정점으로 갈 때, 비용은 얼마나 드는지 가중치를 같이 포함해.. 2023. 8. 8. [Graph] Chapter 04. BFS를 이용한 길찾기 구현 GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/ce84719bc1e67974dda74fb833ac50e526c8fe19 BFS를 이용한 길찾기 구현 · developeSHG/Data_Structure-Algorithm@ce84719 developeSHG committed Aug 8, 2023 github.com 이전 글에서 구현한 BFS를 토대로 Maze(미로) 글에 길찾기를 적용했던 우수법을 BFS로 교체해보자. 이전에 BFS를 구현할 때, Vertex라는 점을 만든 다음 인접리스트 혹은 인접행렬을 토대로 관리했었다. 대부분의 경우에는 실제 정점정보와 인접정보를 구분해서 만드는 것이 조금 더 활용하기 편하다고 했다. 하지.. 2023. 8. 8. [Graph] Chapter 03. BFS (너비 우선 탐색) GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/b415c0586aecf03641d3eb30fb58d34f1ccdab96 BFS (너비 우선 탐색) 구현 · developeSHG/Data_Structure-Algorithm@b415c05 developeSHG committed Aug 8, 2023 github.com 길찾기를 할 때, 한 경로로 깊이 탐색하는 DFS 보다 가까운 것을 먼저 탐색하는 BFS를 더 우선 사용. #include #include #include #include #include using namespace std; // [ ][ ][ ][ ][ ][ ][ ][ ] // DFS (Depth First S.. 2023. 8. 8. 이전 1 ··· 5 6 7 8 9 10 11 ··· 54 다음
