본문 바로가기

알고리즘

알고리즘/자료구조 2020. 6. 1. 세그먼트 트리 with Lazy propagation 저번 글에서 점 갱신과 구간 연산을 \(O(\log n)\)에 처리할 수 있는 자료구조인 세그먼트 트리에 대해 알아봤습니다. 이번엔 구간 갱신까지 \(O(\log n)\)에 처리하게 해주는 Lazy propagation에 대해 알아봅시다. Lazy propagation을 하기 앞서, 다음 문제를 풀어봅시다. https://www.acmicpc.net/problem/16975 16975번: 수열과 쿼리 21 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i j k: Ai, Ai+1, ..., Aj에 k를 더한다. 2 x: Ax 를 출력한다. www.acmicpc.net 이 문제처럼 구간 갱신이 필요하지만, 구간에 대한 연산결과가 아닌 한 ..
알고리즘/자료구조 2020. 5. 15. 세그먼트 트리 세그먼트 트리 (Segment Tree)는 동적인 구간 질의를 효율적으로 처리할 수 있는 자료구조입니다. 예를 들어, 어떤 배열의 구간 \([l, r]\)의 원소 중 최소값을 알아내거나 구간 전체를 한꺼번에 갱신하는 등의 연산을 빠르게 할 수 있게 됩니다. https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄�� www.acmicpc.net 최대 \(10^6\)개의 원소로 이루어진 배열이 있습니다. 최대 \(20000\..
알고리즘/그래프 2020. 5. 11. 최소 공통 조상 최소 공통 조상(Least Common Ancestor, LCA)는 트리에 있는 정점 \(u, v\)에 대해, \(u\)와 \(v\)의 공통 조상 중 가장 가까운 것을 말합니다. 예를 들어 아래와 같은 트리에서, 2번 정점과 7번 정점의 LCA는 1번 정점, 9번 정점과 4번 정점의 LCA는 2번 정점입니다. 그러면 LCA를 구하는 알고리즘에 대해 알아봅시다. 1. \(O(n)\) Navie https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다. www.a..
알고리즘/그래프 2020. 5. 10. 위상 정렬 위상 정렬(Topological sorting)은 유향 그래프의 정점들을 변의 방향을 거스르지 않도록 나열하는 것을 말합니다. 쉽게 말해서 간선 \(u \rightarrow v\)가 있다면, 정점 \(v\)는 무조건 정점 \(u\)이후에 등장해야 합니다. 예를 들어 다음과 같은 유향 그래프에서, $$\{1, 5, 2, 3, 6, 4\}$$ 는 가능한 위상 정렬 중 하나입니다. 방향 그래프에 사이클이 존재한다면, 위상 정렬 역시 존재할 수 없습니다. 따라서 그래프는 항상 '사이클 없는 유향그래프'(Directed Acyclic Graph, DAG)여야 합니다. 그러면 위상 정렬을 구하는 알고리즘에 대해 알아봅시다. https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫..
알고리즘/그래프 2020. 5. 5. 최소 스패닝 트리 우선 '최소 스패닝 트리'가 무엇을 뜻하는 단어인지 먼저 알아봅시다. 우선 '트리'란, 사이클을 갖지 않는 연결 그래프를 뜻합니다. 정점이 \(V\)개인 트리는 \(V-1\)개의 간선으로 모두 연결되어 있게 됩니다. '그래프의 스패닝 트리'는, 그래프에서 일부의 간선을 선택해 만든 트리를 뜻합니다. 따라서 이 연결 그래프는 다음과 같은 스패닝 트리를 가질 수 있게 됩니다. 물론 위 2가지의 형태가 아닌 다른 형태의 스패닝 트리도 존재합니다. '그래프의 최소 스패닝 트리'는, 가중치가 있는 연결 그래프에서 간선의 가중치의 합이 가장 작은 스패닝 트리를 말합니다. 따라서 이 연결 그래프의 최소 스패닝 트리는 이런 형태가 됩니다. 가중치의 합은 17로, 가중치의 합이 이보다 작은 스패닝 트리는 만들 수 없습니..
알고리즘/자료구조 2020. 5. 4. 유니온 파인드 (Union-Find) 유니온 파인드 (Union-Find Disjoint Set)은 교집합이 없는 서로소 집합들을 다루는 자료구조입니다. 유니온 파인드를 이용하면 서로소 집합들을 서로 합치거나(Union), 특정 원소가 어떤 집합에 속해있는지(Find) 알아내는 연산을 매우 효율적으로 할 수 있습니다. 유니온 파인드에서의 한 집합은 하나의 대표값(원소)로 표시하며, 그 집합에 포함된 다른 원소들은 대표원소로 가는 경로가 존재하는 트리 형태로 저장되게 됩니다. 예를 들어봅시다. 초기에 모든 원소들은 자기 자신을 대표원소로 가지는 크기 1인 집합에 속해 있습니다. $$\{1\},\{2\},\{3\},\{4\},\{5\},\{6\}$$ 여기에서 2번 집합과 3번 집합을 합치는 연산을 해봅시다. 합칠 때는 두 집합의 대표값중 하나를..
알고리즘/그래프 2020. 4. 29. 최단 경로 그래프에서 두 정점 사이의 최단 경로를 구하는 알고리즘에 대해 알아봅시다. BFS 간선의 가중치가 모두 1이라면(같다면), BFS를 이용해 한 정점에서 다른 정점들 사이의 최단 거리를 알 수 있습니다. 자세한 설명은 https://anz1217.tistory.com/21 그래프 탐색 (DFS, BFS) 그래프는 정점과 정점들을 잇는 간선들의 집합으로 이루어진 자료구조입니다. 이 글에서는 그래프를 저장하는 방법과, 그래프를 탐색하는 방법에 대해 알아보도록 합시다. 다음과 같은 그래프를 저장한다고 생각해.. anz1217.tistory.com 에서 볼 수 있습니다. 시간 복잡도는 \(O(|V|+|E|)\)입니다. 0-1 BFS 문제를 조금 확장해 봅시다. 간선의 가중치가 모두 0또는 1이라면 어떻게 최단 거..
알고리즘/자료구조 2020. 4. 28. 내장 라이브러리가 있는 자료 구조 C++은 프로그램에 필요한 자료구조와 알고리즘을 STL(Standard Template Library)로서 제공합니다. 이 글에서는 C++ STL에 내장된 자료구조가 어떤 것들이 있는지 간단하게 언급하고 넘어가려고 합니다. 기본적인 자료구조 자체에 대한 설명은 하지 않습니다. 1. 정적 배열 (array) 1 2 3 4 5 6 7 8 #include using namespace std; int main() { int a[100]; // 정적 배열 array b; // 함수로 전달할 때 포인터 형 변환이 되지 않는 정적 배열 } 2. 동적 배열 (vector) 1 2 3 4 5 6 7 #include using namespace std; int main() { vector vec; // 동적 배열 } 3...

티스토리툴바