반응형 [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. [C++로 배우는 알고리즘과 자료구조 심화] Day 8: 최소 신장 트리 (Minimum Spanning Tree) 심화 최소 신장 트리 (Minimum Spanning Tree, MST)최소 신장 트리(MST)는 가중치가 있는 연결된 무향 그래프에서 모든 정점을 포함하며, 간선의 가중치 합이 최소가 되는 트리입니다. MST를 찾는 대표적인 알고리즘으로는 크루스칼 알고리즘(Kruskal's Algorithm)과 프림 알고리즘(Prim's Algorithm)이 있습니다.크루스칼 알고리즘 (Kruskal's Algorithm)크루스칼 알고리즘은 간선을 가중치의 오름차순으로 정렬한 후, 사이클을 형성하지 않는 간선을 선택하여 MST를 구성하는 알고리즘입니다.크루스칼 알고리즘의 시간 복잡도:(O(E \log E + E \log V)), 여기서 (E)는 간선의 수, (V)는 정점의 수입니다.프림 알고리즘 (Prim's Algorit.. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조 심화] Day 9: 최단 경로 알고리즘 심화 (벨만-포드, 존슨 알고리즘) 최단 경로 알고리즘최단 경로 알고리즘은 가중치 그래프에서 주어진 두 정점 간의 최단 경로를 찾는 알고리즘입니다. 대표적인 알고리즘으로는 다익스트라 알고리즘(Dijkstra's Algorithm), 벨만-포드 알고리즘(Bellman-Ford Algorithm), 그리고 존슨 알고리즘(Johnson's Algorithm)이 있습니다.오늘은 벨만-포드 알고리즘과 존슨 알고리즘에 대해 심화 학습하겠습니다.벨만-포드 알고리즘 (Bellman-Ford Algorithm)벨만-포드 알고리즘은 음의 가중치가 있는 그래프에서 최단 경로를 찾을 수 있는 알고리즘입니다. 그러나 음의 사이클이 있는 경우에는 사용할 수 없습니다.벨만-포드 알고리즘의 시간 복잡도:(O(VE)), 여기서 (V)는 정점의 수, (E)는 간선의 수입.. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조 심화] Day 6: 스플레이 트리 (Splay Tree) 스플레이 트리 (Splay Tree)스플레이 트리는 자가 조정 이진 탐색 트리입니다. 각 연산 후, 스플레이 연산을 통해 접근한 노드를 트리의 루트로 이동시킵니다. 이는 자주 접근하는 노드를 트리의 상위로 올려, 평균적으로 빠른 접근을 가능하게 합니다.스플레이 트리의 주요 특징자가 조정: 각 연산 후 접근한 노드를 루트로 이동시키는 스플레이 연산을 수행합니다.평균 시간 복잡도: (O(\log n)) (최악의 경우 시간 복잡도: (O(n)))회전 연산: 좌회전, 우회전, 좌-좌 회전, 우-우 회전, 좌-우 회전, 우-좌 회전을 포함한 회전 연산을 사용합니다.스플레이 트리의 기본 연산삽입 (Insert): 새로운 노드를 삽입하고 스플레이 연산을 수행합니다.삭제 (Delete): 특정 키를 가진 노드를 삭제하.. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조 심화] Day 7: 스킵 리스트 (Skip List) 스킵 리스트 (Skip List)스킵 리스트는 연결 리스트에 인덱스를 추가하여 검색, 삽입, 삭제 연산의 시간 복잡도를 (O(\log n))으로 개선한 자료구조입니다. 여러 레벨로 구성된 연결 리스트로, 각 레벨마다 원소를 건너뛰어가며 검색할 수 있습니다. 이는 균형 이진 탐색 트리와 유사한 시간 복잡도를 가지면서도 구현이 간단합니다.스킵 리스트의 주요 특징시간 복잡도:평균: (O(\log n))최악의 경우: (O(n))레벨 구조: 여러 레벨의 리스트로 구성되며, 각 레벨은 원소를 건너뛰어가며 검색할 수 있도록 합니다.확률적 균형 유지: 랜덤하게 레벨을 선택하여 원소를 삽입함으로써 확률적으로 균형을 유지합니다.스킵 리스트의 기본 연산삽입 (Insert): 새로운 원소를 삽입하고 레벨을 랜덤하게 결정합니다.. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조 심화] Day 5: 균형 이진 탐색 트리 (AVL 트리, Red-Black 트리) 균형 이진 탐색 트리 (AVL 트리)AVL 트리는 자가 균형 이진 탐색 트리로, 각 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하가 되도록 유지합니다. 이는 트리의 균형을 유지하여 탐색, 삽입, 삭제 연산의 시간 복잡도가 (O(\log n))이 되도록 합니다.AVL 트리의 주요 특징균형 조건: 각 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하가 되도록 유지합니다.회전 연산: 삽입 및 삭제 후 균형을 유지하기 위해 회전 연산을 사용합니다.AVL 트리의 기본 연산삽입 (Insert): 새로운 노드를 삽입한 후 균형을 유지합니다.삭제 (Delete): 특정 키를 가진 노드를 삭제한 후 균형을 유지합니다.검색 (Search): 특정 키를 가진 노드를 검색합니다.AVL 트리의 구현.. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조 심화] Day 3: 펜윅 트리 (Fenwick Tree, Binary Indexed Tree) 펜윅 트리 (Fenwick Tree, Binary Indexed Tree)펜윅 트리(BIT, Fenwick Tree)는 배열의 구간 합을 효율적으로 계산하고 업데이트할 수 있는 자료구조입니다. 세그먼트 트리와 유사하지만, 구현이 더 간단하고 메모리 사용량이 적습니다.펜윅 트리의 주요 특징시간 복잡도:업데이트: (O(\log n))쿼리: (O(\log n))구현 방법:트리의 각 노드는 배열의 특정 구간에 대한 정보를 저장합니다.이진수의 비트 연산을 활용하여 구간을 관리합니다.펜윅 트리의 기본 연산업데이트 (Update): 특정 인덱스의 값을 업데이트합니다.쿼리 (Query): 특정 인덱스까지의 구간 합을 계산합니다.펜윅 트리의 구현다음은 C++로 펜윅 트리를 구현한 예제입니다. 구간 합을 구하고 구간 값을.. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조 심화] Day 4: 이면 탐색 트리 (Treap) 이면 탐색 트리 (Treap)이면 탐색 트리(Treap)는 이진 탐색 트리(BST)와 힙(Heap)의 특성을 동시에 가지는 자료구조입니다. 각 노드는 키(key)와 우선순위(priority)를 가지며, 다음 두 가지 성질을 만족합니다:이진 탐색 트리 성질: 키의 값에 대해 이진 탐색 트리 성질을 만족합니다.힙 성질: 우선순위에 대해 최대 힙 또는 최소 힙 성질을 만족합니다.트라이의 주요 특징삽입, 삭제, 검색:평균 시간 복잡도: (O(\log n))최악의 경우 시간 복잡도: (O(n))회전 연산:이중회전을 통해 트리의 균형을 유지합니다.트라이의 기본 연산삽입 (Insert): 새로운 노드를 삽입합니다.삭제 (Delete): 특정 키를 가진 노드를 삭제합니다.검색 (Search): 특정 키를 가진 노드를 .. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조 심화] Day 2: 세그먼트 트리 (Segment Tree) 세그먼트 트리 (Segment Tree)세그먼트 트리는 주어진 배열의 구간에 대한 정보를 효율적으로 저장하고 쿼리를 처리하기 위해 사용하는 트리 구조입니다. 세그먼트 트리는 다음과 같은 연산을 빠르게 수행할 수 있습니다:구간 합: 배열의 특정 범위에 대한 합을 구합니다.구간 최솟값/최댓값: 배열의 특정 범위에 대한 최솟값 또는 최댓값을 구합니다.구간 갱신: 배열의 특정 범위에 값을 갱신합니다.세그먼트 트리의 주요 특징시간 복잡도:빌드: (O(n))쿼리: (O(\log n))업데이트: (O(\log n))구현 방법:트리의 각 노드는 배열의 특정 구간을 나타냅니다.루트 노드는 전체 배열을 나타내고, 각 자식 노드는 배열의 절반 구간을 나타냅니다.세그먼트 트리의 기본 연산트리 빌드: 초기 배열을 기반으로 세그.. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조 심화] Day 1: 트라이(Trie) 자료구조와 문자열 검색 트라이(Trie) 자료구조 소개트라이(Trie)는 문자열 또는 단어의 집합을 저장하고 효율적으로 검색하기 위한 트리 기반의 자료구조입니다. 주로 문자열 검색, 자동 완성, 사전 구현 등에 사용됩니다. 트라이는 각 노드가 문자 하나를 나타내며, 루트 노드에서 시작하여 각 문자를 따라가면서 단어를 구성합니다.트라이의 주요 특징빠른 검색: 문자열의 길이에 비례하는 시간 복잡도 (O(L))에서 검색이 가능합니다. 여기서 (L)은 문자열의 길이입니다.공유 구조: 공통 접두사를 가지는 문자열을 공유하여 공간을 절약합니다.삽입과 검색의 단순함: 삽입과 검색 연산이 단순하고 직관적입니다.트라이의 기본 연산삽입 (Insert): 문자열을 트라이에 삽입합니다.검색 (Search): 문자열이 트라이에 존재하는지 확인합니다... 2024. 8. 1. 이전 1 2 3 4 다음 반응형
