반응형 [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. [C++로 배우는 알고리즘과 자료구조 심화] Day 15: 다차원 동적 계획법 (Multidimensional DP) 다차원 동적 계획법 (Multidimensional DP)다차원 동적 계획법은 상태를 여러 차원으로 정의하여 문제를 해결하는 기법입니다. 이 방법은 주로 상태를 더 구체적으로 나누어 관리할 때 사용됩니다. 예를 들어, 3차원 DP는 dp[i][j][k]와 같이 상태를 표현할 수 있습니다.문제 예시: 3차원 DP를 이용한 여행 계획주어진 도시들을 방문하면서 최소 비용으로 여행 계획을 세우는 문제를 해결하기 위해 3차원 DP를 사용할 수 있습니다. 여기서 dp[i][j][k]는 i번째 도시를 j번째 날에 k번 방문했을 때의 최소 비용을 의미합니다. 다차원 DP 구현다음은 C++로 3차원 DP를 사용하여 문제를 해결하는 예제입니다. 문제 정의주어진 도시들의 방문 비용이 포함된 cost 행렬이 있습니다. 여행자.. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조] Day 12: 그래프 표현 방법 (인접 리스트, 인접 행렬) 그래프 표현 방법그래프는 다양한 방식으로 표현할 수 있습니다. 주요한 두 가지 방법은 인접 리스트와 인접 행렬입니다. 각 표현 방법은 공간 복잡도와 특정 연산에 대한 시간 복잡도에서 장단점이 있습니다.인접 리스트 (Adjacency List)인접 리스트는 그래프의 각 노드가 연결된 노드의 리스트를 가지는 방식으로 그래프를 표현합니다. 이 방법은 연결 리스트나 벡터를 사용하여 구현할 수 있습니다.인접 리스트의 특징:공간 복잡도: (O(V + E)), 여기서 (V)는 노드의 수, (E)는 간선의 수입니다.장점: 희소 그래프(Sparse Graph)에 적합하며, 메모리 사용이 효율적입니다.단점: 두 노드 간의 연결 여부를 확인하는 데 O(V)의 시간이 소요될 수 있습니다.인접 리스트 구현AdjacencyLis.. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조 심화] Day 12: 네트워크 흐름 알고리즘 (Ford-Fulkerson, Edmonds-Karp) 네트워크 흐름 알고리즘네트워크 흐름 알고리즘은 유량 네트워크에서 최대 유량을 찾는 데 사용됩니다. 유량 네트워크는 용량이 지정된 방향성 그래프로, 네트워크의 한 정점에서 다른 정점으로 흐르는 유량을 나타냅니다. 오늘은 Ford-Fulkerson 알고리즘과 Edmonds-Karp 알고리즘에 대해 학습하겠습니다.Ford-Fulkerson 알고리즘Ford-Fulkerson 알고리즘은 증가 경로(augmenting path)를 반복적으로 찾아 최대 유량을 계산하는 알고리즘입니다. 이 알고리즘은 DFS를 사용하여 증가 경로를 찾습니다.Ford-Fulkerson 알고리즘의 시간 복잡도:최악의 경우: (O(E \times f)), 여기서 (E)는 간선의 수, (f)는 최대 유량입니다.Ford-Fulkerson 알고리.. 2024. 8. 1. 이전 1 2 3 4 5 6 7 8 다음 반응형
