자료구조 & 알고리즘10 [3] 좌표 압축 (Coordinate-Compression) 좌표 압축은 PS에서 정말 많이 쓰이는 테크닉으로, 세그트리 같이 구간 쿼리를 해결하기 위해 많이 사용한다. 세그트리는 주어진 범위의 모든 영역을 Leaf node로 사용하기 때문에, 해당 범위가 커지면 좌표 압축이 필요하다. 결국 좌표 압축은, 해당 좌표를 0,1,2 ~ 의 값으로 치환하는 것인데, 그 자체는 매우 어렵고 이해가 되지 않는 개념은 아니다. for (int i = 0; i > comp[i]; v.push_back(comp[i]); } sort(v.begin(), v.end()); v.resize(unique(v.begin(), v.end()) - v.begin()); for (int i = 0; i < n; i++) { comp[i] = lower_bound.. 2020. 9. 28. [2] Segment Tree (Lazy Propagation) Lazy-Segment Tree는 기본 세그먼트 트리에 구간에 대한 업데이트를 적용하는 쿼리에 적합한 자료구조이다. 기존 Segment Tree는 매 Update 쿼리마다 Tree의 Leaf node까지 가서 업데이트를 적용하지만 구간에 대해 업데이트가 필요한 경우엔, 그걸 일일이 다 바꿔주는 것이 비효율적이다. 해당 구간을 나중에 조회하지 않을 수도 있기 때문이다. 그럼 해당 구간을 언제 업데이트해줘야 하나? 물론 그 구간을 조회하거나 업데이트 해야 할 때 이다. 그때 아니면 굳이 밑으로 내려갈 필요가 없다. 해당 구간에 업데이트해야 할 값을 배열로 가지고 있고 (segtree와 동일한 배열) 해당 지점을 update 혹은 find로 접근할 때 propagation을 해준다. Propagation vo.. 2020. 9. 28. 페르마의 소정리 $ p $가 소수일때, 임의의 정수 a에 대해서 $ a^p - a $는 p의 배수이다. 이를 모듈러 연산으로 표현하면 다음과 같다. $ a^p \equiv a \pmod p $ 괄호 안의 의미는 양 변에 mod p 가 생략되었다는 뜻이다. 예를 들어, a = 3 이고 p = 7이면 $ 3^7 = 2187 - 3 = 2184 mod 7 = 0 $ 을 성립한다. 만약 a가 p로 나누어지지 않으면, 양변을 a로 나누어 동치인 식을 만들 수 있다. $ a^{p-1} \equiv 1 \pmod p $ 위 성질을 이용해서 임의의 x에 대해서 다음과 같이 일반화할 수 있다. $ a^x \equiv a^{x \mod (p-1)} \pmod p $ 이 성질을 이용해서 나머지를 매우 빠르고 쉽게 구할 수 있다. 예제 ww.. 2020. 9. 20. [1] Segment Tree Segment Tree 는 다양한 유형의 문제를 빠르게 해결해주는 자료구조이다. 구간에 대한 정보를 구하는 경우, 단순히 정렬한 후 Prefix Sum 을 이용해서 구간합을 빠르게 구할 수 있지만 만약 개별 쿼리 도중 배열에서 특정 요소의 값이 변경되야 하는 경우엔 매번 다시 정렬을 해야 되어 비효율적이다. 이러한 경우, 구간에 대한 정보를 담는 Tree를 구성할 수 있는데, 이를 세그먼트 트리라고 한다. 세그먼트 트리는 기본적으로 Complete Binary Tree이고, 모든 Element에 대한 정보가 트리의 Leaf Node에 포함된다. 그리고 그 위 node들은, 자식 node를 포함하는 구간에 대한 정보를 담는 것이다. 간단하게, 세그멘트 트리를 이용해서 구간합을 구하는 코드의 예시를 보자. .. 2020. 9. 13. 이전 1 2 3 다음
