본문 바로가기

알고리즘/자료구조

알고리즘/자료구조 2021. 8. 2. 세그먼트 트리 응용 세그먼트 트리는 쓰임새가 무궁무진합니다. 응용하여 쓸 수 있는 방법들을 몇가지 알아봅시다. 세그먼트 트리의 각 노드에는 구간의 연산 값 하나 뿐만이 아니라, 여러개의 값 또는 상태를 저장할 수도 있습니다. 아무튼 서로 다른 두 상태를 merge할 수 있고 결합법칙이 성립한다면 그것을 이용해 세그먼트 트리를 만들 수 있고, 갱신과 구간 값을 빠르게 얻어낼 수 있습니다. https://www.acmicpc.net/problem/17408 17408번: 수열과 쿼리 24 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오 1 i v: Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 l r: l ≤ i > i >> v; update(..
알고리즘/자료구조 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. 4. 유니온 파인드 (Union-Find) 유니온 파인드 (Union-Find Disjoint Set)은 교집합이 없는 서로소 집합들을 다루는 자료구조입니다. 유니온 파인드를 이용하면 서로소 집합들을 서로 합치거나(Union), 특정 원소가 어떤 집합에 속해있는지(Find) 알아내는 연산을 매우 효율적으로 할 수 있습니다. 유니온 파인드에서의 한 집합은 하나의 대표값(원소)로 표시하며, 그 집합에 포함된 다른 원소들은 대표원소로 가는 경로가 존재하는 트리 형태로 저장되게 됩니다. 예를 들어봅시다. 초기에 모든 원소들은 자기 자신을 대표원소로 가지는 크기 1인 집합에 속해 있습니다. $$\{1\},\{2\},\{3\},\{4\},\{5\},\{6\}$$ 여기에서 2번 집합과 3번 집합을 합치는 연산을 해봅시다. 합칠 때는 두 집합의 대표값중 하나를..
알고리즘/자료구조 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...

티스토리툴바