개발일지

개념 각 인덱스는 최하위 비트의 값만큼 구간을 저장하고 이를 이용하여 구간의 합을 빠르게 찾을 수 있다. => 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 최백준은 서강대학교에서 “컨닝의 기술”이라는 과목을 가르치고 있다. 이 과목..

개념 그래프 G에서 정점들의 집합을 S라고 할 때 S의 부분집합 'S로 모든 간선을 포함하면 이를 Vertex Cover라고 한다. Minimum Vertex Cover는 NP지만 이분 그래프에서 Minimun Vertex Cover는 최대 매칭과 동치이다. 작동 원리 콰닉의 정리 Kőnig's theorem (graph theory) - Wikipedia An example of a bipartite graph, with a maximum matching (blue) and minimum vertex cover (red) both of size six. In the mathematical area of graph theory, Kőnig's theorem, proved by Dénes Kőnig (19..

개념 Short Path Faster Algorithm의 약어로 가장 빠른 경로를 찾는 알고리즘이다. 다익스트라 알고리즘은 음수인 간선이 존재할 때 사용할 수 없고, 벨만-포드 알고리즘보다 효율이 좋기 때문에 MCMF 알고리즘에서 많이 사용한다. 작동원리 isIn => 덱에 해당 정점이 있는지 확인하는 배열, 큐에 중복으로 값을 넣는 것을 방지 count => 업데이트된 횟수를 저장하는 배열, CYCLE을 확인할 수 있다.(벨만-포드와 같은 개념) 1. 시작 정점을 덱에 넣고 count, isIn, distance를 업데이트한다. 2. 덱에서 POP FRONT하고 isIn을 false로 업데이트한다. 3. 현재 정점에서 갈 수 있는 정점중 distance를 업데이트 할 수 있는 정점이 있으면 distan..