본문 바로가기
반응형
[C++로 배우는 알고리즘과 자료구조] Day 22: 이진 탐색 (Binary Search) 이진 탐색 (Binary Search)이진 탐색은 정렬된 배열에서 원하는 값을 찾는 효율적인 알고리즘입니다. 배열의 중간 값을 선택하고, 중간 값과 찾고자 하는 값을 비교하여 검색 범위를 절반으로 줄여가며 탐색합니다.이진 탐색의 시간 복잡도:최선의 경우: (O(1))평균의 경우: (O(\log n))최악의 경우: (O(\log n))이진 탐색 구현이진 탐색은 재귀적으로 또는 반복적으로 구현할 수 있습니다. 재귀적 이진 탐색 구현#include #include // 재귀적 이진 탐색 함수int binarySearchRecursive(const std::vector& arr, int left, int right, int target) { if (right >= left) { int mid .. 2024. 8. 1.
[C++로 배우는 알고리즘과 자료구조 심화] Day 22: 고급 정렬 알고리즘 (TimSort, IntroSort) 고급 정렬 알고리즘정렬 알고리즘은 데이터 처리와 분석에서 매우 중요한 역할을 합니다. 오늘은 두 가지 고급 정렬 알고리즘인 TimSort와 IntroSort에 대해 학습하겠습니다. 이 두 알고리즘은 효율성과 안정성 측면에서 매우 강력하며, 실세계에서 널리 사용됩니다.TimSortTimSort는 삽입 정렬과 병합 정렬을 혼합한 하이브리드 정렬 알고리즘입니다. 이 알고리즘은 실제 데이터가 부분적으로 정렬되어 있는 경우 매우 효율적입니다. Python의 sort() 함수와 Java의 Arrays.sort()에서 사용되는 기본 정렬 알고리즘이기도 합니다.TimSort의 주요 단계Runs 분할: 주어진 배열을 일정 크기(기본적으로 32 또는 64)로 분할하여 각각을 정렬합니다.Runs 병합: 병합 정렬을 사용하여.. 2024. 8. 1.
[C++ 성능 최적화 및 고급 테크닉] Day 23: 실전 최적화 사례 연구 (2) 실전 최적화 사례 연구오늘은 실전에서 성능을 최적화한 사례를 더 깊이 연구하겠습니다. 특히, 데이터 구조의 선택과 알고리즘의 효율성을 고려한 최적화 기법을 살펴보겠습니다. 사례 1: 데이터 구조 최적화적절한 데이터 구조를 선택하면 성능을 크게 향상시킬 수 있습니다. 예를 들어, 해시맵을 사용하여 탐색 시간을 줄일 수 있습니다. 예제 코드: 데이터 구조 최적화 전#include #include bool contains(const std::vector& vec, int value) { for (int i : vec) { if (i == value) { return true; } } return false;}int main() { std::ve.. 2024. 8. 1.
[C++로 배우는 알고리즘과 자료구조] Day 20: 힙 정렬 (Heap Sort) 힙 정렬 (Heap Sort)힙 정렬은 이진 힙을 이용한 정렬 알고리즘으로, 최대 힙 또는 최소 힙을 사용하여 배열을 정렬합니다. 힙 정렬은 평균 및 최악의 경우 시간 복잡도가 (O(n \log n))입니다.힙 정렬의 주요 단계:힙 구성 (Heapify): 배열을 이진 힙으로 변환합니다.정렬 (Sort): 힙의 루트 요소를 제거하고, 힙을 재구성하여 정렬된 배열을 만듭니다.힙 정렬의 시간 복잡도:평균의 경우: (O(n \log n))최악의 경우: (O(n \log n))최선의 경우: (O(n \log n))힙 정렬 구현힙 구성 함수힙 속성을 유지하면서 배열을 이진 힙으로 변환합니다.#include #include // 힙 구성 함수void heapify(std::vector& arr, int n, int.. 2024. 8. 1.
[C++로 배우는 알고리즘과 자료구조 심화] Day 20: 배낭 문제 변형 (Multiple Knapsack, Unbounded Knapsack) 배낭 문제 변형배낭 문제는 여러 변형이 있습니다. 오늘은 두 가지 주요 변형인 다중 배낭 문제(Multiple Knapsack Problem)와 무제한 배낭 문제(Unbounded Knapsack Problem)에 대해 학습하겠습니다.다중 배낭 문제 (Multiple Knapsack Problem)다중 배낭 문제는 여러 개의 배낭이 주어졌을 때, 각 배낭에 아이템을 넣어 최대 가치를 얻는 문제입니다. 이는 기본 배낭 문제의 확장으로, 각 배낭마다 최대 용량이 다를 수 있습니다.문제 정의주어진 배낭의 수 (m)각 배낭의 최대 용량 (W_i)각 아이템의 무게 (w_j)와 가치 (v_j)다중 배낭 문제 구현다음은 C++로 다중 배낭 문제를 해결하는 예제입니다.#include #include #include i.. 2024. 8. 1.
[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 18: 트리 동적 계획법 (Tree DP) 트리 동적 계획법 (Tree DP)트리 동적 계획법(Tree DP)은 트리 구조를 가진 문제를 해결하기 위한 효율적인 방법입니다. 이는 주로 트리의 정점이나 간선을 따라 상태를 정의하고, 하위 트리에서의 정보를 이용하여 전체 문제를 해결하는 기법입니다.문제 예시: 트리의 최대 독립 집합 (Maximum Independent Set of a Tree)주어진 트리에서 서로 인접하지 않은 정점의 최대 집합을 찾는 문제입니다. 이는 트리 DP를 사용하여 효율적으로 해결할 수 있습니다.문제 정의주어진 트리의 정점 수 (n)트리의 간선 정보최대 독립 집합의 크기 계산트리 DP 구현다음은 C++로 트리의 최대 독립 집합 문제를 해결하는 예제입니다.#include #include #include const int MA.. 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 19: 스테이트 컴프레션 동적 계획법 (State Compression DP) 스테이트 컴프레션 동적 계획법 (State Compression DP)스테이트 컴프레션 동적 계획법(State Compression DP)은 상태를 비트마스크로 표현하여 동적 계획법을 적용하는 기법입니다. 이는 주로 부분 집합 문제나 조합 최적화 문제에 사용됩니다. 이 기법은 상태를 효율적으로 관리하고, 메모리 사용량을 줄일 수 있습니다.문제 예시: 여행 계획주어진 도시들을 방문하면서 최소 비용으로 여행 계획을 세우는 문제를 해결하기 위해 스테이트 컴프레션 DP를 사용할 수 있습니다. 여기서 dp[mask][i]는 방문한 도시 집합이 mask이고 현재 i 도시에 위치한 경우의 최소 비용을 의미합니다.스테이트 컴프레션 DP 구현다음은 C++로 스테이트 컴프레션 DP를 사용하여 문제를 해결하는 예제입니다.#.. 2024. 8. 1.
반응형

티스토리툴바