반응형 [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 7: 스킵 리스트 (Skip List) 스킵 리스트 (Skip List)스킵 리스트는 연결 리스트에 인덱스를 추가하여 검색, 삽입, 삭제 연산의 시간 복잡도를 (O(\log n))으로 개선한 자료구조입니다. 여러 레벨로 구성된 연결 리스트로, 각 레벨마다 원소를 건너뛰어가며 검색할 수 있습니다. 이는 균형 이진 탐색 트리와 유사한 시간 복잡도를 가지면서도 구현이 간단합니다.스킵 리스트의 주요 특징시간 복잡도:평균: (O(\log n))최악의 경우: (O(n))레벨 구조: 여러 레벨의 리스트로 구성되며, 각 레벨은 원소를 건너뛰어가며 검색할 수 있도록 합니다.확률적 균형 유지: 랜덤하게 레벨을 선택하여 원소를 삽입함으로써 확률적으로 균형을 유지합니다.스킵 리스트의 기본 연산삽입 (Insert): 새로운 원소를 삽입하고 레벨을 랜덤하게 결정합니다.. 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 5: 균형 이진 탐색 트리 (AVL 트리, Red-Black 트리) 균형 이진 탐색 트리 (AVL 트리)AVL 트리는 자가 균형 이진 탐색 트리로, 각 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하가 되도록 유지합니다. 이는 트리의 균형을 유지하여 탐색, 삽입, 삭제 연산의 시간 복잡도가 (O(\log n))이 되도록 합니다.AVL 트리의 주요 특징균형 조건: 각 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하가 되도록 유지합니다.회전 연산: 삽입 및 삭제 후 균형을 유지하기 위해 회전 연산을 사용합니다.AVL 트리의 기본 연산삽입 (Insert): 새로운 노드를 삽입한 후 균형을 유지합니다.삭제 (Delete): 특정 키를 가진 노드를 삭제한 후 균형을 유지합니다.검색 (Search): 특정 키를 가진 노드를 검색합니다.AVL 트리의 구현.. 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 3: 펜윅 트리 (Fenwick Tree, Binary Indexed Tree) 펜윅 트리 (Fenwick Tree, Binary Indexed Tree)펜윅 트리(BIT, Fenwick Tree)는 배열의 구간 합을 효율적으로 계산하고 업데이트할 수 있는 자료구조입니다. 세그먼트 트리와 유사하지만, 구현이 더 간단하고 메모리 사용량이 적습니다.펜윅 트리의 주요 특징시간 복잡도:업데이트: (O(\log n))쿼리: (O(\log n))구현 방법:트리의 각 노드는 배열의 특정 구간에 대한 정보를 저장합니다.이진수의 비트 연산을 활용하여 구간을 관리합니다.펜윅 트리의 기본 연산업데이트 (Update): 특정 인덱스의 값을 업데이트합니다.쿼리 (Query): 특정 인덱스까지의 구간 합을 계산합니다.펜윅 트리의 구현다음은 C++로 펜윅 트리를 구현한 예제입니다. 구간 합을 구하고 구간 값을.. 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 4: 이면 탐색 트리 (Treap) 이면 탐색 트리 (Treap)이면 탐색 트리(Treap)는 이진 탐색 트리(BST)와 힙(Heap)의 특성을 동시에 가지는 자료구조입니다. 각 노드는 키(key)와 우선순위(priority)를 가지며, 다음 두 가지 성질을 만족합니다:이진 탐색 트리 성질: 키의 값에 대해 이진 탐색 트리 성질을 만족합니다.힙 성질: 우선순위에 대해 최대 힙 또는 최소 힙 성질을 만족합니다.트라이의 주요 특징삽입, 삭제, 검색:평균 시간 복잡도: (O(\log n))최악의 경우 시간 복잡도: (O(n))회전 연산:이중회전을 통해 트리의 균형을 유지합니다.트라이의 기본 연산삽입 (Insert): 새로운 노드를 삽입합니다.삭제 (Delete): 특정 키를 가진 노드를 삭제합니다.검색 (Search): 특정 키를 가진 노드를 .. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조 심화] Day 2: 세그먼트 트리 (Segment Tree) 세그먼트 트리 (Segment Tree)세그먼트 트리는 주어진 배열의 구간에 대한 정보를 효율적으로 저장하고 쿼리를 처리하기 위해 사용하는 트리 구조입니다. 세그먼트 트리는 다음과 같은 연산을 빠르게 수행할 수 있습니다:구간 합: 배열의 특정 범위에 대한 합을 구합니다.구간 최솟값/최댓값: 배열의 특정 범위에 대한 최솟값 또는 최댓값을 구합니다.구간 갱신: 배열의 특정 범위에 값을 갱신합니다.세그먼트 트리의 주요 특징시간 복잡도:빌드: (O(n))쿼리: (O(\log n))업데이트: (O(\log n))구현 방법:트리의 각 노드는 배열의 특정 구간을 나타냅니다.루트 노드는 전체 배열을 나타내고, 각 자식 노드는 배열의 절반 구간을 나타냅니다.세그먼트 트리의 기본 연산트리 빌드: 초기 배열을 기반으로 세그.. 2024. 8. 1. 이전 1 ··· 3 4 5 6 7 8 다음 반응형
