MO's algorithm은 온라인으로 풀기 힘든 쿼리 문제를 오프라인으로 쉽게 풀 수 있게 해주는 알고리즘이다. MO's algorithm은 쿼리를 정렬한 뒤 정렬된 순서대로 처리를 한다. 이론은 이게 끝이다. 이론만 들어서는 아마 문제에 어떻게 적용해야 할 지 감이 안올것이다. 그럼 연습문제를 풀면서 MO's algorithm을 익혀보도록 하자. 연습문제는 https://www.acmicpc.net/problem/13547에서 풀 수 있다. 구간에 존재하는 서로 다른 수의 개수 연습 문제는 아래와 같다. 자연수로 이루어진 \(A_1,\ A_2,\ A_3,\ ...\ ,\ A_{N-1},\ A_{N}\)시퀀스가 있다. 이 때 다음 쿼리를 처리해야 한다. 1. \(x,\ y\ (1 \le x \le y ..
원소들을 효율적으로 관리해야할 일이 있을때 우리는 어떤 전략을 선택해야할까? 원소들을 효율적으로 관리하는 방법은 여러가지가 있다. 이번에는 그 중 하나인 Sqrt Decomposition에 대해 알아보도록 하자. Sqrt Decomposition에서 Sqrt는 Square root의 약자다. 이를 우리나라 말로 번역하자면 평방분할이라고 한다. 하지만 의미적으로 별로 와닿지 않는다고 생각하기 때문에 Sqrt Decomposition이라고 하겠다. 연속적인 원소들을 하나의 묶음으로 Sqrt Decomposition의 기본 아이디어는 정말 간단하다. 연속적인 원소들을 하나의 묶음으로 생각하자는 것이다. 이 때 한 묶음의 크기는 보통 \(\sqrt N\)으로 잡는다.(그래서 Square root라는 이름이 붙은..
방향 그래프가 주어졌을 때 종종 이 그래프 내에서 \(Cycle\)의 존재 유무를 확인해야 할 때가 있다. 이 글에서는 방향 그래프 내에서 싸이클의 존재 유무를 알아내는 알고리즘을 소개하려 한다. 기본적인 알고리즘 \(Cycle\)의 정의를 한번 생각해 보자. \(Cycle\)이란 정점 \(u\)에서 시작해 어떠한 경로를 지나 다시 \(u\)로 돌아오는 경로가 있다면 이를 \(Cycle\)이라고 한다. 그리고 그래프 내에 이러한 \(Cycle\)이 한개라도 있다면 \(Cycle\)이 존재하는 그래프가 된다. 그렇다면 특정한 시작 정점 \(u\)를 잡고 \(dfs\)를 실행해 다시 시작정점 \(u\)로 돌아오는 경로가 있는지 확인하는 알고리즘을 만든 뒤 모든 정점에 대해 해당 알고리즘을 실행하면 \(Cyc..
- Total
- Today
- Yesterday
- Binary Search
- bipartite matching
- disjoint set
- brute force
- DP
- max flow
- Sqrt Decomposition
- Data Structure
- greedy
- graph
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 |