반응형 자료구조73 [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. [C++로 배우는 알고리즘과 자료구조 심화] Day 13: 이분 그래프 매칭 (Hopcroft-Karp 알고리즘) 이분 그래프 매칭 (Bipartite Graph Matching)이분 그래프 매칭은 두 개의 분리된 정점 집합을 가지는 그래프에서 최대 매칭을 찾는 문제입니다. 이분 그래프 매칭은 네트워크 플로우, 작업 할당 문제, 매칭 문제 등 다양한 응용 분야에서 사용됩니다.Hopcroft-Karp 알고리즘Hopcroft-Karp 알고리즘은 이분 그래프에서 최대 매칭을 찾는 효율적인 알고리즘입니다. 이 알고리즘은 BFS와 DFS를 결합하여 구현됩니다.Hopcroft-Karp 알고리즘의 시간 복잡도:(O(\sqrt{V}E)), 여기서 (V)는 정점의 수, (E)는 간선의 수입니다.Hopcroft-Karp 알고리즘 구현다음은 C++로 Hopcroft-Karp 알고리즘을 구현한 예제입니다. 그래프 클래스 정의#includ.. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조 ] Day 10: 트라이 (Trie) 트라이 (Trie)트라이는 문자열을 효율적으로 저장하고 검색하기 위한 트리 기반 자료구조입니다. 트라이는 주로 문자열 집합의 검색, 삽입, 삭제에 사용되며, 접두사 검색에 매우 효율적입니다.트라이의 특징:노드 구조: 각 노드는 문자와 자식 노드를 가집니다.루트 노드: 루트 노드는 빈 문자열을 나타냅니다.경로: 문자열은 루트 노드에서 시작하여 각 문자에 해당하는 노드를 따라 내려가면서 표현됩니다.접두사 검색: 공통 접두사를 가진 문자열을 효율적으로 검색할 수 있습니다.트라이 구현TrieNode.h#ifndef TRIENODE_H#define TRIENODE_H#include // 트라이의 노드 구조체struct TrieNode { std::unordered_map children; // 자식 노드를 .. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조 심화] Day 10: 위상 정렬 (Topological Sorting) 위상 정렬 (Topological Sorting)위상 정렬은 유향 비순환 그래프(DAG, Directed Acyclic Graph)의 정점을 순서대로 나열하는 방법입니다. 이 순서는 모든 간선 (u, v)에 대해 정점 u가 정점 v보다 먼저 나오는 순서를 의미합니다. 위상 정렬은 주로 작업 스케줄링, 컴파일러에서의 심볼 테이블 생성 등에 사용됩니다.위상 정렬의 주요 특징DAG: 위상 정렬은 반드시 유향 비순환 그래프에서만 가능합니다.순서: 정점 u에서 정점 v로 가는 모든 경로에 대해 정점 u는 정점 v보다 먼저 나옵니다.위상 정렬의 구현 방법Kahn's Algorithm: 진입 차수를 이용한 위상 정렬DFS 기반 알고리즘: 깊이 우선 탐색을 이용한 위상 정렬Kahn's AlgorithmKahn's Al.. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조] Day 11: 그래프의 기본 개념 그래프 (Graph)그래프는 노드(정점, Vertex)와 간선(Edge)으로 구성된 자료구조로, 여러 노드가 간선으로 연결된 형태를 가집니다. 그래프는 다양한 문제를 모델링하고 해결하는 데 사용됩니다.그래프의 구성 요소:노드 (Vertex): 그래프의 개별 요소입니다.간선 (Edge): 노드 간의 연결을 나타냅니다.그래프의 종류:방향 그래프 (Directed Graph): 간선이 방향을 가지는 그래프입니다.무방향 그래프 (Undirected Graph): 간선이 방향을 가지지 않는 그래프입니다.가중치 그래프 (Weighted Graph): 간선에 가중치가 있는 그래프입니다.비가중치 그래프 (Unweighted Graph): 간선에 가중치가 없는 그래프입니다.그래프의 표현 방법그래프는 다음과 같은 방법으로.. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조 심화] Day 11: 강한 연결 요소 (Kosaraju, Tarjan 알고리즘) 강한 연결 요소 (Strongly Connected Components, SCC)강한 연결 요소(SCC)는 방향 그래프에서 각 정점이 서로 도달 가능한 최대 부분 그래프입니다. 즉, SCC의 모든 정점 u, v에 대해 u에서 v로 가는 경로와 v에서 u로 가는 경로가 모두 존재합니다.Kosaraju's AlgorithmKosaraju's Algorithm은 그래프를 두 번의 DFS로 탐색하여 SCC를 찾는 알고리즘입니다.Kosaraju's Algorithm의 단계:DFS: 원본 그래프에서 DFS를 수행하여 정점을 완료된 순서대로 스택에 저장합니다.전치 그래프 생성: 모든 간선의 방향을 반전시킨 그래프를 만듭니다.DFS: 스택에서 정점을 꺼내어 전치 그래프에서 DFS를 수행합니다.Kosaraju's Alg.. 2024. 8. 1. 이전 1 2 3 4 5 6 7 8 9 다음 반응형
