자료구조

[Basic C++] #69_priority_queue C++의 STL에서 제공하는 priority_queue컨테이너에 대해 알아보겠습니다. Overview 개념 선언 멤버 함수 예제 #0. 개념 1. 우선순위 큐? [자료구조]#7_우선순위 큐 [자료구조]#7_우선순위 큐 우선순위 큐 자료구조에 대해 알아보겠습니다. Overview 개념 구현 참고 #0. 개념 1. 우선순위 큐 정의 : 우선순위 큐(Priority Queue)는 원소들이 우선순위에 따라 정렬된 연결 webddevys.tistory.com 우선순위 큐는 각 원소에 우선순위를 할당하여, 가장 높은 우선순위를 갖는 원소가 다른 원소보다 먼저 처리되는 자료구조입니다. 우선순위 큐는 가장 높은 우선순위를 갖는 원소가 맨 앞에 위치하며, 우선순위 ..

#0. 개념 1. 그래프?[정의] : 그래프는 노드와 간선들의 집합으로 이루어진 비 선형 자료구조입니다. 그래프의 노드들은 간선을 통해 연결되어 일종의 네트워크를 형성합니다. 그래프는 노드와 간선의 개수, 간선의 방향 유무 등에 따라서 다양한 형태로 나타납니다. 예를 들면, 간선의 방향성 유무에 따라서 비 방향성 그래프와 방향성 그래프가 존재합니다. 더불어, 간선의 연결 강도에 따라서 가중치 그래프/네트워크가 있고, 노드와 간선의 연결 유무에 따라서 부분 그래프와 완전 그래프가 존재합니다.[특징] : (1) 계층 구조의 부재 : 그래프는 계층 구조를 갖지 않습니다. (2) 간선의 방향성 : 그래프의 간선은 비 방향성 혹은 방향성을 갖습니다. (3) 간선의 가중치 : 그래프의 간선은 가중치를 가질 수 있습..

[자료구조]#4_레드-블랙 트리 레드-블랙 트리에 대해 알아보겠습니다. Overview 개념 정렬 방법 #0. 개념 1. 레드-블랙 트리? [정의] : 레드-블랙 트리는 균형 이진 트리의 한 종류로, 노드에 빨간색/검정색을 부여하는 방식으로 트리의 높이 균형을 유지합니다. 레드-블랙 트리의 자가 균형성은 편향 이진 트리의 최악의 경우 O(n)의 시간 복잡도 대신, 항상 O(log n)의 탐색 시간을 보장합니다. [특징] : 레드-블랙 트리는 몇 가지 조건으로 노드에 색을 부여하고, Restructuring 혹은 Recolorizing을 통해 정렬 작업을 수행합니다. [레드-블랙 트리 vs AVL트리] : 레드-블랙 트리는 AVL트리와 같은 균형 이진 트리이지만, 균형 조건이 비교적 더 허용적이므로, 일반..

[자료구조]#2_이중 연결 리스트(Double Linked List) 선형 자료 구조 중 "이중 연결 리스트"에 대해 알아보겠습니다. Overview 이중 연결 리스트 삽입, 제거 알고리즘 이중 연결 리스트 1. 개념 typedef struct Node[ Data data; Node* prevLink; Node* nextLink; } Node; 연결 리스트의 노드는 "데이터 필드" + "다음 노드를 가리키는 링크(포인터)"로 이루어져 있습니다. 이중 연결 리스트는 다음 노드뿐만 아니라, 이전 노드를 가리키는 링크 또한 가집니다. 보통의 연결 리스트가 갖는 "단방향 탐색"에 대한 단점을 보완하기 위함입니다. 삽입, 제거 알고리즘 1. 삽입 알고리즘 1. 비어있는 연결리스트에 새로운 노드 삽입 #1 head..

[자료구조]#2_원형 연결 리스트(Circular Linked List) 선형 자료 구조 중 "원형 연결 리스트"에 대해 알아보겠습니다. Overview 원형 연결 리스트 삽입, 제거 알고리즘 원형 연결 리스트 1. 원형 연결 리스트 원형 연결 리스트는 연결 리스트의 마지막 노드가 "nullptr" 가리키지 않고, 연결 리스트의 첫 번째 노드를 가리키는 자료구조입니다. 삽입, 삭제 알고리즘 1. 삽입 #include #include using namespace std; typedef struct _Node { string Name; struct _Node* Next; }Node; int main() { Node* Head; Node* Node_1 = new Node(); Node_1->Name = "Fi..

[자료구조]#1_연결 리스트(Linked List) 선형 자료 구조 중 "연결 리스트"에 대해 알아보겠습니다. Overview 연결 리스트? 삽입, 제거 알고리즘 탐색 알고리즘 연결 리스트 1. 개념 연결 리스트는 노드 기반의 선형 자료구조로, 각 노드는 데이터 필드와 다음 노드를 가리키는 포인터로 구성되어 있습니다. 각 항목/노드의 논리적 저장 순서는 물리 저장 순서와 일치하지 않습니다. 2. 특징 각 항목은 "데이터 필드" + "포인터"를 갖는 노드 형식으로, 다음 노드를 가리키는 "포인터"를 갖습니다. 접근 방법은 첫 노드부터 포인터를 타고 순차적으로 접근하며, O(n)의 수행 속도를 가집니다. 삽입, 삭제 방법은 "포인터" 연결을 끊고, 연결하는 방식으로 매우 간단합니다. 크기는 고정되어 있지 않..

[Basic C++] #31-2_STL 컨테이너, vector, list, deque C++ 개발에서 표준 라이브러리(STL)에 대해 알아보겠습니다. "전문가를 위한 C"의 15 항목, "C++ 표준 라이브러리 살펴보기"에 해당하는 내용입니다. Overview vector list deque set map #0. vector 1. 개념 vector는 STL이 제공하는 순차 컨테이너에 대한 템플릿 클래스입니다. vector는 지정된 형식의 요소를 선형 배열에 저장하고, 모든 요소에 대한 빠른 임의의 접근이 가능합니다. vector의 성능은 컨테이너 끝에서 수행하는 삽입 및 제거 작업의 성능은 O(1) 상수 시간으로 비교적 빠릅니다. 하지만, 컨테이너 중간에서 수행하는 삽입 및 삭제 작업의 성능은 O(n) ..