반응형 [C++로 배우는 알고리즘과 자료구조] Day 21: 기수 정렬과 계수 정렬 기수 정렬 (Radix Sort)기수 정렬은 각 자릿수를 기준으로 정렬하는 비교 기반이 아닌 정렬 알고리즘입니다. 기수 정렬은 주로 정수나 문자열을 정렬하는 데 사용되며, 각 자릿수에 대해 계수 정렬을 사용하여 정렬을 수행합니다.기수 정렬의 시간 복잡도:(O(d \times (n + k))), 여기서 (d)는 자릿수의 개수, (n)은 요소의 개수, (k)는 기수(base)입니다.기수 정렬 구현#include #include #include // 계수 정렬 함수void countingSort(std::vector& arr, int exp) { int n = arr.size(); std::vector output(n); // 정렬된 결과를 저장할 배열 int count[10] = {0}; .. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조] Day 18: 합병 정렬 (Merge Sort) 합병 정렬 (Merge Sort)합병 정렬은 분할 정복(Divide and Conquer) 기법을 사용하는 효율적인 정렬 알고리즘입니다. 배열을 반으로 나누어 각각을 정렬한 후, 두 개의 정렬된 배열을 하나의 정렬된 배열로 합병하는 과정을 반복합니다.합병 정렬의 시간 복잡도:평균의 경우: (O(n \log n))최악의 경우: (O(n \log n))최선의 경우: (O(n \log n))합병 정렬의 공간 복잡도:(O(n))합병 정렬 구현합병 정렬의 주요 단계:분할 (Divide): 배열을 두 개의 하위 배열로 분할합니다.정복 (Conquer): 하위 배열을 재귀적으로 정렬합니다.합병 (Combine): 두 개의 정렬된 하위 배열을 하나의 정렬된 배열로 합병합니다.합병 정렬의 구현 코드#include #in.. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조] Day 19: 퀵 정렬 (Quick Sort) 퀵 정렬 (Quick Sort)퀵 정렬은 분할 정복(Divide and Conquer) 기법을 사용하는 효율적인 정렬 알고리즘입니다. 배열을 피벗(Pivot)을 기준으로 두 개의 하위 배열로 나눈 다음, 각각을 정렬합니다. 퀵 정렬은 평균적으로 매우 빠른 정렬 알고리즘으로 간주됩니다.퀵 정렬의 시간 복잡도:평균의 경우: (O(n \log n))최악의 경우: (O(n^2))최선의 경우: (O(n \log n))퀵 정렬의 공간 복잡도:(O(\log n)) (재귀 호출 스택 공간)퀵 정렬 구현퀵 정렬의 주요 단계:분할 (Partition): 피벗을 기준으로 배열을 두 부분으로 나눕니다.정복 (Conquer): 하위 배열을 재귀적으로 정렬합니다.결합 (Combine): 분할된 하위 배열이 정렬된 상태이므로 추가.. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조] Day 16: 버블 정렬과 선택 정렬 버블 정렬 (Bubble Sort)버블 정렬은 가장 간단한 정렬 알고리즘 중 하나로, 인접한 두 요소를 비교하여 필요에 따라 자리를 바꾸면서 배열을 정렬합니다. 배열의 끝까지 이 과정을 반복하면 가장 큰 값이 맨 끝에 위치하게 됩니다. 이 과정을 여러 번 반복하여 배열이 정렬될 때까지 진행합니다.버블 정렬의 시간 복잡도:최선의 경우: (O(n))평균의 경우: (O(n^2))최악의 경우: (O(n^2))버블 정렬 구현#include #include // 버블 정렬 함수void bubbleSort(std::vector& arr) { int n = arr.size(); for (int i = 0; i arr[j + 1]) { std::swap(arr[j], arr[j +.. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조] Day 17: 삽입 정렬과 쉘 정렬 삽입 정렬 (Insertion Sort)삽입 정렬은 배열의 요소를 하나씩 정렬된 부분에 삽입하는 방식으로 동작합니다. 각 요소를 적절한 위치에 삽입하기 위해 이미 정렬된 부분을 오른쪽으로 이동시킵니다.삽입 정렬의 시간 복잡도:최선의 경우: (O(n))평균의 경우: (O(n^2))최악의 경우: (O(n^2))삽입 정렬 구현#include #include // 삽입 정렬 함수void insertionSort(std::vector& arr) { int n = arr.size(); for (int i = 1; i = 0 && arr[j] > key) { arr[j + 1] = arr[j]; // 정렬된 부분에서 키보다 큰 요소 이동 --j; } .. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조 ] Day 14: 해시 함수와 충돌 해결 기법 해시 함수 (Hash Function)해시 함수는 임의의 크기를 가진 데이터를 고정된 크기의 해시 값으로 변환하는 함수입니다. 해시 테이블에서 해시 함수는 주어진 키를 인덱스로 변환하여 데이터의 저장 및 검색을 효율적으로 수행합니다.해시 함수의 특성:결정적 (Deterministic): 동일한 입력에 대해 항상 동일한 해시 값을 반환해야 합니다.균등 분포 (Uniform Distribution): 해시 값이 가능한 고르게 분포되어야 합니다.빠른 계산 (Fast Computation): 해시 값을 빠르게 계산할 수 있어야 합니다.충돌 해결 기법 (Collision Resolution)해시 테이블에서 두 개 이상의 키가 동일한 해시 값을 가지는 경우를 충돌(Collision)이라고 합니다. 충돌을 해결하기 .. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조] Day 15: 정렬 알고리즘 개요 정렬 알고리즘 (Sorting Algorithms)정렬 알고리즘은 주어진 데이터를 특정 순서대로 정렬하는 알고리즘입니다. 정렬은 컴퓨터 과학에서 매우 중요한 개념으로, 데이터의 효율적인 검색 및 정렬된 데이터를 필요로 하는 다양한 알고리즘의 기반이 됩니다.정렬 알고리즘의 종류:버블 정렬 (Bubble Sort)선택 정렬 (Selection Sort)삽입 정렬 (Insertion Sort)합병 정렬 (Merge Sort)퀵 정렬 (Quick Sort)힙 정렬 (Heap Sort)기수 정렬 (Radix Sort)계수 정렬 (Counting Sort)정렬 알고리즘 비교비교 기준:시간 복잡도 (Time Complexity): 알고리즘이 실행되는 데 걸리는 시간의 척도입니다.공간 복잡도 (Space Complex.. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조] Day 12: 그래프 표현 방법 (인접 리스트, 인접 행렬) 그래프 표현 방법그래프는 다양한 방식으로 표현할 수 있습니다. 주요한 두 가지 방법은 인접 리스트와 인접 행렬입니다. 각 표현 방법은 공간 복잡도와 특정 연산에 대한 시간 복잡도에서 장단점이 있습니다.인접 리스트 (Adjacency List)인접 리스트는 그래프의 각 노드가 연결된 노드의 리스트를 가지는 방식으로 그래프를 표현합니다. 이 방법은 연결 리스트나 벡터를 사용하여 구현할 수 있습니다.인접 리스트의 특징:공간 복잡도: (O(V + E)), 여기서 (V)는 노드의 수, (E)는 간선의 수입니다.장점: 희소 그래프(Sparse Graph)에 적합하며, 메모리 사용이 효율적입니다.단점: 두 노드 간의 연결 여부를 확인하는 데 O(V)의 시간이 소요될 수 있습니다.인접 리스트 구현AdjacencyLis.. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조] Day 13: 이진 힙과 힙 정렬 이진 힙 (Binary Heap)이진 힙은 완전 이진 트리의 형태를 가지며, 각 노드가 특정한 우선순위를 가지는 자료구조입니다. 이진 힙은 주로 최대값이나 최소값을 빠르게 찾기 위해 사용됩니다. 이진 힙에는 최대 힙(Max-Heap)과 최소 힙(Min-Heap)이 있습니다.이진 힙의 종류:최대 힙 (Max-Heap): 부모 노드의 값이 자식 노드의 값보다 크거나 같습니다.최소 힙 (Min-Heap): 부모 노드의 값이 자식 노드의 값보다 작거나 같습니다.힙 정렬 (Heap Sort)힙 정렬은 이진 힙을 이용한 정렬 알고리즘으로, 최대 힙 또는 최소 힙을 사용하여 배열을 정렬합니다. 힙 정렬은 평균 및 최악의 경우 시간 복잡도가 (O(n \log n))입니다.힙 정렬의 과정:배열을 이진 힙으로 변환합니다... 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조 ] Day 10: 트라이 (Trie) 트라이 (Trie)트라이는 문자열을 효율적으로 저장하고 검색하기 위한 트리 기반 자료구조입니다. 트라이는 주로 문자열 집합의 검색, 삽입, 삭제에 사용되며, 접두사 검색에 매우 효율적입니다.트라이의 특징:노드 구조: 각 노드는 문자와 자식 노드를 가집니다.루트 노드: 루트 노드는 빈 문자열을 나타냅니다.경로: 문자열은 루트 노드에서 시작하여 각 문자에 해당하는 노드를 따라 내려가면서 표현됩니다.접두사 검색: 공통 접두사를 가진 문자열을 효율적으로 검색할 수 있습니다.트라이 구현TrieNode.h#ifndef TRIENODE_H#define TRIENODE_H#include // 트라이의 노드 구조체struct TrieNode { std::unordered_map children; // 자식 노드를 .. 2024. 8. 1. 이전 1 2 3 4 다음 반응형
