분류 전체보기540 [MST] Chapter 02. Kruskal 알고리즘 GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/e91776c4a5ed1f8b2a4cb1104ac89349e77c8bcf Kruskal · developeSHG/Data_Structure-Algorithm@e91776c developeSHG committed Aug 17, 2023 github.com 다시 복습하면 그래프는 [현실 세계의 사물이나 추상적인 개념간]의 [연결 관계]를 표현한다 했었다. 전형적인 그래프는 정점들과 정점들을 연결하는 간선으로 이루어진 것이 그래프였고, 예로 소셜 네트워크 관계도, 지하철 노선도를 그래프로 표현할 수 있었다. 위 사진처럼 정점에 대한 간선을 연결해서 모든 길을 뚫어놓은 상태이고, BF.. 2023. 8. 16. [MST] Chapter 01. Disjoint Set (Union-Find) GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/131723902448c69701b98d17c20188b35e06dbc0 Disjoint Set · developeSHG/Data_Structure-Algorithm@1317239 developeSHG committed Aug 14, 2023 github.com Minimum Spanning Tree => 그래프/트리의 활용정도가 된다. 최소 스패닝 트리 (Minimum Spanning Tree)을 알기 전에 알고 가야할 부분이 "상호 배타적 집합 (Disjoint Set)"이다. DSU라고도 한다. A*에서 가장 좋은 후보를 찾을 때, 우선순위 큐를 사용을 하면 효율이 좋은 .. 2023. 8. 14. [Hash Table] Chapter 01. 해시 테이블 GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/906c6c8a2bd0ad5d7ed94800c8fb95ced78cd8e6 해시 테이블 · developeSHG/Data_Structure-Algorithm@906c6c8 developeSHG committed Aug 14, 2023 github.com map은 Red-Black Tree. 균형 이진 트리 구조로 만들어져있어 트리 구조로 관리한다. 데이터가 추가, 삭제가 되면 이진 트리를 유지하지만, 균형을 맞춰줘서 한 쪽으로 무너지는 걸 예방하는 형태로 되어있다. 시간 복잡도는 O(log N)을 따른다. hash_map은 속도 측면에서 map보다 훨씬 빠르다. 메모리를 내주고,.. 2023. 8. 14. [Sorting] Chapter 03. 퀵 정렬 GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/2260b9e13b4c3da9221ca71a6b6d7a1515995208 퀵 정렬 · developeSHG/Data_Structure-Algorithm@2260b9e developeSHG committed Aug 14, 2023 github.com 퀵 정렬은 병합 정렬과 마찬가지로, 데이터를 둘 씩 쪼개서 진행하는 것은 비슷하다. 근데 병합 정렬은 시작부터 반으로 쪼갠 다음, 왼쪽 그룹과 오른쪽 그룹을 따로 정렬해서 정렬된 양 쪽 그룹을 합치는 형태로 조립했었다. 하지만 퀵 정렬은 처음부터 분할하기 보다는 어느정도 특정 알고리즘을 적용시켜 추출한 다음에, 왼쪽 그룹과 오른쪽 그.. 2023. 8. 14. [Sorting] Chapter 02. 힙 정렬과 병합 정렬 GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/2a955748fbaf3cbd0f5cf002a83f51d2bb347387 힙 정렬과 병합 정렬 · developeSHG/Data_Structure-Algorithm@2a95574 developeSHG committed Aug 14, 2023 github.com #include #include #include #include #include using namespace std; #include // 오늘의 주제 : 정렬 // C# 자료구조/알고리즘 // -> A* OpenList (PQ) // -> C# List = C++ vector // PQ O(logN) // Red-Bla.. 2023. 8. 14. [Sorting] Chapter 01. 기본 정렬 (버블, 선택, 삽입) GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/0a525688c3203b9ea67f96a493d765e55d7d8694 기본 정렬 (버블, 선택, 삽입) · developeSHG/Data_Structure-Algorithm@0a52568 developeSHG committed Aug 14, 2023 github.com C++이 아니라 C#이라고 잠시 생각보자. 참고로 이전에, A* 알고리즘에서 OpenList를 만들었는데 그것을 PQ(우선순위 큐)로 만들어 관리하고 있었다. 근데 고민해보면 왜 우선순위 큐를 사용하느냐? 란 생각이 들 수 있다. C#에선 List가 C++에서 vector에 해당하는 자료구조인데, C# Lis.. 2023. 8. 14. [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. 이전 1 ··· 3 4 5 6 7 8 9 ··· 54 다음
