자료구조 알고리즘 (30) 썸네일형 리스트형 힙으로 구현한 우선순위 큐 힙으로 구현한 우선순위 큐 자료구조의 시간 복잡도는 삽입 삭제에서 O(logn) 이다.우선순위에 따라 값이 정렬된다. #include "iostream"#include "vector"#include "queue"#include "algorithm"#include "list"using namespace std;template, class Predicate = less>class PriorityQueue{public: void push(const T& data) { // 우선 힙 구조부터 맞춰준다. _heap.push_back(data); // 도장깨기 시작! int now = static_cast(_heap.size() - 1); // 루트까지 시도하다가 중간에 멈추면 break while (n.. 이진트리 와 힙 이론 이진트리 : 각 노드가 최대 2개의 자식 노드를 가지는 트리한개여도 되고 전부 공노드여도 괜찮다. 이진 트리는 특히 이진 트리 검색에서 많이 사용됨.다만, 이진 검색 트리는 왼쪽 노드는 부모 노드보다 값이 작아야하고 오른쪽 노드는 부모 노드보다 값이 커야한다. 자식 노드 기준만이 아니라 아래 계층의 모든 노드가 해당 좌우 규칙을 지켜야한다. 트리는 구현 자체에 난이도가 있다.아래도 이진 검색 트리가 맞긴하지만….. 검색의 효율이 원하는 정도로 나오지않을것이다. 이때, 트리 재배치로 균형을 맞춰줘야한다. 이 방식이 AVL, 레드블랙트리 이다.이진 검색 트리는 추가 삽입 삭제 난이도가 상당하다. 힙 트리 특징이진 트리 기반이다.부모 노드가 가진 값은 항상 자식 노드가 가진 값보다 크다마지막 레벨을 제외한 .. 트리 계층적 구조를 갖는 데이터를 표현하기 위한 자료구조노드 : 데이터를 표현간선 : 노드의 계층 구조를 표현하기 위해 사용부모, 자식 노드 : 계층 구조의 노드형제 노드 : 같은 부모와의 계층 구조를 이루는 노드루트 노드 : 최상위 노드잎 노드 : 맨 밑에 노드들깊이 : 루트 노드를 기준으로 0부터 아래 계층에 1씩 더해진다높이 : 트리의 계층의 갯수를 의미트리는 재귀적 속성 및 서브트리로 볼 수 있다.트리 내부에 트리가 있다. #include #include #include #include using namespace std;using NodeRef = shared_ptr;struct Node{ Node() {} Node(const string& data) :data(data) {} string data.. BFS 인접 행렬 인접 행렬로 BFS 구현#include #include #include #include using namespace std;struct Vertex{ // int data;};vector vertices;vector> adjacent;vector> adjacent2;vector visited;vector discovered;void CreateGraph(){ vertices.resize(6); discovered.resize(6); adjacent = vector>(6); adjacent2 = vector>(6); // 인접 리스트 사용 그래프 구현 adjacent[0].push_back(1); adjacent[0].push_back(3); adjacent[1].push_back(0); adjacent[.. BFS 인접 리스트 너비 우선 탐색사용 범위가 DFS에 비해 제한적이다.길찾기에서 유용하게 쓰인다.시작점을 지정하고 탐색 시작. 시작점에서 가까운 노드부터 탐색재귀를 사용하지 않는다. (while 문 사용)queue 를 사용하여 발견한 노드를 저장Dfs 는 발견시 바로 해당 노드를 탐색하지만, Bfs 는 발견한 노드를 따로 저장 후 발견한 노드들을 차례대로(선입선출) 탐색한다.시간 복잡도 :인접 행렬 : O(n2)인접 리스트 : O(n+ 간선수) 시작점이 0노드 일 경우에 1,3 번 노드를 먼저 탐색하고 그 후, 2번 4번 노드를 탐색 한 후 5번 노드를 탐색한다.여기서 1,3 or 2,4 번 노드 중 어떤 노드에 먼저 탐색을 진행할지는 큐 자료구조를 이용하여 구현한다. 인접 리스트를 이용한 Bfs 구현#include #.. DFS 깊이 우선 탐색루트 혹은 임의의 노드에서 시작해 다음 branch로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법. 단순 검색 속도는 BFS보다 느리다.자기 자신을 호출하는 순환 알고리즘의 형태(재귀) 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다.(무한루프) 인접 행렬일 경우 시간복잡도 O(n2), 인접 리스트의 시간 복잡도 O(n+간선수) 인접 행렬에서 dfs 는 O(n) 인데 dfsAll 해야 해서 O(n2) 가 맞다. 그래프 전체 구조 파악 및 순환 구조 파악에 용이하다. #include #include #include #include using namespace std;struct Vertex{ // int data;};vector vertices;vector> ad.. 그래프 구현 첫 번째 일반 그래프 구현정점의 구조체에 간선이 같이 들어있는 구조이다.정점과 간선을 따로 구분 하는 것이 관리하기 좋아 정점과 간선을 분리하는 그래프를 만들어 보자. #include #include #include #include using namespace std;void CreateGraph_1(){ struct Vertex { // 간선 (연결된 정점들의 주소로 표현하였음.) vector edges; // int data; }; // 그래프 v를 선언하고 정점 6개를 만든다. vector v; v.resize(6); // 정점끼리 연결 시켜 준다. v[0].edges.push_back(&v[1]); v[0].edges.push_back(&v[3]); v[1].edges.push_back(&v.. 그래프 기초 현실 세계의 사물이나 추상적인 개념 간의 연결 관계를 표현 정점 : 데이터를 표현(사물, 개념 등)간선 : 정점들을 연결하는데 사용순환, 비순환 구조를 이룸. 방향이 있는, 없는 그래프가 각각있음. 루트 노드 개념이 없음. 2개 이사의 경로가 가능. 네트워크 모델 가중치 그래프지하철 역 간의 거리를 가중치로 표현 예 방향 그래프 구현 시 인접 리스트, 인접 행렬로 구현 가능 인접 행렬일 경우, 두 정점을 연결하는 간선을 조회할 때 O(1) 시간 복잡도정점(i) 의 차수를 구할 때는 인접행렬의 i 번째 해의 값을 모두 더하므로 O(n) 의 시간복잡도인접 행렬 일 경우, 메모리 공간이 더 사용되는 단점그래프의 모든 간선의 수를 알아내려면 인접행렬 전체를 순회해야해서 O(n2) 의 시간복잡도 단점 인접 리스트.. 이전 1 2 3 4 다음
