반응형 자료구조72 [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 19: 스테이트 컴프레션 동적 계획법 (State Compression DP) 스테이트 컴프레션 동적 계획법 (State Compression DP)스테이트 컴프레션 동적 계획법(State Compression DP)은 상태를 비트마스크로 표현하여 동적 계획법을 적용하는 기법입니다. 이는 주로 부분 집합 문제나 조합 최적화 문제에 사용됩니다. 이 기법은 상태를 효율적으로 관리하고, 메모리 사용량을 줄일 수 있습니다.문제 예시: 여행 계획주어진 도시들을 방문하면서 최소 비용으로 여행 계획을 세우는 문제를 해결하기 위해 스테이트 컴프레션 DP를 사용할 수 있습니다. 여기서 dp[mask][i]는 방문한 도시 집합이 mask이고 현재 i 도시에 위치한 경우의 최소 비용을 의미합니다.스테이트 컴프레션 DP 구현다음은 C++로 스테이트 컴프레션 DP를 사용하여 문제를 해결하는 예제입니다.#.. 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 16: DP 최적화 기법 (Convex Hull Trick, Divide and Conquer Optimization) DP 최적화 기법동적 계획법(DP)은 많은 문제를 효율적으로 해결할 수 있는 강력한 도구입니다. 그러나 때로는 DP의 시간 복잡도를 더 최적화할 필요가 있습니다. 오늘은 두 가지 주요 DP 최적화 기법에 대해 학습하겠습니다: Convex Hull Trick과 Divide and Conquer Optimization.Convex Hull TrickConvex Hull Trick은 주로 함수 (y = ax + b)의 최솟값이나 최댓값을 효율적으로 찾는 문제에서 사용됩니다. 이 기법은 선형 함수들의 집합을 유지하고, 각 쿼리마다 특정 (x)에서의 최소 (y) 또는 최대 (y)를 빠르게 계산합니다.문제 예시다음과 같은 문제를 고려해봅시다:주어진 선형 함수들의 집합 ({y = a_1x + b_1, y = a_2x.. 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 17: 비트마스크 동적 계획법 (Bitmask DP) 비트마스크 동적 계획법 (Bitmask DP)비트마스크 동적 계획법은 상태를 이진수로 표현하여 여러 상태를 효율적으로 관리하는 기법입니다. 주로 부분 집합 문제나 조합 최적화 문제에 사용됩니다. 상태를 이진수로 표현하면 각 비트가 특정 원소의 포함 여부를 나타내어 간결하게 표현할 수 있습니다.문제 예시: 외판원 문제 (Traveling Salesman Problem, TSP)외판원 문제는 주어진 도시들을 방문하여 모든 도시를 한 번씩 방문하고 시작점으로 돌아올 때, 이동 비용의 합이 최소가 되도록 하는 경로를 찾는 문제입니다. 비트마스크 DP를 사용하여 해결할 수 있습니다.문제 정의주어진 도시 수 (n)각 도시 간의 거리 (dist[i][j])최소 이동 비용을 계산하여 출력비트마스크 DP 구현다음은 C+.. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조 ] Day 14: 해시 함수와 충돌 해결 기법 해시 함수 (Hash Function)해시 함수는 임의의 크기를 가진 데이터를 고정된 크기의 해시 값으로 변환하는 함수입니다. 해시 테이블에서 해시 함수는 주어진 키를 인덱스로 변환하여 데이터의 저장 및 검색을 효율적으로 수행합니다.해시 함수의 특성:결정적 (Deterministic): 동일한 입력에 대해 항상 동일한 해시 값을 반환해야 합니다.균등 분포 (Uniform Distribution): 해시 값이 가능한 고르게 분포되어야 합니다.빠른 계산 (Fast Computation): 해시 값을 빠르게 계산할 수 있어야 합니다.충돌 해결 기법 (Collision Resolution)해시 테이블에서 두 개 이상의 키가 동일한 해시 값을 가지는 경우를 충돌(Collision)이라고 합니다. 충돌을 해결하기 .. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조 심화] Day 14: 중국인의 나머지 정리 (Chinese Remainder Theorem) 중국인의 나머지 정리 (Chinese Remainder Theorem, CRT)중국인의 나머지 정리(CRT)는 서로 다른 소수들의 모듈러 시스템에서 주어진 나머지 값을 갖는 수를 찾는 방법입니다. CRT는 정수론과 암호학, 병렬 컴퓨팅 등 여러 분야에서 활용됩니다.중국인의 나머지 정리다음은 중국인의 나머지 정리의 기본 공식입니다:주어진 서로 다른 정수 (n_1, n_2, \ldots, n_k)가 서로소(즉, (\gcd(n_i, n_j) = 1), (i \ne j))일 때, 다음과 같은 동시 합동식 시스템을 만족하는 유일한 정수 (x)가 존재합니다: [\begin{cases}x \equiv a_1 \pmod{n_1} \x \equiv a_2 \pmod{n_2} \\vdots \x \equiv a_k \pm.. 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. 이전 1 2 3 4 5 6 7 8 다음 반응형
