lin-ing-link

우선순위 큐(priority_queue) : 큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조이다. 우선순위 큐(Priority Queue)는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다. priority_queue 컨테이너 #include templete class priority_queue 🌀 설명 C++ STL에 포함되어 있는 맵를 표현하는 컨테이너. 🌀 인자 T: 자료형 Container: 구현체 Compare: 비교 연산자 🌀 선언 및 초기화 예시 // std::priority_queue mypq; //가장 작은 값이 우선순위가 되는 큐 std::priority_queue mypq; 🌀 ..

그래프 (Graph) 👉 비선형적 자료구조 👉 정점(vertex)과 정점을 연결하는 간선(edge)을 포함 👉 연결에 일정한 패턴을 이루고 있지 않음 👉 그래프는 비어있을 수 있음 👉 그래프는 순환(Cycle) 혹은 비순환(Acycle) ❗️순환(Cycle) : 경로 중에서 경로의 시작 정점과 마지막 정점이 같은 경로 무방향 그래프 (Undirected Graph) : 두 정점를 연결하는 간선의 방향이 없는 그래프 방향 그래프 (Directed Graph) : 두 정점 연결하는 간선의 방향이 있는 그래프 완전 그래프 (Complete Graph) : 모든 정점들 사이에 1:1로 직접 연결된 간선을 갖는 그래프 👉 정점이 n개인 무방향 그래프인 경우, 최대 간선 수 = n(n - 1)/2 부분 그래프 (S..

A priority queue is an abstract datatype. It is a shorthand way of describing a particular interface and behavior, and says nothing about the underlying implementation. A heap is a data structure. It is a name for a particular way of storing data that makes certain operations very efficient. It just so happens that a heap is a very good data structure to implement a priority queue, because the o..

맵 (map) : 맵은 특정 순서에 따라 키 값과 매핑된 값의 조합으로 형성된 요소를 저장하는 연관 컨테이너이다. 👉 key 값 중복 불가능 👉 삽입이 되면서 자동으로 정렬 👉 저장공간의 필요에 따라 동적할당 👉 균형 이진 트리 구조 map 컨테이너 #include template class map; 🌀 설명 C++ STL에 포함되어 있는 맵를 표현하는 컨테이너. 🌀 인자 Key : 키의 자료형 T : 데이터의 자료형 🌀 선언 및 초기화 예시 //int형 키와 value를 갖는 map 선언 std::map m; //m1과 동일한 map 생성 std::map m2(m1); 🌀 멤버함수 //map이 비어있는지 여부를 반환 bool empty() const; //map의 크기를 반환 size_type size..

이진 힙 (Binary Heap) 👉 완전 이진트리를 기본으로 하는 자료구조 👉 각 노드의 값은 해당 노드의 후손 노드의 값보다 크거나 같음 👉 새로운 entry를 추가하기 위해서는, 새로운 entry를 가장 마지막 spot에 위치하고 reheapification 👉 가장 큰 entry를 삭제하기 위해서는, 가장 마지막 노드를 root에 위치하고 reheapfication 👉 배열에 트리의 값들을 넣어줄 때, 0 번째는 건너뛰고 1 번 index 부터 루트노드가 시작 (노드의 고유번호 값과 배열의 index 를 일치시켜 혼동을 줄이기 위함) 최대 힙 (max heap) 구현 🌀 왼쪽 자식 인덱스 : (부모 인덱스) * 2 🌀 오른쪽 자식 인덱스 : (부모 인덱스) * 2 + 1 🌀 부모 인덱스 : (자식..

트리 트리는 노드들의 집합으로 이루어진 자료구조 트리는 하나의 루트 노드를 갖음 루트 노드는 0개 이상의 자식 노드를 갖고 있음 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의됨 트리 구조는 그래프의 일종 트리에서 사용되는 용어 조상 노드 : 선택된 노드에서 루트 노드까지 연결된 모든 노드들 후손 노드 : 선택된 노드의 하위(루트 노드 반대방향)에 있는 모든 노드들 리프 노드 : 자식이 없는 노드 서브 트리 : 트리에서 트리의 형태를 갖춘 일부 노드 집합 차수 : 선택된 노드의 자식 노드의 개수 깊이 : 루트 노드부터 선택된 노드까지 연결된 선의 개수 높이 : 깊이나 최대값과 동일 이진트리 (Binary Tree) : 이진 트리는 트리를 구성하는 모든 노드의 차수가 2이하인..

큐 (Stack) : 가장 처음으로 삽입된 원소가 가장 먼저 제거되는 FIFO(First In, First Out) 형태의 자료구조로, 한 쪽에선느 삽입만 이루어지고 다른 한 쪽에서는 삭제만 이루어지는 선형 구조. queue 컨테이너 #include template class queue; 🌀 설명 C++ STL에 포함되어 있는 큐를 표현하는 컨테이너. 🌀 인자 T : 데이터의 자료형 Container : 데이터를 담는 컨테이너의 유형 🌀 선언 및 초기화 예시 //정수를 담을 수 있는 큐를 선언 std::queue myQueue; //myQueue1과 동일한 큐를 생성 std::queue myQueue2(myQueue1); 🌀 멤버함수 //큐가 비어있는지 여부를 반환 bool empty() const; /..

스택 (Stack) : 가장 마지막으로 삽입된 원소가 가장 먼저 제거되는 LIFO(Last In, First Out) 형태의 자료구조로, 한쪽에서만 자료를 삽입하고 삭제할 수 있는 선형 구조 stack 컨테이너 #include template class stack; 🌀 설명 C++ STL에 포함되어 있는 스택을 표현하는 컨테이너. 🌀 인자 T : 데이터의 자료형 Container : 데이터를 담는 컨테이너의 유형 🌀 선언 및 초기화 예시 //정수를 담을 수 있는 스택 선언 std::stack myStack; //myStack1과 동일한 스택을 생성 std::stack myStack2(myStack1) 🌀 멤버함수 //스택이 비어있는지 여부를 반환 bool empty() const; //스택의 크기를 반환..

list 컨테이너 #include template class list; 🌀 설명 C++ STL에 포함되어 있는 연결리스트(이중 연결 리스트)를 표현하는 컨테이너. 🌀 인자 T : 데이터의 자료형 🌀 선언 및 초기화 예시 //1차원 정수형 연결 리스트 선언 std::list l; //기본 크기가 3인 연결 리스트 선언 std::list l(3); //기본 크기가 3이고, 모든 노드의 데이터를 2로 초기화 std::list l(3,2); //l1와 동일한 연결 리스트 선언 std::list l2(l1); //2차원 정수형 연결 리스트 선언 std::list l; 🌀 멤버함수 (iterators) //리스트의 첫번재 노드를 가리티는 반복자를 반환 iterator begin() noexcept; //리스트의 마..

Linked list : 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조. 데이터를 담고 잇는 노드들이 순서를 유지하며 연결되어 있음. 🌀 연결 리스트의 종류 - 단일 연결 리스트 - 이중 연결 리스트 - 원형 연결 리스트 🌀 장점 리스트의 중간 지점에서도 자료의 추가와 삭제하는 속도가 빠름 🌀 단점 리스트의 특정 위치의 데이터를 검색하는 데에, 배열에 비해서 시간이 더 소요됨 단일 연결 리스트 : 각 노드에 데이터와 한 개의 포인터가 있고, 각 노드의 포인터는 다음 노드를 가리키는 구조 이중 연결 리스트 : 각 노드에 데이터와 두 개의 포인터가 있는 구조 - 한 개의 포인터는 이전 노드를 가리킴 - 다른 한 개의 포인터는 다음 노드를 가리킴 원형 연결 리스..