C++
-
[정리] - The graph theory and the DFS, BFS methods - 2정리 2021. 10. 2. 20:37
DFS는 Depth-First Search의 약자로 어떤 그래프가 있을 때, 임의의 한 정점[Vertex, Node]에서부터 시작하여 순회를 함에 있어서 한 노드의 끝까지 갔다가 Backtracking을 하는 알고리즘입니다. 그렇다면 BFS라고 불리는 Breadth-First Search는 어떠한 알고리즘일까요? 이는 Queue을 이용하여 문제를 푸는데 많은 도움을 줍니다. 저는 왜 Queue을 써야하는지 왜 그런 식으로 코드를 짜서 문제를 푸는지 이해하는데 많은 어려움을 겪었습니다. 일단 Queue자체는 Insertions(push)과 Deletions(pull or pop)이 상수 시간 내에 동작한다는 특징을 갖고 있습니다. 그렇기 때문에 어떤 연결된 그래프, Spanning Tree을 순회하기 위해..
-
[ Anything ] - Iterator - 2C++ 2021. 9. 8. 14:13
Iterator은 크게 Input, Output, Forward, Random Access, Bidirectional iterator로 갈래가 나누어 집니다. 이전엔 input/output에 대해 공부를 했습니다. 나머지도 살펴보도록 합니다. Forward Iterator 대표적으로 사용하는 Algorithm library의 함수 중 하나입니다. 온통 Forward iterator 타입의 오브젝트들로 가득합니다. 이전에 보았던 iterator들의 hierarchy관계도를 보면 알 수 있지만 Forward iterator는 input/output iterator의 조합과 같습니다. input iterator의 access와 output iterator의 assign을 모두 지원한다는 뜻이기도 합니다. 주목..
-
[ Anything ] - Iterator - 1C++ 2021. 9. 7. 17:13
C++에서 자주 사용하는 Iterator입니다. 이 Iterator는 우리가 사용하거나 만든 알고리즘을 STL[Standard Template Library]와 이어주는 일종의 다리의 역할을 하며 C++STL의 주축을 이루는 요소 중 하나입니다. 이 Iterator는 Container의 특정한 메모리 주소를 가리킬 수 있으며 종류에 따라서 Read/Write을 수행할 수 있습니다. 예를 들어서 다음과 같은 Class을 임의로 만들었다고 가정해봅시다. 물론 불완전하긴 하지만 STL의 Algorithm의 여러 함수가 요구하는 Iterator들이 구현이 되어 있기 때문에 Vertex에 필요한 operator을 구현하기만 하다면 정렬이나 제거, 복사 등 유용한 기능들을 활용할 수 있습니다. 그렇기 때문에 Ite..
-
-
[46] - std::optionalGraphics 2021. 8. 12. 14:09
Visual Studio 같은 IDE에서는 C++11 표준이나 C++17 표준을 쉽게 선택할 수 있지만 G++을 통해서 std::optional을 접근하려면 compile 옵션에서 따로 설정을 해주거나 expeimental에 있는 optional을 include해야 합니다. std::optional의 주된 사용처는 함수의 반환 값입니다. 예를 들면 외부에서 파일을 불러온다고 했을 때 사용할 수 있을 것입니다. 위와 같이 파일을 열고 test.txt 내의 모든 string을 반환하는 함수가 있습니다. 만약 파일이 존재하지 않는다면 std::string의 기본 생성자를 반환하게 될 것입니다. 파일이 존재한다면 string을 iterator를 사용해서 만들게 될 것입니다. 메인 함수 부에 이렇게 간단한 코드를..
-
[45] - Multithreading Execution PolicyGraphics 2021. 8. 11. 23:57
Cppreference를 통해 C++의 다양한 기능들을 살펴보면서 자주 마주쳤던 단어인 Execution policy입니다. 예를 들면 다음과 같은 곳에서 자주 등장했습니다. Template Parameter list를 보면 나옵니다. 사족을 다 떼고 Execution Policy의 핵심만 정리하면 어떤 알고리즘에 대해서 다중코어를 사용하여 병렬처리를 할 수 있도록 만든다는 것입니다. 여태, 이 부분을 무시하고 알고리즘을 작성했기 때문에 Defualt 값으로 모든 알고리즘은 Single Threaded이며 단일 코어에서 동작했습니다. 그러나 Execution Policy를 통해서 다른 알고리즘을 선택한다면 다중 코어로 알고리즘을 처리하게 됩니다. 이 전에 실험적 코드를 작성하며 한 번 사용한 적이 있는 ..
-
[44] - Container Adaptors, Priority QueueGraphics 2021. 8. 11. 16:25
이건 에 있는 건 아닙니다. 각각 필요한 헤더가 다릅니다. 이들은 기본적으로 어떤 컨테이너들을 감싸는 Wrapper에 가깝습니다. 아래가 Container Adaptors의 종류입니다. 이 어댑터들은 다음과 같은 컨테이너들을 감쌀 수 있습니다. Container Adaptors에 대한 설명란에 provide different interface for sequential containers라고 명시되어 있기 때문에 다음과 같은 associative container에는 해당 사항이 없을 것입니다. 이 Container Adaptors는 상당히 엄격하고 제한된 기능만을 제공합니다. 예를 들면 std::stack이 std::vector를 wrap하고 있더라도 결코 std::vector의 random acces..
-
[43] - Heap OperationsGraphics 2021. 8. 11. 15:41
자료구조나 알고리즘에서 등장하는 heap이 맞습니다. Memory의 heap을 가리키는 말이 아닙니다. 당시에 배웠던 heap의 성질에는 다양한 것들이 있는데 그 중에 기억해야 할 것 중 하나는 heap의 최상단에 가장 큰 값이 오는 max heap, 반대의 min heap이 존재한다는 것입니다. heap은 주로 tree의 형태로 개념화/상징화 됩니다. 이것은 Data Structure에서 더 자세히 다루기 때문에 여기서 할 필요는 없을 것 같습니다. Data structure를 공부하면서 배우는게 낫지만 heap이 중요한 이유는 이를 바탕으로 priority queue를 만들 수 있다는 점입니다. 특히 알아두면 좋은 것이 'A-star pathfinding' Algorithm에서도 쓰이며 heap-so..