반응형 [C++로 배우는 알고리즘과 자료구조] Day 11: 그래프의 기본 개념 그래프 (Graph)그래프는 노드(정점, Vertex)와 간선(Edge)으로 구성된 자료구조로, 여러 노드가 간선으로 연결된 형태를 가집니다. 그래프는 다양한 문제를 모델링하고 해결하는 데 사용됩니다.그래프의 구성 요소:노드 (Vertex): 그래프의 개별 요소입니다.간선 (Edge): 노드 간의 연결을 나타냅니다.그래프의 종류:방향 그래프 (Directed Graph): 간선이 방향을 가지는 그래프입니다.무방향 그래프 (Undirected Graph): 간선이 방향을 가지지 않는 그래프입니다.가중치 그래프 (Weighted Graph): 간선에 가중치가 있는 그래프입니다.비가중치 그래프 (Unweighted Graph): 간선에 가중치가 없는 그래프입니다.그래프의 표현 방법그래프는 다음과 같은 방법으로.. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조] Day 8: 균형 이진 탐색 트리 (AVL 트리) 균형 이진 탐색 트리 (AVL Tree)AVL 트리는 자가 균형 이진 탐색 트리의 일종으로, 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하로 유지되도록 합니다. AVL 트리는 삽입, 삭제 연산 후 트리의 균형을 유지하기 위해 회전을 사용합니다.AVL 트리의 특징:높이 균형: 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하입니다.높이 제한: AVL 트리의 높이는 (O(\log n))로 제한됩니다.시간 복잡도: 검색, 삽입, 삭제 연산의 평균 및 최악의 경우 시간 복잡도는 (O(\log n))입니다.AVL 트리의 주요 연산:삽입 (Insert)삭제 (Delete)검색 (Search)회전 (Rotation): 트리의 균형을 유지하기 위해 사용됩니다. (단순 회전과 .. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조] Day 9: 힙과 우선순위 큐 힙 (Heap)힙은 완전 이진 트리의 형태를 가지며, 각 노드가 특정한 우선순위를 가지는 자료구조입니다. 힙은 주로 최대값이나 최소값을 빠르게 찾기 위해 사용됩니다. 힙에는 최대 힙(Max-Heap)과 최소 힙(Min-Heap)이 있습니다.힙의 종류:최대 힙 (Max-Heap): 부모 노드의 값이 자식 노드의 값보다 크거나 같습니다.최소 힙 (Min-Heap): 부모 노드의 값이 자식 노드의 값보다 작거나 같습니다.우선순위 큐 (Priority Queue)우선순위 큐는 힙을 기반으로 구현되며, 각 요소가 우선순위를 가지는 큐입니다. 우선순위 큐는 삽입과 삭제 연산에서 우선순위에 따라 요소를 정렬합니다. 따라서 가장 높은 우선순위를 가진 요소를 O(log n) 시간 복잡도로 삽입하거나 삭제할 수 있습니다... 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조] Day 7: 이진 탐색 트리 (BST) 이진 탐색 트리 (Binary Search Tree, BST)이진 탐색 트리(BST)는 각 노드가 최대 두 개의 자식 노드를 가지는 이진 트리의 일종으로, 왼쪽 서브트리의 모든 값은 루트의 값보다 작고, 오른쪽 서브트리의 모든 값은 루트의 값보다 큰 속성을 가집니다. 이러한 속성 덕분에 BST는 효율적인 검색, 삽입, 삭제 연산을 지원합니다.BST의 주요 연산:삽입 (Insert): 새로운 값을 트리에 삽입합니다.검색 (Search): 특정 값을 트리에서 검색합니다.삭제 (Delete): 트리에서 특정 값을 삭제합니다.순회 (Traversal): 트리의 노드를 특정 순서로 방문합니다.BST 구현BinarySearchTree.h#ifndef BINARYSEARCHTREE_H#define BINARYSEAR.. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조] Day 5: 해시 테이블 (Hash Table) 해시 테이블 (Hash Table)해시 테이블은 키(Key)와 값(Value) 쌍을 저장하는 자료구조로, 평균적으로 O(1) 시간 복잡도로 데이터를 검색, 삽입, 삭제할 수 있습니다. 해시 테이블은 해시 함수를 사용하여 키를 해시 값으로 변환하고, 이를 인덱스로 사용하여 값을 저장합니다.해시 테이블의 주요 연산:삽입 (Insert): 키와 값을 해시 테이블에 삽입합니다.검색 (Search): 키를 사용하여 해시 테이블에서 값을 검색합니다.삭제 (Delete): 키를 사용하여 해시 테이블에서 값을 삭제합니다.해시 함수 (Hash Function)해시 함수는 임의의 크기를 가진 데이터를 고정된 크기의 해시 값으로 변환하는 함수입니다. 해시 함수는 다음과 같은 특성을 가져야 합니다:결정적 (Determinis.. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조] Day 6: 트리의 기본 개념 트리 (Tree)트리는 계층적 자료구조로, 노드(Node)와 간선(Edge)으로 구성됩니다. 트리는 하나의 루트(Root) 노드를 가지며, 각 노드는 자식 노드를 가질 수 있습니다. 트리는 사이클이 없는 비순환 그래프입니다.트리의 용어:루트 노드 (Root Node): 트리의 최상위 노드입니다.부모 노드 (Parent Node): 특정 노드의 바로 위에 있는 노드입니다.자식 노드 (Child Node): 특정 노드의 바로 아래에 있는 노드입니다.리프 노드 (Leaf Node): 자식 노드가 없는 노드입니다.서브트리 (Subtree): 노드와 그 자손 노드들로 이루어진 트리의 부분 집합입니다.높이 (Height): 루트 노드에서 리프 노드까지의 최대 경로 길이입니다.이진 트리 (Binary Tree)이진 .. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조] Day 3: 연결 리스트 (단일, 이중, 원형) 연결 리스트 (Linked List)연결 리스트는 노드들이 포인터로 연결된 선형 자료구조입니다. 각 노드는 데이터와 다음 노드를 가리키는 포인터를 포함합니다. 연결 리스트는 동적 메모리 할당을 사용하여 크기를 유연하게 조정할 수 있습니다.연결 리스트의 종류:단일 연결 리스트 (Singly Linked List)이중 연결 리스트 (Doubly Linked List)원형 연결 리스트 (Circular Linked List)단일 연결 리스트 (Singly Linked List)단일 연결 리스트는 각 노드가 다음 노드를 가리키는 포인터를 가진 자료구조입니다.단일 연결 리스트 구현노드 구조체 정의#include // 단일 연결 리스트의 노드 구조체struct Node { int data; // 데이터 .. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조] Day 4: 스택과 큐 스택 (Stack)스택은 후입선출(LIFO, Last In First Out) 원칙을 따르는 자료구조입니다. 즉, 가장 나중에 삽입된 요소가 가장 먼저 제거됩니다. 스택은 주로 재귀적 알고리즘, 언어 구문 분석, 백트래킹 등에서 사용됩니다.스택의 주요 연산:push: 스택의 맨 위에 요소를 추가합니다.pop: 스택의 맨 위 요소를 제거합니다.top: 스택의 맨 위 요소를 반환합니다.isEmpty: 스택이 비어 있는지 확인합니다.스택 구현 예제#include #include class Stack {public: void push(int value) { data.push_back(value); // 스택의 맨 위에 요소 추가 } void pop() { if (!dat.. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조] Day 2: 배열과 문자열 배열 (Array)배열은 동일한 타입의 요소들이 연속적으로 저장된 자료구조입니다. 배열은 고정된 크기를 가지며, 인덱스를 사용하여 요소에 접근할 수 있습니다. 배열은 C++에서 가장 기본적인 자료구조 중 하나입니다.배열의 특징:고정된 크기: 배열의 크기는 생성 시 결정되며, 변경할 수 없습니다.빠른 접근 속도: 인덱스를 사용하여 O(1) 시간 복잡도로 요소에 접근할 수 있습니다.연속된 메모리 공간: 배열은 연속된 메모리 공간에 저장됩니다.배열 예제#include int main() { // 배열 선언 및 초기화 int arr[5] = {1, 2, 3, 4, 5}; // 배열의 크기 int size = sizeof(arr) / sizeof(arr[0]); // 배열의 요소 출력 .. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조] Day 1: 알고리즘과 자료구조 소개 알고리즘과 자료구조란?알고리즘 (Algorithm)알고리즘은 주어진 문제를 해결하기 위해 설계된 일련의 절차나 방법입니다. 알고리즘은 컴퓨터 과학에서 매우 중요한 개념으로, 효율적인 문제 해결과 성능 최적화를 위해 필수적입니다.알고리즘의 특징:명확성 (Clarity): 각 단계는 명확하고 이해하기 쉬워야 합니다.유한성 (Finiteness): 알고리즘은 반드시 종료되어야 합니다.입력 (Input): 0개 이상의 입력이 있어야 합니다.출력 (Output): 1개 이상의 출력이 있어야 합니다.효율성 (Efficiency): 시간과 공간 측면에서 효율적이어야 합니다.자료구조 (Data Structure)자료구조는 데이터를 저장하고 조직화하는 방법입니다. 자료구조는 데이터에 대한 접근 및 수정 작업을 효율적으로.. 2024. 7. 1. 이전 1 2 3 4 다음 반응형
