[C++] Data Structure & Algorithm44 [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. [Graph] Chapter 02. DFS (깊이 우선 탐색) GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/ee1c8ba520c4c868b8bf032b18231b882f72723e DFS (깊이 우선 탐색) 구현 · developeSHG/Data_Structure-Algorithm@ee1c8ba developeSHG committed Aug 8, 2023 github.com #include #include #include #include #include using namespace std; // [ ][ ][ ][ ][ ][ ][ ][ ] // DFS (Depth First Search) 깊이 우선 탐색 // BFS (Breadth First Search) 너비 우선 탐색 struc.. 2023. 8. 8. [Graph] Chapter 01. 그래프 GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/a371f42dd4ae7aea9e445bcca06d4ebff3d9e1de 그래프 구현 · developeSHG/Data_Structure-Algorithm@a371f42 developeSHG committed Aug 8, 2023 github.com 그래프의 개념 [현실 세계의 사물이나 추상적인 개념 간]의 [연결 관계]를 표현 정점(Vertex) : 데이터로르 표현 (사물, 개념 등) 간선(Edge) : 정점들을 연결하는데 사용 위 사진의 그래프를 3가지 방법으로 만들어보자. #include #include #include #include #include using names.. 2023. 8. 8. [Linear Data] Chapter 05. 오른손 법칙 개선 GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/32793def2975e48222abcbbe66d53fed33f5b49d 오른손 법칙 개선 · developeSHG/Data_Structure-Algorithm@32793de developeSHG committed Aug 8, 2023 github.com 이전 카테고리인 Maze(미로)를 만들었을 때, 길찾기 알고리즘으로 오른손 법칙을 이용했다. 하지만 아쉬운 점은 막힌 길을 굳이 갈 필요가 없음에도 불구하고, 우수법 특성상 막힌 길에 들어갔다 다시 나온다는 것이 비효율적이다. 최단 거리까진 아니라도 불필요하게 이동하는 현상을 예방할 수 없을까 생각이 드는데, 이전에 학습한 s.. 2023. 8. 7. [Linear Data] Chapter 04. 큐 GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/c944c3b8377426e722f4c3cf296d00c6b62db56c 큐(Array, List) 구현 · developeSHG/Data_Structure-Algorithm@c944c3b developeSHG committed Aug 7, 2023 github.com Queue는 선입선출 구조다. 큐를 구현할 때, 데이터의 삽입은 뒤에서 추가되고, 삭제는 맨 앞에서 일어난다. 이럴 때, 데이터 복사로 인해 삽입/삭제 속도가 느린 vector보다 단순 node 끼리 연결된 list가 유용하다. 하지만, vector로 구현할 수 있는 방법이 아예 없는 건 아니다. 생각을 바꿔서,.. 2023. 8. 7. [Linear Data] Chapter 03. 스택 GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/a95915725879968c437ae898c1458fe69dca2927 스택 구현 · developeSHG/Data_Structure-Algorithm@a959157 developeSHG committed Aug 7, 2023 github.com stack은 맨 뒤에다가 데이터를 밀어넣고 꺼내오는 방식이기 때문에, vector를 이용해서 만들 수 있겠다 생각이 든다. 즉, stack도 동적 배열로 만드는 방식과 연결 리스트로 만드는 방식 둘 다 공존한다. 중요한 부분은 맨 뒤 데이터의 작업을 지원하면 되기 떄문에 어떤 자료구조든 stack으로 활용할 수 있다. C# 방식 데이.. 2023. 8. 7. [Linear Data] Chapter 02. 연결 리스트 구현 GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/9590b4df8605e6f46bf862345586cc7b1b701779 연결 리스트 구현 · developeSHG/Data_Structure-Algorithm@9590b4d developeSHG committed Aug 7, 2023 github.com 연결 리스트 : - 연속되지 않은 메모리를 사용 장점 : 중간 삽입/삭제 이점 단점 : N번째 데이터를 바로 찾을 수 없음 (임의 접근 Random Access 불가) list는 노드로 이루어져 중간 삽입/삭제가 빠르기 때문에 push_front도 존재하지만, vector의 경우는 push_front가 없고, push_back.. 2023. 8. 7. 이전 1 2 3 4 5 다음
