STL
-
[C++] 우선순위 큐 STL(priority_queue)C++/STL 2021. 12. 27. 02:52
With Heap Sort Max heap, Min heap를 구현하기 위해서 사용하며, 계속해서 minimum 값을 구해야하는 다익스트라 알고리즘 같은 경우에서 priority_queue를 이용해 min heap을 사용하면 좀 더 짧은 시간에 해결할 수 있다. Perfect Binary Tree(포화 이진 트리) -> 말단 노드를 제외한 모든 노드의 차수가 2로 트리의 레벨마다 비어있는 공간이 존재하지 않음. Complete Binary Tree(완전 이진 트리) -> leaf node의 오른쪽 노드는 비어 있을 수 있으며 배열에 저장하는 것이 가장 효율적. Heap은 Complete Binary Tree를 만족. Max Heap : 부모 노드는 항상 자식 노드에 들어있는 값 보다 크다. Min Hea..
-
너비 우선 탐색(BFS)알고리즘/탐색 2021. 12. 25. 00:47
너비 우선 탐색(Breadth First Search): 특정 데이터를 탐색할 때 너비를 우선으로 하여 탐색을 수행하는 알고리즘. 최단 경로를 찾아준다는 점에서 최단 길이를 보장해야 할 때 많이 사용함. (ex. 미로찾기) 선입선출의 특성을 가진 큐를 이용하는데 큐는 너비 우선 탐색을 가능하도록 해준다. 시작 노드를 큐에 삽입하면서 방문처리. 큐에서 하나의 노드를 꺼낸다. 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입. 2, 3번 과정을 반복하면 시작 노드에서 거리가 가까운 순서대로 출력이 될 것임. #include #include #include using namespace std; int n = 7; int checked[7]; vector arr[8]; void b..