개발일지

개념 Segment Tree에서 구간의 Update를 빠르게 처리하기 위한 방법이다. Segment Tree에서 Update의 시간 복잡도는 O(logN)이기 때문에 구간의 길이가 L인 Update의 시간 복잡도는 O(LlogN)이기 때문에 쿼리의 수가 많은 경우 시간초과를 받을 수 있다. Lazy Segment Tree는 Update를 필요한 시기에 Update하도록 미루면서 Range Update를 O(logN)으로 수행할 수 있다. 작동원리 구간을 Update할 경우 Segment Tree에서 참조하는 Node만 Update를 진행하고, 자식 노드의 Update는 Lazy Tree에 기록하여 Update를 미룬다. 시간 복잡도 init : O(NlogN) update : O(logN) update_..

개념 각 노드에 구간의 정보를 저장하여 Query, Update를 빠르게 처리할 수 트리다. 작동원리 트리로 구간의 정보를 저장하여 최악의 경우 트리의 높이만큼 트리를 탐색하여 Query와 Update를 수행할 수 있다. 트리의 성질 왼쪽 자식노드 : index * 2 오른쪽 자식노드 : index * 2 + 1 Query 참조하는 범위가 구간을 완전히 벗어나면 0을 Return한다. 참조하는 범위가 구간에 완전히 겹치면 Tree에 저장된 값을 Return한다. 참조하는 범위가 구간에 걸치면 Tree에 더 깊은 Level을 참조한다. 3-6 구간의 정보를 얻으려면 5, 6을 참조한다. 1-7 구간의 정보를 얻으려면 2, 6, 14를 참조한다. 1-8 구간의 정보를 얻으려면 1을 참조한다. Update 참..

개념 각 인덱스는 최하위 비트의 값만큼 구간을 저장하고 이를 이용하여 구간의 합을 빠르게 찾을 수 있다. => 1, 3, 5, 7은 최하위 비트의 값이 1 -> 구간의 길이가 1만큼의 합을 저장 => 2, 6은 최하위 비트의 값이 2 -> 구간의 길이가 2만큼의 합을 저장 => 4는 최하위 비트의 값이 4 -> 구간의 길이가 4만큼의 합을 저장 => 8은 최하위 비트의 값이 8 -> 구간의 길이가 8만큼 합을 저장 작동원리 최하위 비트를 구하는 법 index & -index Query 1-3 구간의 합을 구하면 트리에서 2, 3을 더한다. 3(0011)에 저장된 값을 더하고 최하위 비트(0001)를 뺀다. => 2(0010) 2(0010)에 저장된 값을 더하고 최하위 비트(0010)를 뺀다. => 0(0..

행렬의 곱셈 크기가 A * B인 X 행렬과 크기가 B * C인 행렬 Y의 곱의 결과 Z는 A * C의 행렬이다. (A의 열의 개수와 B의 행의 개수는 같아야 한다.) C 행렬의 (i, j)는 A의 i행의 성분 * B의 j열의 성분의 합이다. 곱셈의 항등원 (단위행렬 : Unit Matrix) 왼쪽 위에서 오른쪽 아래로 (↘) 1인 행렬이다. 기호 E 시간 복잡도 N1*M 행렬과 M*N2 행렬의 시간 복잡도는 O(N1 * N2 * M) 코드 vector operator*=(vector &x, vector const &y) { vector result(x.size(), vector(y.front().size(), 0L)); for (int i = 0;i < x.size();++i) { for (int j =..

개념 서로 같은 집합에 속해있는지 확인하고 같은 집합으로 합치거나 집합의 포함된 원소의 수를 알아내는 알고리즘이다. union => 두 원소 a, b가 있을 때 a가 속한 집합과 b가 속한 집합을 합치는 연산 find => 원소 a가 있을 때 a가 속한 집합을 찾는 연산 작동원리 초기화 1. 배열을 -1로 초기화한다. (음수의 절대값이 해당 집합에 속안 원소의 갯수가 된다.) find 1. 재귀호출을 통해 배열에 저장된 값이 음수일 때 까지 찾는다 (배열에 저장된 값이 양수면 해당 원소의 부모 원소이고, 음수면 해당 집합의 최고 위치에 있는 인덱스이다.) 2. 배열에 저장된 값이 음수이면 해당 인덱스를 반환한다. union 1. 두 원소의 속한 집합을 find연산으로 찾는다. 2. 두 원소가 속한 집합이..

개념 탐색 범위를 반으로 줄이면서 값을 찾는 방법이다. 작동원리 1. 탐색 범위를 정렬한다. 2. l -> 탐색 범위 최소값, r -> 탐색 범위 최대값, m -> 탐색 범위 중간값 3. m에 찾으려는 위치가 있는지 확인한다. 4. m에 찾는 값보다 큰 값이 존재하면 r을 m - 1로 바꾼다. ( 정렬되어있기 때문에 m보다 큰 인덱스에 저장된 값은 m에 저장된 값보다 크기 때문에 확인할 필요가 없다.) 5. m에 찾는 값보다 작은 값이 존재하면 l을 m + 1로 바꾼다. (정렬되어있기 때문에 l보다 작은 인덱스에 저장된 값은 m에 저장된 값보다 작기 때문에 확인할 필요가 없다.) 6. l > n >> k; vector ve(n); for (auto &i : ve) { cin >> i; } long lon..

개념 유량이 있는 그래프에서 얼마나 많은 유량을 보낼 수 있는지 확인하는 알고리즘 유량(Flow) : 두 정점 사이에서 흐르는 유량 용량(Capacity) : 두 정점 사이에서 최대로 흐를 수 있는 유량 소스(Source) : 유량이 시작되는 정점 싱크(Sink) : 유량이 도착하는 정점 용량 제한 속성 (Flow 유량은 용량을 넘을 수 없다. 유량의 대칭성 A -> B로 10이 흘렀으면, B -> A로 다시 10을 보낼 수 있다. => 유량을 보낼 경로를 찾을 때 보통 BFS를 사용하고 BFS는 우선순위를 고려하지 않고 경로를 찾게 된다. 이럴 때 최대로 흐르는 경로가 아닌 다른 경로를 선택하는 문제를 해결할 때 필요한 개념이다. 작동원리 1. 유량 그래프를 모델링한다 => 역방향 간선도 필수적으로 추..

개념 그래프 G에서 정접들의 집합을 S라고 할 때 S의 부분 집합 'S를 골랐을 때 서로 인접하지 않으면 독립 집합이라 하고 이중에서 'S의 크기가 가장 큰 독립집합을 최대 독립집합이라고 한다. Maximum Independent Set의 특징은 Maximum Independent Set의 여집합은 Minimum Vertex Cover이다. => 최대 집합 - Minimum Vertex Cover = 최대 독립 집합 => 최대 집합 - 최대 이분 매칭 = 최대 독립 집합이다 시간복잡도 이분매칭 할 때 : O(V^(1/2) * E) 문제 11014 컨닝2 www.acmicpc.net/problem/11014 11014번: 컨닝 2 최백준은 서강대학교에서 “컨닝의 기술”이라는 과목을 가르치고 있다. 이 과목..