본문 바로가기
반응형
[C++로 배우는 알고리즘과 자료구조] Day 29: 분할 정복 기법 분할 정복 기법 (Divide and Conquer)분할 정복 기법은 문제를 더 작은 부분 문제로 나누어 해결한 후, 그 결과를 결합하여 전체 문제의 해를 구하는 알고리즘 설계 기법입니다. 대표적인 예로 합병 정렬(Merge Sort)과 퀵 정렬(Quick Sort)이 있습니다.분할 정복 기법의 주요 단계:분할 (Divide): 문제를 더 작은 부분 문제로 나눕니다.정복 (Conquer): 각 부분 문제를 재귀적으로 해결합니다.결합 (Combine): 부분 문제의 해를 결합하여 전체 문제의 해를 구합니다.대표적인 분할 정복 알고리즘: 합병 정렬합병 정렬 (Merge Sort)합병 정렬은 분할 정복 기법을 사용하는 효율적인 정렬 알고리즘입니다. 배열을 반으로 나누어 각각을 정렬한 후, 두 개의 정렬된 배열.. 2024. 8. 1.
[C++로 배우는 알고리즘과 자료구조] Day 30: 알고리즘 문제 해결 및 코딩 테스트 준비 알고리즘 문제 해결 및 코딩 테스트 준비코딩 테스트는 프로그래밍 실력을 검증하기 위한 중요한 과정입니다. 알고리즘과 자료구조를 잘 이해하고, 다양한 문제를 해결할 수 있는 능력을 갖추는 것이 중요합니다. 오늘은 알고리즘 문제 해결 및 코딩 테스트 준비에 필요한 몇 가지 팁과 예제를 다루겠습니다.코딩 테스트 준비 팁기본기 다지기:알고리즘과 자료구조의 기본 개념을 확실히 이해합니다.배열, 문자열, 스택, 큐, 링크드 리스트, 해시 테이블, 트리, 그래프 등을 학습합니다.다양한 문제 풀기:다양한 알고리즘 문제를 풀어보며 문제 해결 능력을 키웁니다.LeetCode, HackerRank, CodeSignal, Programmers와 같은 온라인 플랫폼에서 문제를 풉니다.시간 복잡도와 공간 복잡도 이해:알고리즘의 .. 2024. 8. 1.
[C++로 배우는 알고리즘과 자료구조] Day 27: 최소 신장 트리 (크루스칼, 프림 알고리즘) 최소 신장 트리 (MST, Minimum Spanning Tree)최소 신장 트리(MST)는 가중치가 있는 연결된 그래프에서 모든 정점을 포함하며, 간선의 가중치 합이 최소가 되는 트리입니다. MST를 찾는 대표적인 알고리즘으로는 크루스칼 알고리즘과 프림 알고리즘이 있습니다.크루스칼 알고리즘 (Kruskal's Algorithm)크루스칼 알고리즘은 간선을 가중치의 오름차순으로 정렬한 후, 사이클을 형성하지 않는 간선을 선택하여 MST를 구성하는 알고리즘입니다.크루스칼 알고리즘의 시간 복잡도:(O(E \log E + E \log V)), 여기서 (E)는 간선의 수, (V)는 정점의 수입니다.크루스칼 알고리즘 구현그래프 구현 (간선 리스트 사용)#include #include #include // 간선 구조.. 2024. 8. 1.
[C++로 배우는 알고리즘과 자료구조] Day 28: 동적 계획법 (DP) 기초 동적 계획법 (Dynamic Programming, DP)동적 계획법(DP)은 복잡한 문제를 해결하기 위해 작은 부분 문제로 나누어 해결하고, 그 결과를 저장하여 전체 문제의 해를 구하는 알고리즘 설계 기법입니다. DP는 주로 재귀적 구조를 가지며, 중복되는 부분 문제를 해결하여 효율성을 높입니다.DP의 주요 특징:중복된 부분 문제 (Overlapping Subproblems): 문제를 해결하는 과정에서 동일한 부분 문제가 여러 번 재계산됩니다.최적 부분 구조 (Optimal Substructure): 문제의 최적 해는 부분 문제의 최적 해로 구성될 수 있습니다.DP의 접근 방식:탑다운 (Top-Down): 재귀 + 메모이제이션바텀업 (Bottom-Up): 반복문 + 테이블피보나치 수열 (Fibonacc.. 2024. 8. 1.
[C++로 배우는 알고리즘과 자료구조] Day 25: 다익스트라 알고리즘 (Dijkstra's Algorithm) 다익스트라 알고리즘 (Dijkstra's Algorithm)다익스트라 알고리즘은 가중치가 있는 그래프에서 단일 출발점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 음수 가중치가 없는 그래프에서 작동합니다.다익스트라 알고리즘의 시간 복잡도:일반적인 구현: (O(V^2))우선순위 큐를 사용한 구현 (힙): (O((V + E) \log V))다익스트라 알고리즘 구현그래프 구현 (인접 리스트 사용)#include #include #include #include #include // 그래프 클래스 정의class Graph {public: Graph(int vertices); void addEdge(int u, int v, int weight); // 간선 추가 vo.. 2024. 8. 1.
[C++로 배우는 알고리즘과 자료구조] Day 26: 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm) 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)플로이드-워셜 알고리즘은 모든 정점 쌍 간의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 음의 가중치가 있는 그래프에서도 작동하지만, 음의 사이클이 있는 그래프에서는 사용할 수 없습니다.플로이드-워셜 알고리즘의 시간 복잡도:(O(V^3)), 여기서 (V)는 정점의 수입니다.플로이드-워셜 알고리즘 구현그래프 구현 (인접 행렬 사용)#include #include #include // 무한대 값을 나타내는 상수const int INF = INT_MAX;// 그래프 클래스 정의class Graph {public: Graph(int vertices); void addEdge(int u, int v, int weight); // .. 2024. 8. 1.
[C++로 배우는 알고리즘과 자료구조] Day 23: 깊이 우선 탐색 (DFS) 깊이 우선 탐색 (DFS, Depth-First Search)깊이 우선 탐색(DFS)은 그래프 탐색 알고리즘 중 하나로, 가능한 한 깊게 탐색한 후 더 이상 깊이 갈 수 없으면 다시 되돌아와 다른 경로를 탐색하는 방식입니다. DFS는 스택 자료구조를 사용하여 구현할 수 있으며, 재귀적으로도 구현이 가능합니다.DFS의 주요 특징:시간 복잡도: (O(V + E)), 여기서 (V)는 정점의 수, (E)는 간선의 수입니다.공간 복잡도: (O(V)), 재귀 호출 스택의 깊이입니다.DFS 구현그래프 구현 (인접 리스트 사용)#include #include #include // 그래프 클래스 정의class Graph {public: Graph(int vertices); void addEdge(int v, .. 2024. 8. 1.
[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 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 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.
반응형

티스토리툴바