언어/자료구조

#1. 개념 트라이(Trie)는 검색 트리의 일종으로, 주로 문자열 검색에 사용되는 자료구조입니다. 트라이 검색 트리의 각 노드는 문자열의 특정 문자를 나타내며, 자식 노드에 대한 링크(배열 혹은 맵)를 가지고 있는 트리 자료구조 중 하나입니다. #2. 동작 방식 1. 검색 트라이 검색 트리에서 특정 문자열을 검색할 경우, 해당 문자열의 각 노드를 트라이 검색 트리의 루트 노드를 시작으로 순차적으로 탐색합니다. 만약, 해당 문자열의 각 문자를 나타내는 노드를 모두 성공적으로 찾고, 그 끝에 문자열의 끝을 나타내는 마커가 존재하면, 해당 문자열은 트라이 검색 트리에 존재합니다. 2. 삽입/삭제 트라이 검색 트리에 새로운 문자열을 삽입할 때, 트리의 루트 노드부 시작하여 각 문자에 해당하는 노드를 순차적으로..

[자료구조]#7_우선순위 큐 우선순위 큐 자료구조에 대해 알아보겠습니다. Overview 개념 구현 참고 #0. 개념 1. 우선순위 큐 정의 : 우선순위 큐(Priority Queue)는 원소들이 우선순위에 따라 정렬된 연결 자료구조로, 원소의 삽입 순서와 무관하게 가장 높은 우선순위를 가진 원소가 먼저 나오는 특징을 갖고 있습니다. 우선순위 큐는 원소 간 우선순위를 유지하기 위해 삽입/삭제 수행 시 정렬 작업을 자동적으로 수행합니다. 따라서, 우선순위 큐 자료구조는 내부적으로 항상 정렬된 상태를 유지합니다. 성능 : 우선 순위 큐의 삽입/삭제 작업의 평균/최악 시간 복잡도는 O(log n)입니다. 일반적으로, 우선순위 큐는 "힙(heap)" 자료구조를 통해 구현하며, 삽입/삭제 작업은 최대 힙 혹은 최..

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

[자료구조]#5_트리 트리 자료구조에 대해 알아보겠습니다.  Overview 개념이진트리순회이진 탐색 트리균형 이진트리AVL 트리레드-블랙 트리Map, Set힙 #0. 개념1. 트리? [정의] : 트리는 1:n 관계의 계층 구조를 갖는 비선형 자료구조입니다. 트리는 노드로 구성되어, 각 노드의 연결 관계는 간선으로 표현합니다. 트리 자료구조는 사이클이 존재하지 않아 노드 간 계층 구조를 갖는 것이 특징입니다. 만약, 트리 자료구조의 노드 개수가 N개라면, 간선의 갯수는 N-1개입니다. [특징] : (1) 계층 구조 : 트리의 루트 노드는 부모 노드가 없지만, 그 외 노드들은 부모-자식 관계를 가지며 계층 구조를 형성합니다.  (2) 간선의 방향성 : 트리의 간선은 항상 부모 -> 자식으로 방향성을 갖습니..

[자료 구조] #0_선형 자료구조 선형 자료구조에 대해 알아보겠습니다. Overview 개념 스택 큐 원형 큐 덱 배열 벡터 리스트 이중 연결 리스트 #0. 개념 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)의 수행 속도를 가집니다. 삽입, 삭제 방법은 "포인터" 연결을 끊고, 연결하는 방식으로 매우 간단합니다. 크기는 고정되어 있지 않..