CP Algorithm & Knowledge (30) 썸네일형 리스트형 imos법 imos method いもす法 이 게시글에서는 imos법에 대해 배우고 관련 문제를 푼다. imos법이란? 이름의 유래는 작성자도 잘 알지 못하지만 일본에서 온 것으로 추정된다. imos법은 다음과 같은 형태를 가진 문제를 풀 때 사용할 수 있다. N차원 직교 좌표계에서 특정 범위(구간)에 x를 더하기 위와 같은 쿼리가 연속으로 주어질 때 imos법을 사용하면 일부 좌표를 마킹하여 d차원일 때 $O(N^{d})$의 시간 복잡도로 공간을 채울 수 있다. 선분에서의 imos법 특정 구간에 1을 더하길 원한다고 해보자. imos법은 구간이 시작되는 점에 1을 더하고 구간을 벗어나는 가장 첫 번째 점에 1을 뺀 뒤 이 사이를 누적합으로 더해가며 스위핑 한다. 위에서 말한 대로 스위핑을 하면 해당 구간에 1을 더한 결과를 얻을 수 있다. 1부.. 오일러 투어(Euler Tour) 응용 feat. 2820 자동차 공장 https://nicotina04.tistory.com/157 오일러 투어(Euler Tour) 기초 오일러 투어? 오일러 투어는 트리에서 백트래킹을 할 때 그 흔적을 남기는 순회로 볼 수 있다. 오일러 트리를 이용하면 DFS를 하면서 몇 번째 이동에 어떤 정점에 머무르는지, 어떤 부모 노드의 nicotina04.tistory.com 이 게시글에서는 전에 다루었던 오일러 투어를 응용하여 풀 수 있는 문제를 풀어본다. https://www.acmicpc.net/problem/2820 2820번: 자동차 공장 상근이는 자동차를 매우 좋아한다. 자동차 공장에 취직한 상근이는 계속된 승진 끝에 드디어 사장이 되었다. 공장에는 총 N명의 직원이 있다. 상근이를 제외한 모든 직원은 한 명의 상사가 있다. www.a.. 오일러 투어(Euler Tour) 기초 오일러 투어? 오일러 투어는 트리에서 백트래킹을 할 때 그 흔적을 남기는 순회로 볼 수 있다. 오일러 트리를 이용하면 DFS를 하면서 몇 번째 이동에 어떤 정점에 머무르는지, 어떤 부모 노드의 자식 중 가장 큰 번호가 무엇인지, 그리고 해당 정점이 어느 시점에 처음으로 방문되고 어느 시점에 마지막으로 방문되는지 파악할 수 있다. 오일러 투어로 무엇을 하려는지에 따라 그 구현이 달라지므로 위 경우들에 대한 구현을 소개한다. 1. x번째 이동에 도착한 정점 다음 코드는 DFS를 할 때 특정 시점에 방문한 노드를 기록한다. vector footprint; vector tree[100001]; bool discovered[100001]; void euler_tour(int node) { footprint.pus.. 오일러의 체(Linear Sieve)로 O(logn) 소인수 분해 하기 이 게시글에서는 linear sieve 또는 오일러의 체라 불리는 알고리즘에 대해 알아보고 그 구현을 배우도록 한다. Linear Sieve Linear sieve는 에라토스테네스의 체를 개선하여 N 이하의 소수를 $O(N)$ 만에 찾고 N 이하 자연수의 소인수 분해를 $O(\log N)$에 할 수 있게 만들어 준다. 과정은 다음과 같다. 소수의 여부 대신 해당 수의 최소 소인수(Smallest Prime Factor. 이하 spf)를 나타내는 체(배열)를 둔다. spf 체를 순회하면서 해당 index의 값이 비어있는(0) 경우 소수가 된다. 그래서 spf[index] = index가 되고 index를 소수 집합에 추가한다. 그런 다음 현재까지 판별한 모든 소수들에 대해 반복문을 돌면서 spf[index.. 그래프에서 DFS로 사이클 찾기 이 게시글에서는 유향 그래프에서 사이클을 찾는 방법을 알아본다. 왜 유향 그래프라 했냐면 무향 그래프에는 별도의 정의가 있지 않는 한 서로를 왕복할 수만 있으면 사이클이 존재하는 것이기 때문이다. DFS 스패닝 트리와 간선 분류 어떤 그래프를 DFS로 탐색했을 때 지나간 엣지만을 남겨놓으면 트리 형태가 되는데 이를 DFS 스패닝 트리라고 한다. 어떤 그래프를 DFS 스패닝 트리로 변환했을 때 그래프의 모든 엣지를 4가지로 분류할 수 있다. Tree edge (트리 간선) 트리 간선은 DFS 스패닝 트리에 속하는 간선이다. 즉, DFS를 하면서 거쳐간 간선이다. Forward edge (순방향 간선) DFS를 통해 어떤 연결된 두 노드 사이의 부모 자식 관계를 정립할 수 있지만 DFS 스패닝 트리에서 트리.. 이전 1 2 3 4 5 6 다음
