반응형 자료구조73 [C++로 배우는 알고리즘과 자료구조] Day 24: 너비 우선 탐색 (BFS) 너비 우선 탐색 (BFS, Breadth-First Search)너비 우선 탐색(BFS)은 그래프 탐색 알고리즘 중 하나로, 시작 정점에서 출발하여 인접한 정점들을 모두 탐색한 후, 탐색이 끝난 정점의 인접 정점을 탐색하는 방식입니다. BFS는 큐 자료구조를 사용하여 구현할 수 있습니다.BFS의 주요 특징:시간 복잡도: (O(V + E)), 여기서 (V)는 정점의 수, (E)는 간선의 수입니다.공간 복잡도: (O(V)), 큐와 방문 여부를 저장하는 배열의 크기입니다.BFS 구현그래프 구현 (인접 리스트 사용)#include #include #include #include // 그래프 클래스 정의class Graph {public: Graph(int vertices); void addEdge(i.. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조 심화] Day 24: 확률적 알고리즘 (Monte Carlo, Las Vegas 알고리즘) 확률적 알고리즘확률적 알고리즘은 무작위성을 도입하여 문제를 해결하는 알고리즘입니다. 이러한 알고리즘은 일반적으로 평균적인 성능이 좋으며, 최악의 경우를 피할 수 있습니다. 확률적 알고리즘은 크게 두 가지 유형으로 나눌 수 있습니다: Monte Carlo 알고리즘과 Las Vegas 알고리즘.Monte Carlo 알고리즘Monte Carlo 알고리즘은 정해진 시간 내에 정답을 찾을 확률을 높이는 알고리즘입니다. 정확한 답을 보장하지 않지만, 답을 찾을 확률이 높습니다.예시: 소수 판별Monte Carlo 알고리즘을 사용하여 주어진 수가 소수인지 판별하는 방법입니다. 주로 Miller-Rabin 소수 판별법이 사용됩니다. Monte Carlo 알고리즘 구현: Miller-Rabin 소수 판별법#include.. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조 심화] Day 21: 문자열 동적 계획법 (Edit Distance, Longest Common Subsequence) 문자열 동적 계획법문자열 관련 문제는 많은 응용 분야에서 중요합니다. 오늘은 두 가지 주요 문제인 편집 거리(Edit Distance)와 최장 공통 부분 수열(Longest Common Subsequence, LCS)에 대해 학습하겠습니다.편집 거리 (Edit Distance)편집 거리(Edit Distance)는 두 문자열을 같게 만들기 위해 필요한 최소 편집 연산 횟수를 의미합니다. 가능한 편집 연산은 삽입, 삭제, 교체입니다.문제 정의두 문자열 ( s1 )과 ( s2 )가 주어졌을 때, ( s1 )을 ( s2 )로 변환하는 데 필요한 최소 편집 연산 횟수를 계산합니다.편집 거리 구현다음은 C++로 편집 거리 문제를 해결하는 예제입니다.#include #include #include #include .. 2024. 8. 1. [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 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. 이전 1 2 3 4 5 6 ··· 9 다음 반응형
